PadhaikoAll subjects

Past exam question: 2077 Chaitra (Regular), Q2

Data Structure and Algorithms · 8 marks

Open in the Padhaiko app

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

Question

Define stack. Convert following infix expression showing stack status after every step. (A*B*(((C^X+D^Y)+E/Z)*F)))

Solution

Definition of Stack: A stack is a linear LIFO (Last-In, First-Out) Abstract Data Type in which insertions (push) and deletions (pop) occur solely at one end called top.

Tabular Stack Trace for (A*B*(((C^X+D^Y)+E/Z)*F))):

SymbolStack (Bottom Top)Postfix OutputAction
(((empty)Push (
A(AAppend A
*( *APush *
B( *A BAppend B
*( *A B *Pop * (equal prec), push *
(( * (A B *Push (
(( * ( (A B *Push (
(( * ( ( (A B *Push (
C( * ( ( (A B * CAppend C
^( * ( ( ( ^A B * CPush ^
X( * ( ( ( ^A B * C XAppend X
+( * ( ( ( +A B * C X ^Pop ^, push +
D( * ( ( ( +A B * C X ^ DAppend D
^( * ( ( ( + ^A B * C X ^ DPush ^
Y( * ( ( ( + ^A B * C X ^ D YAppend Y
)( * ( (A B * C X ^ D Y ^ +Pop ^, +, discard (
+( * ( ( +A B * C X ^ D Y ^ +Push +
E( * ( ( +A B * C X ^ D Y ^ + EAppend E
/( * ( ( + /A B * C X ^ D Y ^ + EPush /
Z( * ( ( + /A B * C X ^ D Y ^ + E ZAppend Z
)( * (A B * C X ^ D Y ^ + E Z / +Pop /, +, discard (
*( * ( *A B * C X ^ D Y ^ + E Z / +Push *
F( * ( *A B * C X ^ D Y ^ + E Z / + FAppend F
)( *A B * C X ^ D Y ^ + E Z / + F *Pop *, discard (
)(empty)A B * C X ^ D Y ^ + E Z / + F * *Pop *, discard (
)(empty)A B * C X ^ D Y ^ + E Z / + F * *Extra unmatched ) ignored
Answer:

Ignoring the stray unmatched trailing ), the converted postfix expression is:

(AB*CX^DY^+EZ/+F**).

All past exam questions for Data Structure and Algorithms