PadhaikoAll subjects

Past exam question: 2074 Bhadra (Regular), Q2

Data Structure and Algorithms · 10 marks

Open in the Padhaiko app

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

Question

Convert A + B - C * (D - E + F/G) / H expression into postfix expression using stack.

Solution

Precedence and Associativity Rules:

Tabular Stack Trace:

SymbolStack (Bottom Top)Postfix OutputAction
A(empty)AAppend A
++APush +
B+A BAppend B
--A B +Pop + (equal prec), push -
C-A B + CAppend C
*- *A B + CPush *
(- * (A B + CPush (
D- * (A B + C DAppend D
-- * ( -A B + C DPush -
E- * ( -A B + C D EAppend E
+- * ( +A B + C D E -Pop - (equal prec), push +
F- * ( +A B + C D E - FAppend F
/- * ( + /A B + C D E - FPush /
G- * ( + /A B + C D E - F GAppend G
)- *A B + C D E - F G / +Pop /, +, discard (
/- /A B + C D E - F G / + *Pop * (equal prec), push /
H- /A B + C D E - F G / + * HAppend H
(end)(empty)A B + C D E - F G / + * H / -Pop /, -
Answer:

Converted postfix expression:

(AB+CDE-FG/+*H/-).

All past exam questions for Data Structure and Algorithms