Scan tokens; push every opener. A closer requires a nonempty stack with top=matching_open(closer), then pops it. The input is balanced exactly when the stack is empty at the end.
Recognition signals
The input contains paired parentheses, tags, or begin/end tokens.
Nesting must be proper and crossing pairs are forbidden.
Unmatched positions or maximum nesting depth are requested.
The most recent opener determines whether the current closer is legal.
False friends
Signal
Why it is different
One delimiter type and count only
A balance counter may suffice, but multiple types require a stack to reject crossings.
Can delete arbitrarily to become valid
Minimum deletion or all repair plans need more than one validation pass.
Core invariant
After a prefix, the stack contains exactly its unmatched openers in occurrence order; the top is the only opener the next closer may legally match.
State, transition, and processing order
Item
Definition
State
Stack of opener symbols or indexes, closer-to-opener map, and optional maximum depth or error position.
Transition
Push an opener; for a closer, verify nonempty and matching type, then pop, otherwise fail or record repair information.
Frontier / order
All unfinished nesting levels, with the newest opener at top and therefore due to close first.
Python skeleton
def delimiters_balanced(text):
match = {')': '(', ']': '[', '}': '{'}
opening = set(match.values())
stack = []
for ch in text:
if ch in opening:
stack.append(ch)
elif ch in match:
if not stack or stack[-1] != match[ch]:
return False
stack.pop()
return not stack
Correctness sketch
Every opener is pushed and removed only by its correct closer, so all produced pair types match.
LIFO enforces inner-before-outer closure and rules out crossing pairs.
A mismatching closer cannot legally skip the top; an empty final stack means no opener remains unmatched.
Complexity
Time
Space
Parameters
O(n)
O(d)
n is input length and d maximum nesting depth, with d up to n.
Edge cases
The empty string is usually valid.
A leading closer fails immediately.
Openers left at end make the input incomplete.
The protocol must decide whether ordinary nondelimiter characters are ignored, rejected, or token content.
Error patterns
Pattern
Why it fails / fix
Counting opens and closes only
([)] has balanced counts but invalid nesting.
Reading stack[-1] before checking emptiness
An extra closer causes an exception.
Skipping the final empty check
A prefix missing closers is incorrectly accepted.
Selection and exclusion rules
Use a stack for multiple types or when positions matter.
For one type and validation only, a counter may suffice.
For longest valid spans, store indexes rather than symbols.