Past exam question: 2075 Baisakh (Back), Q2
Open in the Padhaiko appQuestion
Define stack. How to convert infix to postfix notation? Explain with example. Evaluate the postfix expression AB+C*DEFG-*+ with status of stack where A = 2, B = 3, C = 10, D = 5, E = 2, F = 4 and G = 6.
Solution
Definition of Stack and Infix-to-Postfix Conversion Rule: A stack is a LIFO linear ADT (push and pop at top). To convert infix to postfix:
- Scan infix left to right. Output operands immediately.
- Push
(onto the stack. - On operator
op, pop and output stack operators with greater or equal precedence (except right-associative^, which pops only strictly greater precedence), then pushop. - On
), pop and output until(is popped and discarded. - At end of expression, pop remaining stack operators.
Example: A + B * C: output A, push +, output B, push * (), output C, pop * then + A B C * +.
Postfix Evaluation Trace (A=2, B=3, C=10, D=5, E=2, F=4, G=6): Literal sequence: 2 3 + 10 * 5 2 4 6 - * +
| Token | Action | Stack (Bottom Top) |
|---|---|---|
2 | Push 2 | [2] |
3 | Push 3 | [2, 3] |
+ | [5] | |
10 | Push 10 | [5, 10] |
* | [50] | |
5 | Push 5 | [50, 5] |
2 | Push 2 | [50, 5, 2] |
4 | Push 4 | [50, 5, 2, 4] |
6 | Push 6 | [50, 5, 2, 4, 6] |
- | [50, 5, 2, -2] | |
* | [50, 5, -4] | |
+ | [50, 1] |
With a missing trailing + (AB+C*DEFG-*++), popping 1 and 50 gives .
Answer:
- Stack & Infix-to-Postfix: Operands pass directly to output while operators are buffered on a LIFO stack by precedence (e.g.,
A + B * C -> A B C * +). - Evaluation of
AB+C*DEFG-*+: Leaves[50, 1]on the stack due to the missing sixth binary operator in the printed question (yielding if the intended trailing operator is+).