Hey, I'm a newbie C programmer doing first semester kind of coding. I'm
attempting to read input from the keyboard of the form "Af RtS"
representing a boolean logic expression, here it represents ((NOT a AND f)
OR (NOT R and t and NOT s)).
This will (eventually) get simplified as much as possible and be used to
generate a PostScript file to draw a circuit diagram (logic gates etc).
I've only just started though and I'm wondering what the best data
structure to store characters is. A linked list will work with the simple
things I'm doing now but ideally I want to be able to use parenthesis to
allow more complicated statements to be made. At the moment I have a kind
of binary tree with each node having an AND and an OR pointer.
A -OR-> R
| |
and and
v v
f t
|
and
v
S
Traversing it by going down each branch sequentially... Not sure how I'm
going to allow parentheses though.
Just wondering if this is a decent way of doing it, any suggestions on
improvements or different ideas much appreciared. Also any comments on
general coding style etc. would be helpful.
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
char letter;
struct node *child;
struct node *sibling;
} node;
node *createFirstNode(char c)
{
node *firstNode = malloc(sizeof(node));
firstNode->letter = c;
firstNode->child = NULL;
firstNode->sibling = NULL;
return firstNode;
}
node *createNode(char c)
{
node *newNode = malloc(sizeof(node));
if(currentNode==NULL)
{
currentParent->sibling = newNode;
currentParent = newNode;
currentNode = newNode;
}
else if(currentNode==currentParent)
{
currentNode->child = newNode;
currentNode = newNode;
}
else
{
currentNode->sibling = newNode;
currentNode = newNode;
}
newNode->letter = c;
return newNode;
}
node *firstNode, currentNode, currentParent;
int main()
{
int i;
char c;
while(1)
{
c = getchar;
if ( c >= 97 && c <= 122 )
{
firstNode=createFirstNode(c);
break;
}
}
currentParent = firstNode;
currentNode = firstNode;
while(1)
{
c = getchar();
if (c == 10) /*if c is the enter key */
{
printf("Finished inputting the tree\n");
break;
}
if (c == 32) /*if c is the space key*/
currentNode=NULL;
if ( c >= 97 && c <= 122 )
{
createNode(c);
printf("fn:%p cp:%p cn:%p\n",firstNode,currentParent,currentNode);
}
}
return(0);
} 1 1255
ekiMbo wrote: Hey, I'm a newbie C programmer doing first semester kind of coding. I'm attempting to read input from the keyboard of the form "Af RtS" representing a boolean logic expression, here it represents ((NOT a AND f) OR (NOT R and t and NOT s)).
This will (eventually) get simplified as much as possible and be used to generate a PostScript file to draw a circuit diagram (logic gates etc). I've only just started though and I'm wondering what the best data structure to store characters is. A linked list will work with the simple things I'm doing now but ideally I want to be able to use parenthesis to allow more complicated statements to be made. At the moment I have a kind of binary tree with each node having an AND and an OR pointer.
A -OR-> R
| | and and v v
f t | and v
S
Traversing it by going down each branch sequentially... Not sure how I'm going to allow parentheses though.
Just wondering if this is a decent way of doing it, any suggestions on improvements or different ideas much appreciared. Also any comments on general coding style etc. would be helpful.
Algorithms and the like are offtopic here.
<OT>
If you are going to evaluate the expressions eventually and for one
set of values for your variables, I suggest going directly for it by
using operator precedence and (recursive) function calls. Only for
evaluating many state combinations of the variables I would go to
the effort of handling a binary tree.
You pass on the read-in string or copies of parts (but I would then
rather use explicit AND and OR operators).
This is no precise formulation of the algorithm, just something to get
you started:
EvalExpression("Af RtS")
looks for the first operator of lowest priority (OR) and passes
everything that comes before encountering ' '/OR (here:"Af") to
EvalOr(). If this returns TRUE, EvalExpression() returns TRUE, else
EvalExpression() returns EvalExpression() of the rest of the string
or FALSE if there is no rest.
EvalOr() looks for AND-Expressions and passes the first to EvalAnd()
in the same way.
EvalAnd() can either look at the value or can pass it on to EvalNot()
or EvalValue(), respectively.
Parentheses and other operators can be fit easily into this scheme;
if you encounter '(', you start looking for the closing parenthesis
(which balances the opening and closing parentheses for the first time)
and pass the "content", that is, the stuff between the parentheses to
EvalExpression() if necessary. You can do this equivalently for your
binary tree.
</OT> #include <stdio.h> #include <stdlib.h>
typedef struct node { char letter; struct node *child; struct node *sibling; } node;
node *createFirstNode(char c) { node *firstNode = malloc(sizeof(node)); firstNode->letter = c; firstNode->child = NULL; firstNode->sibling = NULL; return firstNode; } node *createNode(char c) { node *newNode = malloc(sizeof(node));
if(currentNode==NULL) { currentParent->sibling = newNode; currentParent = newNode; currentNode = newNode; } else if(currentNode==currentParent) { currentNode->child = newNode; currentNode = newNode; } else { currentNode->sibling = newNode; currentNode = newNode; }
newNode->letter = c; return newNode; } node *firstNode, currentNode, currentParent;
This certainly is not your code -- firstNode, currentNode and
currentParent are first declared here but not known in the
above functions. Please give us code that compiles.
Apart from that: You probably mean
node *firstNode, *currentNode, *currentParent; int main() { int i; char c; while(1) { c = getchar;
You probably mean getchar() if ( c >= 97 && c <= 122 )
Do not use hard-coded numbers but the functions from <ctype.h>
to check. Example: If you mean lowercase letters, use islower(). { firstNode=createFirstNode(c); break; } } currentParent = firstNode; currentNode = firstNode;
while(1) { c = getchar(); if (c == 10) /*if c is the enter key */
Dito: use '\n' { printf("Finished inputting the tree\n"); break; } if (c == 32) /*if c is the space key*/
Dito: use ' ' currentNode=NULL; if ( c >= 97 && c <= 122 ) { createNode(c); printf("fn:%p cp:%p cn:%p\n",firstNode,currentParent,currentNode); } }
return(0); }
Please give us the code you work with. This crap does not compile
and certainly will not give results of any sensible kind.
Moreover, it does not implement the algorithm you suggest.
Michael
--
E-Mail: Mine is a gmx dot de address. This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics
by: C++ Shark |
last post by:
Hi,
which stl class is good for creating search trees? I am looking for
something flexible, that allows me to search for a required state (of
matrices, graphs, etc.) quickly.
thanks in...
|
by: Paul Arnold |
last post by:
We are currently in the process of developing a client/server based
generic tree application with which we want to be able to model and
render any size, shape and depth of tree.
Our primary...
|
by: SomeDude |
last post by:
Lo group,
During my quest for the "perfect" way for storing tree-structures it
quickly became clear that all of the available SQL-solutions have their
own peculiar weaknesses (scalability, slow...
|
by: barnesc |
last post by:
Hi again,
Since my linear algebra library appears not to serve any practical
need (I found cgkit, and that works better for me), I've gotten bored
and went back to one of my other projects:...
|
by: Robert Schuldenfrei |
last post by:
Hi NG,
After a break of two months I am back on my project of converting a COBOL
ERP product to C# and SQL Server. I now have to process a tree structure in
C#. Not only am I a newbie in C#,...
|
by: ptrSriram |
last post by:
Can someone help me with an algorithm to merge two binary search trees.
One method I thought of was to flatten both the trees into sorted
lists(inorder traversal),merge those two sorted lists,...
|
by: rose74 |
last post by:
hi
i'd like to know how can i merge two hierarchical trees together.
for instnace to query for each deparatment all its employees with considering to the employees hierarchicy (managers-employees).
|
by: Ganon11 |
last post by:
Hey guys,
OK, taking care of this beforehand; I AM a student in a university. This IS part of my homework, and (as a moderator), I'm doing my best to follow the posting guidelines I work so hard...
|
by: parasuram |
last post by:
Hi friends .............
this is a question regarding the data structures trees
Pleas post it if possible with in 2 days
I will thankful if some body could help doing this.
Operating...
|
by: rsprawls |
last post by:
I found a disk for a b-tree algorithm that I purchased back in 93 or
so. I'd hoped to find this, but now I'd like to know how worthwhile
are b-trees in today's advancements? This is old C code...
|
by: Faith0G |
last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...
|
by: isladogs |
last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM).
In this session, we are pleased to welcome former...
|
by: ryjfgjl |
last post by:
In our work, we often need to import Excel data into databases (such as MySQL, SQL Server, Oracle) for data analysis and processing. Usually, we use database tools like Navicat or the Excel import...
|
by: taylorcarr |
last post by:
A Canon printer is a smart device known for being advanced, efficient, and reliable. It is designed for home, office, and hybrid workspace use and can also be used for a variety of purposes. However,...
|
by: Charles Arthur |
last post by:
How do i turn on java script on a villaon, callus and itel keypad mobile phone
|
by: aa123db |
last post by:
Variable and constants
Use var or let for variables and const fror constants.
Var foo ='bar';
Let foo ='bar';const baz ='bar';
Functions
function $name$ ($parameters$) {
}
...
|
by: emmanuelkatto |
last post by:
Hi All, I am Emmanuel katto from Uganda. I want to ask what challenges you've faced while migrating a website to cloud.
Please let me know.
Thanks!
Emmanuel
|
by: BarryA |
last post by:
What are the essential steps and strategies outlined in the Data Structures and Algorithms (DSA) roadmap for aspiring data scientists? How can individuals effectively utilize this roadmap to progress...
|
by: Sonnysonu |
last post by:
This is the data of csv file
1 2 3
1 2 3
1 2 3
1 2 3
2 3
2 3
3
the lengths should be different i have to store the data by column-wise with in the specific length.
suppose the i have to...
| |