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

Popular Answer

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.

Review your notes to see what the instructor said about this, and if you're still unsure, ask the instructor.

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

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

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


Related Questions





Licensed under: CC-BY-SA with attribution
Not affiliated with Stack Overflow
Licensed under: CC-BY-SA with attribution
Not affiliated with Stack Overflow