What postfix expression does the following infix expression translate to? 2 + 3 - 4 / 3 * 3 + 4 I'm really confused on how does it translate to 2 3 4 3 / 3 * - + 4 +?. Can somebody explain it, please?
Thanks in advance
Put parens around the infix to show order of operations honoring precedence and associativity:
((2 + 3) - ((4 / 3) * 3)) + 4
Now you can use this to draw a syntax tree:
+
_________/ \_
| |
- 4
_/ \____
| |
+ *
/ \ _/ \_
2 3 | |
'/' 3
/ \
4 3
Now you can get postfix by traversing the tree in post order:
2 3 + 4 3 / 3 * - 4 +
There are other post orders that give the right answer. For example, you can get more by choosing to evaluate either the left or the right subtree first for each commutative operator. Equivalently, you can reverse the left and right hand subtrees for each commutative operator and always use a standard, left child first post order search.
You can check the order by executing it with a stack machine:
Stack
read 2, push 2 [2
read 3, push 3 [2 3
read +, pop 3, pop 2, push 5 (i.e. 2 + 3) [5
read 4, push 4 [5 4
read 3, push 3 [5 4 3
read /, pop 3, pop 4, push 1.33... (i.e. 4/3) [5 1.33...
read 3, push 3 [5 1.33... 3
read *, pop 3, pop 1.33..., push 4 (i.e. 1.33... * 3)[5 4
read -, pop 4, pop 5, push 1 (i.e. 5 - 4) [1
read 4, push 4 [1 4
read +, pop 4, pop 1, push 5 (i.e. 1 + 4) [5
So 5 is the answer, which agrees with the infix evaluation.