To evaluate an expression without any embedded function calls:
20252002
To evaluate an expression without any embedded function calls:
- A.
One stack is enough
- B.
Two stacks are needed
- C.
As many stacks as the height of the expression tree are needed
- D.
A Turing machine is needed in the general case
Attempted by 400 students.
Show answer & explanation
Correct answer: A
Explanation:
Any expression can be converted into Postfix or Prefix form.
Prefix and postfix evaluation can be done using a single stack.
For example : Expression '10 2 8 * + 3 -' is given. PUSH 10 in the stack. PUSH 2 in the stack. PUSH 8 in the stack. When operator '*' occurs, POP 2 and 8 from the stack.
PUSH 2 * 8 = 16 in the stack. When operator '+' occurs, POP 16 and 10 from the stack. PUSH 10 * 16 = 26 in the stack. PUSH 3 in the stack.
When operator '-' occurs, POP 26 and 3 from the stack.
PUSH 26 - 3 = 23 in the stack. So, 23 is the answer obtained using single stack.
Thus, option (A) is correct.
A video solution is available for this question — log in and enroll to watch it.