Stacks and brackets

My favourite data structure is the stack. I like it because picking the right data structure can make a problem trivial to solve. Balancing brackets is a good example.

What's a stack?

A stack lets you put something on top and take it back off. The last thing you put in is the first thing you get out. In Python, a list can do this with append and pop.

Balancing brackets

Take ([{}]). Each closing bracket needs to match the most recently opened bracket. That sounds like a stack to me.

Put opening brackets on the stack. When we find a closing bracket, take the top one off and check that they match. If there's nothing to take off, or they don't match, we're done: the brackets aren't balanced. At the end, the stack needs to be empty too.

def balanced(text):
    stack = []
    pairs = {")": "(", "]": "[", "}": "{", ">": "<"}

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

    return not stack

balanced("<{[()]}>") is True. balanced("([)]") is False: the ) tries to close a [. Extra closing brackets and unclosed brackets also fail.

This checks (), [], {} and <>, and ignores other characters. It treats every bracket as a bracket, even inside a quoted string or when < means less than, so it's not a programming language parser.

We look at each character once, so that's O(n) time and up to O(n) space for the stack.