Past exam question: 2078 Baishakh (Back), Q2
Open in the Padhaiko appQuestion
Convert the infix expression: A+B-(C*D/E+F)-G*H into postfix expression using stack. Evaluate the converted postfix expression using stack for A=10, B=5, C=4, D=6, E=3, F=8, G=2, and H=1.
Solution
Infix to Postfix Conversion (A+B-(C*D/E+F)-G*H): Precedence: *, / +, - (all left-associative).
| Symbol | Stack | Postfix Output |
|---|---|---|
A | (empty) | A |
+ | + | A |
B | + | A B |
- | - | A B + |
( | - ( | A B + |
C | - ( | A B + C |
* | - ( * | A B + C |
D | - ( * | A B + C D |
/ | - ( / | A B + C D * |
E | - ( / | A B + C D * E |
+ | - ( + | A B + C D * E / |
F | - ( + | A B + C D * E / F |
) | - | A B + C D * E / F + |
- | - | A B + C D * E / F + - |
G | - | A B + C D * E / F + - G |
* | - * | A B + C D * E / F + - G |
H | - * | A B + C D * E / F + - G H |
| (end) | (empty) | A B + C D * E / F + - G H * - |
Postfix Evaluation Trace (A=10, B=5, C=4, D=6, E=3, F=8, G=2, H=1): Expression: 10 5 + 4 6 * 3 / 8 + - 2 1 * -
| Token | Action | Operand Stack (Bottom Top) |
|---|---|---|
10 | Push 10 | [10] |
5 | Push 5 | [10, 5] |
+ | Pop 5, 10 | [15] |
4 | Push 4 | [15, 4] |
6 | Push 6 | [15, 4, 6] |
* | Pop 6, 4 | [15, 24] |
3 | Push 3 | [15, 24, 3] |
/ | Pop 3, 24 | [15, 8] |
8 | Push 8 | [15, 8, 8] |
+ | Pop 8, 8 | [15, 16] |
- | Pop 16, 15 | [-1] |
2 | Push 2 | [-1, 2] |
1 | Push 1 | [-1, 2, 1] |
* | Pop 1, 2 | [-1, 2] |
- | Pop 2, -1 | [-3] |
Answer:
- Postfix Expression:
A B + C D * E / F + - G H * -(AB+CD*E/F+-GH*-). - Evaluated Value: .