# Parser tree or expression tree

c expression-trees parsing ### Question

I'm doing a command line calculator, so I need to parse expressions.

``````calc 2*(3+4)*5
``````

I already have the scanner step done, returning a token's array. Now I'm at parser step. However I have no clue about how to do a parser/expression tree.

This is all I have so far:

``````NODE* create_node(TOKEN* t) {
NODE* n = (NODE*)malloc(sizeof(NODE));
n->t = t;
n->l = n->r = 0;
return n;
}

void insert_node(NODE** top, NODE** n) {
if (!*top) {
*top = *n;
return;
}

if (!(*top)->l) insert_node(&(*top)->l, n);
else
if (!(*top)->r) insert_node(&(*top)->r, n);
else
insert_node(&(*top)->l, n);
}
``````

Then I pass the token array like:

``````while (*tokens != 0) {
NODE* n = create_node(*tokens++);
insert_node(&root, &n);
}
``````

As you can see my tree just raise to the left. I have no clue how to make it works ordering by operators at the top and numbers as leafs including operators precedence order.

I would appreciate an enlightenment, also in programming (code) terms.

1
3
10/18/2012 3:24:54 PM

#### Fastest Entity Framework Extensions

Your code for creating nodes looks okay to me. The problem is that you need code to figure out how to properly build the binary tree. You can't just stick a node anywhere you find a NULL pointer.

Your example expression: `2*(3+4)*5`

Would turn into something like:

``````    *
/ \
*   5
/ \
2   +
/ \
3   4
``````

Your teacher should have given you some idea how to do this.

When I was in college, I wrote this sort of code, and we wrote our own "recursive descent parser". Another popular approach would be to use a system like GNU Bison.

http://en.wikipedia.org/wiki/Recursive_descent_parser

http://en.wikipedia.org/wiki/GNU_bison

8
6/13/2012 11:25:17 PM

Prime Library

More Projects...