Past exam question: 2078 Chaitra (Regular), Q2
Open in the Padhaiko appQuestion
Define stack. Convert following infix expression to postfix expression showing stack status in each step; A×(B+C) -(B^D)×A + E / F.
Solution
Definition of Stack: A stack is a linear Abstract Data Type (ADT) that follows the Last-In, First-Out (LIFO) principle: insertions (push) and deletions (pop) occur strictly at one end called the top. Attempting to push onto a full stack causes Stack Overflow, and attempting to pop from an empty stack causes Stack Underflow.
Operator Precedence and Associativity Rules:
^(Exponentiation): Highest precedence, right-associative.×(*),/: Medium precedence, left-associative.+,-: Lowest precedence, left-associative.(is pushed directly onto the stack; when)is scanned, pop operators to output until(is popped and discarded.- Note: In the printed expression
A×(B+C) -(B^D)×A + E / F,×denotes multiplication (*).
Tabular Stack Trace for A*(B+C)-(B^D)*A+E/F:
| Scanned Symbol | Stack (Bottom Top) | Postfix Output | Action |
|---|---|---|---|
A | (empty) | A | Append operand A |
× | × | A | Push × |
( | × ( | A | Push ( |
B | × ( | A B | Append operand B |
+ | × ( + | A B | Push + |
C | × ( + | A B C | Append operand C |
) | × | A B C + | Pop +, discard ( |
- | - | A B C + × | Pop × (), push - |
( | - ( | A B C + × | Push ( |
B | - ( | A B C + × B | Append operand B |
^ | - ( ^ | A B C + × B | Push ^ |
D | - ( ^ | A B C + × B D | Append operand D |
) | - | A B C + × B D ^ | Pop ^, discard ( |
× | - × | A B C + × B D ^ | Push × () |
A | - × | A B C + × B D ^ A | Append operand A |
+ | + | A B C + × B D ^ A × - | Pop × then - (equal/higher precedence), push + |
E | + | A B C + × B D ^ A × - E | Append operand E |
/ | + / | A B C + × B D ^ A × - E | Push / () |
F | + / | A B C + × B D ^ A × - E F | Append operand F |
| (end) | (empty) | A B C + × B D ^ A × - E F / + | Pop / then + |
Answer:
- Stack: A LIFO linear data structure supporting
push,pop, andpeekat a singletopend. - Converted Postfix Expression:
(or ABC+*BD^A*-EF/+ using * for multiplication).