Computing the value of a Binary Expression Tree

Question

I have a binary tree constructor that will take prefix notation in a string and will ultimately print out something like this:

|-- *
    |-- 2
    |-- +
        |-- 4
        |-- +
            |-- 6
            |-- 7

The prefix notation for this tree is: (* 2 (+ 4 (+ 6 7))) The value should be: 2*17 = 34. I understand that stacks are used when computing these trees, but I'm not sure how to go about it.

The idea that I have, is that there are two stacks. One for operators and one for operands. When two operands are put in, the last operator is taken out, and the new operand is put where?

Additionally, I need to take the tree above, and return a postfix, infix, and prefix notation. Every time I try and do so, it spits out a prefix notation.

Answer 1

This is really easy:

int eval(tree) {
    if tree is just a number return that number
    else {
        l = eval(tree.left)
        r = eval(tree.right)
        return result of operation on l and r
    }
}

Likewise, for the printing. Prefix means, you first print the operaor, then the left subtree, then the right subtree. Postfix would mean: first the left subtree, then the right subtree, then the operator.

Only infix is a bit more complicated, because you perhaps need to print the subtress in parentheses.

Answer 2

To my understanding, it should not be necessary to have two stacks. If I recall correctly, the algorithm for evaluation of the tree can be either implemented recursively or via a stack - as long as the top of stack is an operator, replace the top of stack with the value of the expression of the corresponding opration. I believe the approach is connected to the so-called "Polish notation" of the term.