A compiler component must check that the brackets in an arithmetic expression are balanced: every opening bracket must be matched by a closing bracket of the same kind, and an inner pair must always close before the outer pair that contains it. Which data structure is the natural choice for this check, and why?
A stack, because each closing bracket must match the most recently seen opening bracket that is still unmatched, which is exactly the last in, first out discipline a stack provides
A queue, because the brackets must be matched in exactly the order in which they first appear in the expression, which is a first in, first out discipline
A sorted array, because keeping the brackets in sorted order allows each closing bracket to find its partner using binary search
A binary search tree, because the nesting depth of each bracket can be stored as a key for fast lookup of the matching pair
The verified answer and full solution are one login away
Every answer here is machine verified, with a step-by-step solution that teaches the method. Your login also unlocks a 7-question mock preview in the real exam interface.
Log in to see the answerMore data structures questions