Past exam question: 2066 Jestha (Back), Q1
Open in the Padhaiko appQuestion
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:
| Symbol | Stack (Bottom Top) | Postfix Output | Action |
|---|---|---|---|
A | (empty) | A | Append A |
+ | + | A | Push + |
( | + ( | A | Push ( |
B | + ( | A B | Append B |
* | + ( * | A B | Push * |
C | + ( * | A B C | Append C |
- | + ( - | A B C * | Pop *, push - |
( | + ( - ( | A B C * | Push ( |
D | + ( - ( | A B C * D | Append D |
/ | + ( - ( / | A B C * D | Push / |
E | + ( - ( / | A B C * D E | Append E |
- | + ( - ( - | A B C * D E / | Pop /, push - |
F | + ( - ( - | A B C * D E / F | Append F |
) | + ( - | A B C * D E / F - | Pop -, discard ( |
* | + ( - * | A B C * D E / F - | Push * |
G | + ( - * | A B C * D E / F - G | Append 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 * - H | Append 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*+).