PadhaikoAll subjects

Past exam question: 2075 Baisakh (Back), Q2

Data Structure and Algorithms · 10 marks

Open in the Padhaiko app

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

Question

Define stack. How to convert infix to postfix notation? Explain with example. Evaluate the postfix expression AB+C*DEFG-*+ with status of stack where A = 2, B = 3, C = 10, D = 5, E = 2, F = 4 and G = 6.

Solution

Definition of Stack and Infix-to-Postfix Conversion Rule: A stack is a LIFO linear ADT (push and pop at top). To convert infix to postfix:

  1. Scan infix left to right. Output operands immediately.
  2. Push ( onto the stack.
  3. On operator op, pop and output stack operators with greater or equal precedence (except right-associative ^, which pops only strictly greater precedence), then push op.
  4. On ), pop and output until ( is popped and discarded.
  5. At end of expression, pop remaining stack operators.

Example: A + B * C: output A, push +, output B, push * (), output C, pop * then + A B C * +.

Postfix Evaluation Trace (A=2, B=3, C=10, D=5, E=2, F=4, G=6): Literal sequence: 2 3 + 10 * 5 2 4 6 - * +

TokenActionStack (Bottom Top)
2Push 2[2]
3Push 3[2, 3]
+[5]
10Push 10[5, 10]
*[50]
5Push 5[50, 5]
2Push 2[50, 5, 2]
4Push 4[50, 5, 2, 4]
6Push 6[50, 5, 2, 4, 6]
-[50, 5, 2, -2]
*[50, 5, -4]
+[50, 1]

With a missing trailing + (AB+C*DEFG-*++), popping 1 and 50 gives .

Answer:

All past exam questions for Data Structure and Algorithms