Trees Query

[ekiMbo]

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);
}

 

[Michael Mair]

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.

#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 )

{
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