PadhaikoAll subjects

Past exam question: 2078 Poush (Back), Q1(b)

Data Structure and Algorithms · 5 marks

Open in the Padhaiko app

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

Question

Convert the following infix expression postfix expression showing stack status in each step. A + (B * C - (D / E ^ F) * G) * H

Solution

Precedence and Associativity Rules:

Tabular Conversion Trace:

SymbolStack (Bottom Top)Postfix OutputAction
A(empty)AAppend A
++APush +
(+ (APush (
B+ (A BAppend B
*+ ( *A BPush *
C+ ( *A B CAppend C
-+ ( -A B C *Pop *, push -
(+ ( - (A B C *Push (
D+ ( - (A B C * DAppend D
/+ ( - ( /A B C * DPush /
E+ ( - ( /A B C * D EAppend E
^+ ( - ( / ^A B C * D EPush ^
F+ ( - ( / ^A B C * D E FAppend F
)+ ( -A B C * D E F ^ /Pop ^, /, discard (
*+ ( - *A B C * D E F ^ /Push *
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 * -Push *
H+ *A B C * D E F ^ / G * - HAppend H
(end)(empty)A B C * D E F ^ / G * - H * +Pop *, +
Answer:

The converted postfix expression is:

(ABC*DEF^/G*-H*+).

All past exam questions for Data Structure and Algorithms