PadhaikoAll subjects

Past exam question: 2072 Ashwin (Regular), Q2

Data Structure and Algorithms · 5 marks

Open in the Padhaiko app

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

Question

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.

All past exam questions for Data Structure and Algorithms