Valid Parentheses

The problem

Determine whether a string of brackets closes in the correct order. This solution assumes the problem’s input alphabet contains only brackets.

A solution

Push the expected closing bracket when opening a pair. Each closing bracket must match the top of the stack.

def is_valid(text):
    pairs = {"(": ")", "[": "]", "{": "}"}
    expected = []

    for char in text:
        if char in pairs:
            expected.append(pairs[char])
        elif not expected or expected.pop() != char:
            return False

    return not expected

assert is_valid("({[]})")
assert not is_valid("([)]")
assert not is_valid("(")

Notes

Thinking in terms of what should come next makes the invariant simple. The final empty-stack check matters: a prefix can be valid even when the whole input is incomplete.

Time is O(n). The stack uses O(n) space in the worst case.