Lecture 9

Balanced brackets

An opening bracket waits for its closing partner. Use a stack to find out whether every pair fits.

Optional practice. Exams are based on lecture notes.

Opening bracketPush it onto the stack.

Closing bracketPop the top and compare their types.

End of inputThe stack must be empty.

Explore

Follow the stack

Other characters do not change the stack.

Up to 40 characters. An empty input is allowed.

Try an example
Step 0

Loaded input

The outlined character is the current one. Green pairs have matched. Red marks a failure.

Ready

An empty stack

Python

Lecture algorithm
def is_matched(expr):
    lefty = "([{"
    righty = ")]}"
    s = ListStack()
    for c in expr:
        if c in lefty:
            s.push(c)
        elif c in righty:
            if s.is_empty():
                return False
            if righty.index(c) != lefty.index(s.pop()):
                return False
    return s.is_empty()

ListStack is the class defined in the lecture. The positions in lefty and righty identify matching types.

Stack

0 brackets

The newest opening bracket is at the top.

The stack is empty.

    Current comparison

    No pair is being compared.

    Matched pairs

    No pairs yet.

    Returned value

    Not returned yet

    Each step processes one character or checks the final stack. The page traces the displayed algorithm and does not run arbitrary Python.

    Look closely

    The nearest opening bracket comes first

    After reading ({[, the top is [. The next closing bracket must be ]. A later ) cannot close ( while [ is still waiting.

    A failure can happen in three ways. A closing bracket arrives too early, the types differ, or opening brackets remain at the end.

    Try

    Make a prediction

    The algorithm has read ({[. Which closing bracket can it accept next?

    Choose one bracket