How to put postfix expressions in a binary tree?
-
28-10-2019 - |
Question
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]
Solution
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.
OTHER TIPS
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)
}
Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow