PadhaikoAll subjects

Past exam question: 2078 Baishakh (Back), Q2

Data Structure and Algorithms · 8 marks

Open in the Padhaiko app

Topic: Definition of stack and its operations · Array implementation of…

Question

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).

SymbolStackPostfix 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 * -

TokenActionOperand Stack (Bottom Top)
10Push 10[10]
5Push 5[10, 5]
+Pop 5, 10 [15]
4Push 4[15, 4]
6Push 6[15, 4, 6]
*Pop 6, 4 [15, 24]
3Push 3[15, 24, 3]
/Pop 3, 24 [15, 8]
8Push 8[15, 8, 8]
+Pop 8, 8 [15, 16]
-Pop 16, 15 [-1]
2Push 2[-1, 2]
1Push 1[-1, 2, 1]
*Pop 1, 2 [-1, 2]
-Pop 2, -1 [-3]
Answer:

All past exam questions for Data Structure and Algorithms