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]
Asked
Active
Viewed 1.8k times
8
Oliver Charlesworth
- 267,707
- 33
- 569
- 680
Mudasir Soomro
- 140
- 1
- 1
- 9
-
4What did you try? A recursive descent function?? – Basile Starynkevitch Dec 04 '11 at 14:21
-
2When this is homework then please state that it is. – H H Dec 04 '11 at 14:25
-
reverse as in convert it in prefix first? yea that's what i figured, that is, after reversing it, create a node of first operator, and then the next operand/operator as its left node and the next to that one as its right! and so on.. – Mudasir Soomro Dec 04 '11 at 17:50
-
you use the stack if processing from forward. – BLUEPIXY Dec 04 '11 at 22:09
-
ahan, i used stack, its working – Mudasir Soomro Dec 05 '11 at 06:20
-
Why? You already have postfix, and all you need from there is a stack. You don't need a tree. Unclear what you're asking for, – user207421 Mar 06 '16 at 09:01
2 Answers
18
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.
Kevin Reid
- 37,492
- 13
- 80
- 108
0
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)
}
Taher A. Ghaleb
- 5,120
- 5
- 31
- 44
