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.

Popular Answer

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.

You should review your notes and see what the teacher said about this, and ask the teacher if you really don't know.

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

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



Licensed under: CC-BY-SA with attribution
Not affiliated with Stack Overflow
Is this KB legal? Yes, learn why
Licensed under: CC-BY-SA with attribution
Not affiliated with Stack Overflow
Is this KB legal? Yes, learn why