PadhaikoAll subjects

Past exam question: 2076 Baisakh (Back), Q2

Data Structure and Algorithms · 5 marks

Open in the Padhaiko app

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

Question

Define stack. Evaluate the postfix expression A*BC-DE*F/+G* with status of stack where A=2, B=3, C=10, D=5, E=2, F=4 and G=6.

Solution

Definition of Stack: A stack is a linear Abstract Data Type (ADT) following the Last-In, First-Out (LIFO) rule, where all insertions (push) and deletions (pop) occur at a single end called top.

Postfix Evaluation Trace for AB*C-DE*F/+G* (A=2, B=3, C=10, D=5, E=2, F=4, G=6): Substituting values: 2 3 * 10 - 5 2 * 4 / + 6 *

SymbolValue / OperationStack (Bottom Top)
APush 2[2]
BPush 3[2, 3]
*Pop 3, 2 [6]
CPush 10[6, 10]
-Pop 10, 6 [-4]
DPush 5[-4, 5]
EPush 2[-4, 5, 2]
*Pop 2, 5 [-4, 10]
FPush 4[-4, 10, 4]
/Pop 4, 10 [-4, 2.5]
+Pop 2.5, -4 [-1.5]
GPush 6[-1.5, 6]
*Pop 6, -1.5 [-9]

(Note: Under C integer division , the result would be .)

Answer:

Under the corrected postfix expression AB*C-DE*F/+G*, the final evaluated value is (or under integer division). Note that the literal printed expression A*BC-DE*F/+G* underflows at the first *.

All past exam questions for Data Structure and Algorithms