Thread: N-ary tree setup?

Hello there,

I'm not new to writing programs but I am quite new to proper programming (i.e. C);

Anyways, I have to write a program to parse an expression into a boolean circuit. The expressions have to follow a strict grammar. For example:

Code:

xY zRg     =    ((x AND (NOT y) OR (z AND (NOT r) AND g))

I'm thinking the best way to implement this would be using an N-ary tree. But I have no idea how to set one up.

Can someone show me how to set one up simply, please?

Thanks for your time,

G.

I had once implemented what you ask. Yeah, a tree is perfect for what you want. You will probably need a 3-ary tree. Okay, you know the board's policy about homework. So I ll give you some code to start with and you can continue from there. If you get stuck just post again.
Here is how you would define a node for a 3-ary tree. I will make it double-linked, meaning you can go up and down the tree.

Code:

typedef nodeTag {
    struct nodeTag *rightChild;
    struct nodeTag *leftChild;
    char operator;
    char leftVar;
    char rightVar;
} node;

So you have a node. Now, you will connect all the nodes with the next and previous pointers. Each node will have tree character. The operator for AND, OR etc etc resambled as 'a', 'o' etc etc and two variables.

The above code should get you stared. For example you can create two nodes like:

Code:

node *root; //the starting point
node n1;
node n2;
node n3;
root = &n1;
n1.rightChild = &n2;
n1.leftChild = &n3
n2.leftChild = NULL;
...
n3.righChild = NULL;
...
n1.operator = '0'; 
n1.leftVar = 'x';
...
// go through one path of the tree through the left childs and make every operator 'a'
node *ptr = root;
while (ptr != NULL) {
    (*ptr).operator = 'a'
    ptr = ptr->leftChild;
}

It needs some work by the way...

Excellent, thank you very much.

Yes I'm aware of the HW policy, I wasn't look for spoon feeding, just a point in the right direction. Anyway, I want to achieve this myself!

G.