Past exam question: 2064 Jestha, Q1
Open in the Padhaiko appQuestion
Define stack as an ADT. Write an algorithm for evaluating postfix expression. Evaluate a given postfix expression: 4 6 4 + * 8 / 4 - in tabular form showing stack after every step.
Solution
Stack as an Abstract Data Type (ADT):
- Value Definition: An ordered LIFO collection of items where insertions (
push) and deletions (pop) occur strictly at one endpointtop. - Operations:
createStack(),isEmpty(S),isFull(S),push(S, x),pop(S),peek(S).
Algorithm for Postfix Evaluation:
Algorithm EVAL_POSTFIX(expr):
1. Initialize empty operand stack S
2. For each token tok in expr from left to right:
If tok is an operand:
PUSH(S, numeric_value(tok))
Else (tok is a binary operator op):
op2 = POP(S)
op1 = POP(S)
res = APPLY(op1, op, op2)
PUSH(S, res)
3. Return POP(S)Tabular Stack Trace for 4 6 4 + * 8 / 4 -:
| Token | Action | Operand Stack (Bottom Top) |
|---|---|---|
4 | Push 4 | [4] |
6 | Push 6 | [4, 6] |
4 | Push 4 | [4, 6, 4] |
+ | Pop 4, 6 | [4, 10] |
* | Pop 10, 4 | [40] |
8 | Push 8 | [40, 8] |
/ | Pop 8, 40 | [5] |
4 | Push 4 | [5, 4] |
- | Pop 4, 5 | [1] |
Answer:
Final evaluated value of 4 6 4 + * 8 / 4 - is .