GATE CS 2002 Q2.19 — Parsing (LL, LR)

To evaluate an arithmetic expression without embedded function calls, one stack is enough. Here is why:

1. Postfix Evaluation: If the expression is represented in postfix (Reverse Polish) notation, it can be evaluated in a single pass using exactly one operand stack. As we scan the expression from left to right:
   • If we encounter an operand, we push it onto the stack.
   • If we encounter an operator, we pop the required number of operands from the stack, apply the operator, and push the result back onto the stack.
2. Infix to Postfix Conversion: If the expression is initially in infix notation, we can convert it to postfix using a single operator stack, and then evaluate the resulting postfix expression using a single operand stack. Since these steps can be done sequentially, we never need more than one stack at any given time.
3. Automata Theory Perspective: The language of well-formed arithmetic expressions is a Context-Free Language (CFL). A Pushdown Automaton (PDA), which possesses exactly one stack, is capable of parsing and processing any CFL.

Therefore, one stack is sufficient to evaluate the expression.