Validating Nested Delimiters with Stacks

Hello! In the previous lesson, you kept an inclusive interval of possible indices while binary search narrowed it. This lesson also relies on a precise account of what remains unresolved, but the input is no longer sorted: it is a sequence of brackets. You’ll use a stack to remember opening brackets that still need closing, then implement a validator for nested (), [], and {}.

Why matching counts are not enough

A valid bracket string must meet three conditions: each closer has the right type of opener, pairs close in the right order, and no opener or closer is left without a partner. Both ()[] and ([{}]) are valid. The strings )( and ([)] are not—even though each contains equal numbers of opening and closing brackets of every type it uses. Counts lose the information about order.

Watch the first part of Greg Hogg’s Valid Parentheses - Leetcode 20 - Stacks (Python) for the rules and the choice of data structure.

When you read from left to right, an opener can remain unmatched while other pairs begin and end inside it. The next closer must match the most recent opener that has not yet been closed. That “most recent unfinished item first” rule is last-in, first-out (LIFO)—exactly what a stack provides.

In Python, a list makes a convenient stack. append adds an opener at the end; stack[-1] inspects that most recent opener; and pop removes it after a successful match. The important restriction is that a closer checks the top, not just any matching opener somewhere in the list.

Maintain the unfinished openers

Consider ([{}]). Here the stack is shown from oldest opener on the left to newest opener on the right:

This trace gives us a useful loop invariant: after processing a prefix of the string without finding an error, the stack contains exactly the opening brackets in that prefix that have not yet been matched, in their original order. Its top is the only opener the next closer may match.

Now examine ([)]. After ( and [ are saved, the next character is ). There is a ( in the stack, but [ is on top. Matching the deeper ( would leave the [ improperly nested, so the string is invalid immediately. Likewise, a closer encountered when the stack is empty has no preceding unmatched opener. Neither failure can be repaired by characters later in the string.

At the end, successful matches alone are not sufficient: the stack must also be empty. The string (( has caused no mismatch, but both openers remain unfinished.

Implement the validator

The function below assumes the input contains only the six bracket characters. A dictionary records the opening bracket required by each closer. Watch the rest of the video before studying the code; the video’s implementation uses the same stack principle, so compare its conditions with those here.

def valid_brackets(s):
    # Contract: s contains only (), [], and {} characters.
    matching_open = {')': '(', ']': '[', '}': '{'}
    stack = []

    for char in s:
        if char in "([{":
            stack.append(char)
        else:  # Under the input contract, char is a closing bracket.
            if not stack or stack[-1] != matching_open[char]:
                return False
            stack.pop()

    return not stack

The order of the closing-bracket checks matters. Python’s or stops evaluating as soon as not stack is true, so stack[-1] is never accessed on an empty list. A matching closer removes its opener; a mismatched closer returns False without pretending that the pair was completed.

Why does the final result work? By the invariant, any opener still in stack at the end lacks a closer. If the stack is empty and no closer failed along the way, every bracket belongs to a correctly ordered, correctly typed pair. The empty string is valid under this definition: it has no unmatched brackets.

Check the edges and adapt the input contract

These cases cover distinct ways a validator can fail, rather than just several versions of the same mismatch:

assert valid_brackets("") is True
assert valid_brackets("()[]{}") is True
assert valid_brackets("([{}])") is True

assert valid_brackets("([)]") is False  # Wrong nesting order
assert valid_brackets("(]") is False    # Wrong bracket type
assert valid_brackets(")(") is False    # Closer with an empty stack
assert valid_brackets("([]") is False   # Opener left at the end

The code scans each of the $n$ characters once. With three fixed bracket types, its dictionary has constant size; each list operation at the end of the stack takes constant time. Total time is $O(n)$. If the greatest number of simultaneously unmatched openers is $d$, the stack uses $O(d)$ auxiliary space, which is $O(n)$ in the worst case—for example, when the entire input consists of openers.

A related prompt may ask whether brackets are balanced inside an expression, such as total[2 * (a + b)]. In that case, ordinary characters do not affect the bracket stack. You can retain the function’s matching logic and skip non-bracket characters at the start of its loop:

for char in s:
    if char not in "()[]{}":
        continue
    # Then apply the same opener and closer logic as above.

Make that change only when the problem explicitly permits other characters. The original bracket-only function has a narrower contract; it does not silently accept arbitrary input. A real programming-language parser also needs rules for brackets inside strings and comments, which this simple character scan does not attempt to handle.

Key takeaways

A bracket validator needs more than counts: it must preserve the order of unmatched openers. Save each opener on a stack, require each closer to match the stack’s top, reject an empty-stack or type mismatch immediately, and accept only if the stack is empty at the end. This gives a one-pass $O(n)$-time solution with $O(n)$ worst-case auxiliary space.

This completes the module’s first pass through high-yield coding patterns. Next, the course turns to design fundamentals, beginning with Python classes as a way to give data and behavior clear responsibilities.