PadhaikoAll subjects

Past exam question: 2064 Jestha, Q1

Data Structure and Algorithms · 8 marks

Open in the Padhaiko app

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

Question

Define stack as an ADT. Write an algorithm for evaluating postfix expression. Evaluate a given postfix expression: 4 6 4 + * 8 / 4 - in tabular form showing stack after every step.

Solution

Stack as an Abstract Data Type (ADT):

Algorithm for Postfix Evaluation:

Algorithm EVAL_POSTFIX(expr):
1. Initialize empty operand stack S
2. For each token tok in expr from left to right:
       If tok is an operand:
           PUSH(S, numeric_value(tok))
       Else (tok is a binary operator op):
           op2 = POP(S)
           op1 = POP(S)
           res = APPLY(op1, op, op2)
           PUSH(S, res)
3. Return POP(S)

Tabular Stack Trace for 4 6 4 + * 8 / 4 -:

TokenActionOperand Stack (Bottom Top)
4Push 4[4]
6Push 6[4, 6]
4Push 4[4, 6, 4]
+Pop 4, 6 [4, 10]
*Pop 10, 4 [40]
8Push 8[40, 8]
/Pop 8, 40 [5]
4Push 4[5, 4]
-Pop 4, 5 [1]
Answer:

Final evaluated value of 4 6 4 + * 8 / 4 - is .

All past exam questions for Data Structure and Algorithms