Expression tree is a binary tree in which each internal node corresponds to operator and each leaf node corresponds to operand. Consider the expression:
(a + b*c) * ( d + e)
It can be represented as a binary tree as
In-order traversal, reconstructs the expression:
(a + b*c) * ( d + e) i.e Infix notation. Post-order traversal results in the corresponding postfix expression:
a b c * + d e + *.
Given a postfix expression, we can construct the expression tree, using a stack that contains pointers to the tree nodes. We loop through input expression and do following for every character.
- If the symbol is an operand, we create a one-node tree and push a pointer to it into a stack.
- If the symbol is an operator, we pop twice pointers to two trees T1 and T2 (T1 is popped first) and form a new tree whose root is the operator and whose left and right children are T2 and T1, respectively. A pointer to this new tree is then pushed onto the stack.
Example: Consider the expression (a + b) * (c * (d + e)). The postfix expression is:
a b + c d e + * *
Steps for constructing expression tree
- The first tow symbols are operands, so we create one-node trees and push pointers to them onto a stack.
- Next, we read ‘+’ so two pointers to trees are popped, a new tree is formed, and a pointer to it is pushed onto the stack.
- Next, c, d, and e are read, and for each a one-node tree is created and a pointer to the corresponding tree is pushed onto the stack.
- Then we read ‘ + ‘ and two trees are having ‘d’ and ‘e’ as root are merged.
- Then, ‘ * ‘ is read, so we pop two tree pointers (root nodes are ‘c’ and ‘+’ ) and form a new tree with ‘*’ as root.
- Finally, the last symbol ‘*’ is read, two trees are merged, and a pointer to the final tree is pushed onto the stack.
As all the operators in the tree are binary hence each node will have either 0 or 2 children. As it can be inferred from the examples above , the integer values would appear at the leaf nodes , while the interior nodes represent the operators. To evaluate a recursive approach can be followed.
// Let t be the syntax tree If t is not null then If t.val is operand then return t.val else A = solve(t.left) B = solve(t.right) return A t.operator B