Past exam question: 2079 Ashwin (Back), Q2(b)
Open in the Padhaiko appQuestion
Convert the following infix expression to postfix expression with required status of stack.
Solution
Infix to Postfix Conversion Algorithm Rules:
- Operands are directly appended to the postfix output expression.
- Left parenthesis
(is pushed onto the operator stack. - Operators (
+,-,*,/) are pushed after popping any operators on the stack with greater or equal precedence (inside parentheses,(has the lowest precedence). Precedence order:*,/>+,-. - Right parenthesis
)pops operators from the stack and appends them to the postfix output until the matching(is encountered, which is discarded.
Step-by-Step Stack Status and Postfix Trace: Tracing through each symbol of the given expression:
| Step | Symbol Scanned | Operator Stack (Bottom Top) | Postfix Output Buffer | Action Taken |
|---|---|---|---|---|
| 1 | ( | ( | (empty) | Push ( |
| 2 | ( | ( ( | (empty) | Push ( |
| 3 | a | ( ( | a | Append operand a |
| 4 | + | ( ( + | a | Push + |
| 5 | ( | ( ( + ( | a | Push ( |
| 6 | ( | ( ( + ( ( | a | Push ( |
| 7 | b | ( ( + ( ( | a b | Append operand b |
| 8 | * | ( ( + ( ( * | a b | Push * |
| 9 | c | ( ( + ( ( * | a b c | Append operand c |
| 10 | ) | ( ( + ( | a b c * | Pop *, discard ( |
| 11 | / | ( ( + ( / | a b c * | Push / |
| 12 | ( | ( ( + ( / ( | a b c * | Push ( |
| 13 | d | ( ( + ( / ( | a b c * d | Append operand d |
| 14 | - | ( ( + ( / ( - | a b c * d | Push - |
| 15 | e | ( ( + ( / ( - | a b c * d e | Append operand e |
| 16 | ) | ( ( + ( / | a b c * d e - | Pop -, discard ( |
| 17 | ) | ( ( + | a b c * d e - / | Pop /, discard ( |
| 18 | ) | ( | a b c * d e - / + | Pop +, discard ( |
| 19 | ) | (empty) | a b c * d e - / + | Discard matching ( |
Algebraic Sub-expression Verification: Decomposing the parenthesized sub-expressions to verify correctness:
- Inner multiplication:
- Inner subtraction:
- Inner division:
- Outer addition:
Both the algorithmic stack simulation and structural derivation yield identical results.
Answer:
The converted postfix expression is:
(or in compact form: abc*de-/+)