Postfix notation to expression tree

Question

There are enough resources on how to convert an expression tree into postfix notation, and it's not that hard.

But I have to parse a postfix expression into an expression tree.

The expression is:

A 2 ^ 2 A * B * - B 2 ^ + A B - /

I don't really have a clue on how to interpret the expression. Does someone has a clue on how to proces this?

Answer 1

Create a stack containing nodes that could be part of a tree

1. Push operands on a stack (A, 2, B, etc. are operands) as leaf-nodes, not bound to any tree in any direction
2. For operators, pop the necessary operands off the stack, create a node with the operator at the top, and the operands hanging below it, push the new node onto the stack

For your data:

1. Push A onto the stack
2. Push 2 onto the stack
3. Pop A and 2, create ^-node (with A and 2 below), push it on the stack
4. Push 2 on stack
5. Push A on stack
6. Pop 2 and 2 and combine to form the *-node
7. etc.
8. etc.

This would give you the following tree for your data:

A 2 ^ 2 A * B * - B 2 ^ + A B - /

                     /
              +         -
     -            ^    A B
 ^        *      B 2
A 2    *    B
      A 2

hope this tree is readable :P

Answer 2

Does this look correct:

for n in items:
    if n is argument:
        push n
    if n is operator:
        a = pop
        b = pop
        push a+n+b
 answer = pop



A 2 ^ 2 A * B * - B 2 ^ + A B - /

Running this on your statment should yield a stack that evolves like this:

[A]
[A, 2]
[A^2]
[A^2, 2]
[A^2, 2, A]
[A^2, 2*A]
[A^2, 2*A, B]
[A^2, 2*A*B]
[A^2-2*A*B]
[A^2-2*A*B, B]
[A^2-2*A*B, B, 2]
[A^2-2*A*B, B^2]
[A^2-2*A*B+B^2]
[A^2-2*A*B+B^2, A]
[A^2-2*A*B+B^2, A, B]
[A^2-2*A*B+B^2, A-B]
[A^2-2*A*B+B^2/A-B]