Balanced Parentheses Checking
What You'll Learn
You'll learn how to use a stack to verify that parentheses (), brackets [], and braces {} are properly matched and nested in expressions.
The Problem
When you write code or mathematical expressions, every opening symbol must have a corresponding closing symbol in the correct order. For example:
(a + b)✓ Valid{[()]}✓ Valid((a + b)✗ Missing closing parenthesis{[}]✗ Wrong nesting order
Why Stacks Are Perfect for This
Think of a stack like a stack of trays in a cafeteria—last one in, first one out. When checking parentheses:
- Push opening symbols (
(,[,{) onto the stack as you encounter them - When you see a closing symbol (
),],}):- Pop from the stack
- Check if it matches the type (parenthesis with parenthesis, bracket with bracket, etc.)
- If it doesn't match or the stack is empty, the expression is invalid
- After scanning everything, the stack should be empty
The Algorithm Flow
For the expression {[()]}:
- See
{→ push it - See
[→ push it - See
(→ push it - See
)→ pop(, they match ✓ - See
]→ pop[, they match ✓ - See
}→ pop{, they match ✓ - Stack is empty → Valid!
For the invalid expression {[}]:
- Push
{, push[ - See
}→ pop[, but[doesn't match}✗ Invalid!
Key Takeaway: A stack naturally tracks opening symbols in reverse order of their appearance, making it the ideal data structure for checking if parentheses, brackets, and braces are balanced and properly nested.