GATE CS 2004 Q5 — Arrays, Stacks and Queues

The correct option is B.

To check whether an arithmetic expression has balanced parentheses, we need to ensure that every opening parenthesis is closed by its corresponding closing parenthesis in the correct, nested order (Last-In, First-Out).

A stack is the most suitable data structure for this task because of its LIFO (Last-In-First-Out) property:

• Scan the expression from left to right:
• If an opening parenthesis (e.g., (, {, [) is encountered, we push it onto the stack.
• If a closing parenthesis (e.g., ), }, ]) is encountered:
  • If the stack is empty, the expression is unbalanced (no matching opening parenthesis).
  • Otherwise, we pop the top element from the stack. If the popped opening parenthesis does not match the current closing parenthesis, the expression is unbalanced.
• At the end of the expression: If the stack is empty, the parentheses are balanced; otherwise, there are unmatched opening parentheses, so it is unbalanced.

Other data structures like queues (FIFO), trees, or general lists do not naturally support this nested, symmetric matching behavior as efficiently as a stack, which accomplishes this in $O(n)$ time and $O(n)$ auxiliary space.