How to put postfix expressions in a binary tree?

问题:

so i have a binary tree and a postfix expression "6 2 * 3 /" what is the algo to put it in a tree? like,

          [/]
          / \
        [*]  [3]
        / \
      [6] [2]

回答1:

To construct a tree from the expression, pretend you are evaluating it directly but construct trees instead of calculating numbers. (This trick works for many more things than postfix expressions.)

Algorithm: Have a stack to store intermediate values (which are trees), and examine each token from left to right:

• If it is a number, turn it into a leaf node and push it on the stack.
• If it is an operator, pop two items from the stack, construct an operator node with those children, and push the new node on the stack.

At the end, if the expression is properly formed, then you should have exactly one tree on the stack which is the entire expression in tree form.

回答2:

Postfix-to-tree(j){
  n <--ALLOCATE_NODE(A[j],NULL,NULL)
    Switch
      case Postfix[j] is a binary operator
        do j <--j-1
         right[n] <-- Postfix-to-tree(j)
              j <-- j-1
              left[n] <--postfix-to-tree(j)
                 case postfix[j] is a unary operator 
               do j <-- j-1
                  right[n] <-- Postfix-to-tree(j)
}