Past exam question: 2065 Shrawan (Regular / Back), Q2
Open in the Padhaiko appQuestion
Define stack as an ADT? Convert the following infix expression onto prefix and post fix. a) A + [B + C + (D + E) * F] / G b) ((a + b) * c - (d - e) \$ (f + g)
Solution
Stack as an ADT:
- Value Definition: Ordered LIFO sequence where insertions and removals occur only at
top. - Operations:
createStack(),isEmpty(S),isFull(S),push(S, x),pop(S),peek(S).
Part a) A + [B + C + (D + E) * F] / G: Treat [ and ] as grouping brackets identical to ( and ):
(D + E)DE+/+DE(D + E) * FDE+F*/*+DEFB + C + (D + E) * FBC+DE+F*+/++BC*+DEF- Divide by
GBC+DE+F*+G///++BC*+DEFG - Add to
A- Postfix:
A B C + D E + F * + G / + - Prefix:
+ A / + + B C * + D E F G
- Postfix:
Part b) ((a + b) * c - (d - e)) \$ (f + g):
(a + b) * cab+c*/*+abc(d - e)de-/-de((a + b) * c - (d - e))ab+c*de--/-*+abc-de(f + g)fg+/+fg- Apply
\$:- Postfix:
a b + c * d e - - f g + \$ - Prefix:
\$ - * + a b c - d e + f g
- Postfix:
Answer:
- Stack ADT: LIFO sequence supporting
push,pop,peek,isEmpty,isFull. - a) Postfix:
ABC+DE+F*+G/+, Prefix:+A/++BC*+DEFG. - b) (with missing
)closed before\$) Postfix:ab+c*de--fg+\$, Prefix:\$-*+abc-de+fg.