Past exam question: 2072 Ashwin (Regular), Q2
Open in the Padhaiko appQuestion
What is a stack? Write an algorithm to convert infix expression into postfix expression using stack.
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 only at one end called top.
Algorithm INFIX_TO_POSTFIX(expr):
Algorithm INFIX_TO_POSTFIX(expr):
1. Initialize an empty operator stack S and empty output string post.
2. Scan 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 !ISEMPTY(S) and PEEK(S) != '(':
Append POP(S) to post.
POP(S) // discard '('
d) Else (ch is an operator +, -, *, /, ^):
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.Answer:
A stack is a LIFO linear structure (push/pop at top). The INFIX_TO_POSTFIX algorithm outputs operands directly, buffers ( and operators on the stack by precedence/associativity, and flushes until ( on each ) before draining remaining operators at the end.