QUESTION 58 What will be the minimum size of stack required to evaluate the prefix...
Qualcomm technical mcq question, verified with a worked answer. Free to practise - no sign-up.
QUESTION 58
What will be the minimum size of stack required to evaluate the prefix expression given below?
^ 2 * % 13 5 4
Show answer & explanation
Answer: D. 3
Prefix expressions are evaluated right-to-left. Operands are pushed onto the stack, and when an operator is encountered, the required operands are popped, the operation is performed, and the result is pushed back. For this expression, the maximum stack depth reached during evaluation is 3, which occurs when we have multiple operands queued before operators consume them.
Step-by-step Derivation:
Evaluation of prefix expression '^ 2 * % 13 5 4' (right-to-left):
- Read '4' (operand): Push 4 → Stack: [4], depth = 1
- Read '5' (operand): Push 5 → Stack: [4, 5], depth = 2
- Read '13' (operand): Push 13 → Stack: [4, 5, 13], depth = 3
- Read '%' (operator): Pop 13, 5 → Compute 13 % 5 = 3 → Push 3 → Stack: [4, 3], depth = 2
- Read '*' (operator): Pop 3, 4 → Compute 3 * 4 = 12 → Push 12 → Stack: [12], depth = 1
- Read '2' (operand): Push 2 → Stack: [12, 2], depth = 2
- Read '^' (operator): Pop 2, 12 → Compute 12 ^ 2 = 144 → Push 144 → Stack: [144], depth = 1
Maximum stack depth required = 3 (reached at step 3)