Past exam question: 2078 Poush (Back), Q1(b)
Open in the Padhaiko appQuestion
Convert the following infix expression postfix expression showing stack status in each step. A + (B * C - (D / E ^ F) * G) * H
Solution
Precedence and Associativity Rules:
^: highest precedence, right-associative.*,/: medium precedence, left-associative.+,-: lowest precedence, left-associative.
Tabular Conversion Trace:
| Symbol | Stack (Bottom Top) | Postfix Output | Action |
|---|---|---|---|
A | (empty) | A | Append A |
+ | + | A | Push + |
( | + ( | A | Push ( |
B | + ( | A B | Append B |
* | + ( * | A B | Push * |
C | + ( * | A B C | Append C |
- | + ( - | A B C * | Pop *, push - |
( | + ( - ( | A B C * | Push ( |
D | + ( - ( | A B C * D | Append D |
/ | + ( - ( / | A B C * D | Push / |
E | + ( - ( / | A B C * D E | Append E |
^ | + ( - ( / ^ | A B C * D E | Push ^ |
F | + ( - ( / ^ | A B C * D E F | Append F |
) | + ( - | A B C * D E F ^ / | Pop ^, /, discard ( |
* | + ( - * | A B C * D E F ^ / | Push * |
G | + ( - * | A B C * D E F ^ / G | Append G |
) | + | A B C * D E F ^ / G * - | Pop *, -, discard ( |
* | + * | A B C * D E F ^ / G * - | Push * |
H | + * | A B C * D E F ^ / G * - H | Append H |
| (end) | (empty) | A B C * D E F ^ / G * - H * + | Pop *, + |
Answer:
The converted postfix expression is:
(ABC*DEF^/G*-H*+).