PadhaikoAll subjects

Past exam question: 2066 Jestha (Back), Q1

Data Structure and Algorithms · 8 marks

Open in the Padhaiko app

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

Question

Write an algorithm for converting infix expression to postfix expression. Convert a given infix expression: A + (B * C - (D / E - F) * G) * H into postfix expression showing stack status after every step in tabular form.

Solution

Algorithm for Infix to Postfix Conversion:

Algorithm INFIX_TO_POSTFIX(expr):
1. Create an empty operator stack S and output string post.
2. For each symbol ch in expr from left to right:
   a) If ch is an operand: append ch to post.
   b) Else if ch == '(': PUSH(S, ch).
   c) Else if ch == ')':
          While PEEK(S) != '(': append POP(S) to post.
          POP(S)   // discard '('
   d) Else (operator ch):
          While !ISEMPTY(S) and PEEK(S) != '(' and
                (PREC(PEEK(S)) > PREC(ch) or
                 (PREC(PEEK(S)) == PREC(ch) and ch != '^')):
              append POP(S) to post.
          PUSH(S, ch).
3. While !ISEMPTY(S): append POP(S) to post.
4. Return post.

Tabular Trace for A + (B * C - (D / E - F) * G) * H:

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 E /Pop /, push -
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:

Converted postfix expression: A B C * D E / F - G * - H * + (ABC*DE/F-G*-H*+).

All past exam questions for Data Structure and Algorithms