I need to figure out the value of this postfix expression
3 2 * 2 ↑ 5 3 - 8 4 / * -
Can someone help?
Thanks, I'm new here
Welcome to the forum. For a reasonable price, I can sell you an HP 50g calculator that uses reverse polish notation. You can enter this expression and get the result. Just kidding.
Why don't you read the algorithm for evaluating a postfix expression and the following example? I think the explanation is pretty clear.
Hi,
If you don't know about the stack data structure, you can quit reading now.
Otherwise, here's my description of the algorithm:
Assume all operands (as in your example) are single digit integers. For a valid postfix expression, scan the string from left to right.
1. If the current token is an operand, push it.
2. If the current token is an operator, pop the two operands (first pop is second operand), perform the operation and push the result.
3. At the end of the scan, the one value on the stack is the value of the expression.
Examples:
1. 5 2 -: push 5, push 2, pop 2 pop 5, compute 5-2=3 and push 3. Value is 3.
2. 2 3 4 * + 2 3 ^ +: push 2, push 3, push 4, pop 4, pop 3, push (3*4=12), pop 12, pop 2, push(2+12=14), push 2, push 3, pop 3, pop 2, push(2^3=8), pop 8, pop 14, push(14+8=22), Value is 22.
For long expressions, it may help to draw the contents of the stack at each stage. Finally, the above algorithm also detects errors in the expression: if at any point, an operator that requires two operands is encountered, but there is only one value on the stack, then expression error. Also at conclusion, if there is not exactly one operand on the stack, again error.
A good way to visualize your expression is with a binary tree. The operator is the third term in every expression. So starting, we have:
*
/ \
3 2
We then treat this cluster (3 2 *) as a single value. So we have ((3 2 *) 2 ^). Again, the carat is the root of a tree with the left child as * and the right child as 2.
We then examine (5 3 *), which we construct as its own binary tree. We do the same for (8 4 /). The * operator in ( (5 3 *) (8 4 /) *) tells us that * is the root for these two binary trees. Finally, we connect the - operator to the carat and * operators.
The algorithm is great if you are programming a solution for this. The binary tree is quite easy to visualize. In essence, the algorithm is using stacks and queues to traverse a binary tree structure without having the physical node-based backbone present. This is one of Dijkstra's algorithms, though not the famous shortest path algorithm. Hope this helps some!