Past exam question: 2077 Chaitra (Regular), Q2
Open in the Padhaiko appQuestion
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))):
| Symbol | Stack (Bottom Top) | Postfix Output | Action |
|---|---|---|---|
( | ( | (empty) | Push ( |
A | ( | A | Append A |
* | ( * | A | Push * |
B | ( * | A B | Append B |
* | ( * | A B * | Pop * (equal prec), push * |
( | ( * ( | A B * | Push ( |
( | ( * ( ( | A B * | Push ( |
( | ( * ( ( ( | A B * | Push ( |
C | ( * ( ( ( | A B * C | Append C |
^ | ( * ( ( ( ^ | A B * C | Push ^ |
X | ( * ( ( ( ^ | A B * C X | Append X |
+ | ( * ( ( ( + | A B * C X ^ | Pop ^, push + |
D | ( * ( ( ( + | A B * C X ^ D | Append D |
^ | ( * ( ( ( + ^ | A B * C X ^ D | Push ^ |
Y | ( * ( ( ( + ^ | A B * C X ^ D Y | Append Y |
) | ( * ( ( | A B * C X ^ D Y ^ + | Pop ^, +, discard ( |
+ | ( * ( ( + | A B * C X ^ D Y ^ + | Push + |
E | ( * ( ( + | A B * C X ^ D Y ^ + E | Append E |
/ | ( * ( ( + / | A B * C X ^ D Y ^ + E | Push / |
Z | ( * ( ( + / | A B * C X ^ D Y ^ + E Z | Append 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 / + F | Append 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**).