# Parser tree or expression tree

c expression-trees parsing

### Question

In order to create a command-line calculator, I must parse expressions.

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

I've already finished the scanning phase, which returns an array of tokens. My current step is the parser. But I have no idea how to create a parser or expression tree.

I only have this at the moment:

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

I then send the token array as follows:

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

My tree is just rising to the left, as you can see. I have no idea how to make it work with operator precedence order at the top and numbers acting as leaves.

I would value some clarification, even in terms of programming (code).

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

#### Fastest Entity Framework Extensions

I like how your node-creation code works. The issue is that you need code to determine how to correctly construct the binary tree. Nodes cannot simply be inserted anywhere a NULL pointer is present.

Your illustrative phrase:`2*(3+4)*5`

would evolve to become:

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

Your instructor ought to have explained how to accomplish this to you.

I used to write code like this in college, and my team and I even created our own "recursive descent parser." Using a system like GNU Bison is a common alternative strategy.

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...