-
The following postfix expression with single digit operands is evaluated using a stack :
8 2 3 ^/ 2 3 * + 5 1 * -
Note that ^ is the exponentiation operator. The top two elements of the stack after the first * is evaluated are
-
- 6, 1
- 5, 7
- 3, 2
- 1, 5
- 6, 1
Correct Option: A
The algorithm for evaluating any postfix expression is fairly straightforward :
1. While there are input tokens left
o Read the next token from input.
o If the token is a value
+ Push it onto the stack.
o Otherwise, the token is an operator
(operator here includes both operators, and functions).
* It is known a priori that the operator takes n arguments.
* If there are fewer than n values on the stack (Error) The user has not input sufficient values in the expression.
* Else, Pop the top n values from the stack.
* Evaluate the operator, with the values as arguments.
* Push the returned results, if any, back onto the stack.
2. If there is only one value in the stack
o That value is the result of the calculation.
3. If there are more values in the stack
o (Error) The user input has too many values.
Let us run the above algorithm for the given expression. First three tokens are values, so they are simply pushed. After pushing 8, 2 and 3, the stack is as follows 8, 2, 3
When ^ is read, top two are popped and power(2^3) is calculated 8, 8
When/ is read, top two are popped and division(8/8) is performed 1
Next two tokens are values, so they are simply pushed.
After pushing 2 and 3, the stack is as follows 1, 2, 3
When * comes, top two are popped and multiplication is performed 1, 6