Stacks represent last-opened, first-closed structure. Closing tokens must match the latest unmatched opening token.
Before you start
You should know arrays, loops and basic complexity notation. Start with a small input you can trace by hand. State what each variable means and which invariant is maintained, then use that invariant to explain correctness before discussing performance or writing a more compact solution.
The practical goal is to reason through this situation: Push opening brackets and pop only when the closing type matches. Read the walkthrough first, then try the interview exercise before opening its answer. The important part is explaining the decision and its consequences, rather than remembering a definition alone.
Step-by-step walkthrough
Step 1: Track unmatched openers
Push each opening delimiter in encounter order.
Step 2: Match the most recent opener
A closing token must match the stack top.
Step 3: Verify final completion
An empty final stack is necessary after processing all tokens.
Worked scenario
Push opening brackets and pop only when the closing type matches.
For ‘([)]’, bracket counts balance but the closing parenthesis conflicts with the latest opener ‘[’. Reject at that position. For ‘([])’, the square pair closes first and the outer parentheses close next. This explains why order, not only frequency, defines nested correctness.
Common mistake
Counting bracket totals ignores incorrect nesting order.
Verify the behavior
Test premature closing, mismatched types, unfinished opening and valid nesting.
Interview exercise
Reject an invalid sequence.
Answer and reasoning
Reject a closing token with an empty or mismatched stack and require the stack to be empty at completion.
Continue learning
Compare the scenario with the Data Structures and Algorithms interview questions and test your understanding with the Data Structures and Algorithms MCQs. For terminology and implementation details, consult the reference material.