Data Structures19 sections · 729 units
Open in Course

The Matching Problem

Nested structures

Consider the string "(()())". How do you verify the parentheses are balanced? You need to match each close with its corresponding open.

Here's the trick: each close matches the most recent unmatched open. "Most recent" means LIFO. That's a stack. Push each open parenthesis.

When you see a close, pop and check if it matches. If the stack is empty at the end and every close matched, the string is valid.