Question

The best data structure to check whether an arithmetic expression has balanced parenthesis is a

• A. stack
• B. list
• C. queue
• D. tree

Answer 1

The correct option is A stack

The stack is a data structure in which each push (insert) or pop (delete) operation takes constant $\theta \left(1\right)$ time. The best data structure to check whether an arithmetic expression has a balanced parenthesis.

Step 1: Start with empty stack of currently open parenthesis
Step 2: Process each char of an expression string
Step 3: If it is open, push it on the stack
Step 4: If it is closed, check it against the top of stack element
Step 4.1: If stack empty or not a matching parenthesis then not balanced and return false
step 4.2: Otherwise it matches. pop the open parenthesis then go to step 2
Step 5: If stack is empty at the end, return true
Step 6: If not empty then some parenthesis is unmatched, return false