PadhaikoAll subjects

Past exam question: 2073 Bhadra (Regular), Q2(b)

Data Structure and Algorithms · 5 marks

Open in the Padhaiko app

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

Question

Show status of stack while converting following infix expression to postfix expression: A+B-(C*D/E+F)-G*H.

Solution

Operator Precedence Rules: *, / +, - (all left-associative).

Tabular Stack Trace:

SymbolStack (Bottom Top)Postfix OutputAction
A(empty)AOutput A
++APush +
B+A BOutput B
--A B +Pop +, push -
(- (A B +Push (
C- (A B + COutput C
*- ( *A B + CPush *
D- ( *A B + C DOutput D
/- ( /A B + C D *Pop *, push /
E- ( /A B + C D * EOutput E
+- ( +A B + C D * E /Pop /, push +
F- ( +A B + C D * E / FOutput F
)-A B + C D * E / F +Pop +, discard (
--A B + C D * E / F + -Pop -, push -
G-A B + C D * E / F + - GOutput G
*- *A B + C D * E / F + - GPush *
H- *A B + C D * E / F + - G HOutput H
(end)(empty)A B + C D * E / F + - G H * -Pop *, -
Answer:

Converted postfix expression: A B + C D * E / F + - G H * - (AB+CD*E/F+-GH*-).

All past exam questions for Data Structure and Algorithms