Bracket matching

What is a stack?

A stack is a collection where you add and remove from the same end, called the top. Push means add an item; pop means remove the top item; peek means read the top without removing it. The last item added is the first removed. This order is called last in, first out, or LIFO.

Example: Push 4, then 8, then 15. The next pop returns 15. After that, the top is 8.

Helpful before this chapter

If these ideas are new, begin with:

Arrays and dynamic arrays

Understand the idea

Open brackets are pending obligations. A close bracket must match the most recent unmatched opener; checking counts alone ignores nesting. Reject a closer immediately if the stack is empty: there is no opener to match it. After the scan, pending openers also make the expression invalid. These checks cover both premature closes and incomplete nesting.

Work through an example

'([)]' has balanced counts but is invalid: ')' arrives while '[' is on top. '([])' closes the inner pair first.

Time and space complexity

O(n) time/O(n) worst-case space.

Why it works

The stack contains unmatched openers in encounter order.

Common mistakes

A matching count does not prove nesting.
Require an empty stack at the end.

Chapter lab · Python implementation

A stack preserves last-in-first-out order. The lab resolves next-warmer-day queries using a monotonic stack of unresolved indices. Each index is pushed once and popped at most once. This explains why a nested while loop can still do linear total work.

This shared lab connects the chapter's topics. Follow the current lesson's worked example first, then trace the complete implementation. Additional algorithms described in topic exercises are variations you can implement independently.

def valid_brackets(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
        else:
            raise ValueError('brackets only')
    return not stack

def warmer(temperatures):
    answer=[0]*len(temperatures)
    stack=[]
    for i,temp in enumerate(temperatures):
        while stack and temperatures[stack[-1]]<temp:
            j=stack.pop()
            answer[j]=i-j
        stack.append(i)
    return answer

Run and test the lab

Copy the implementation and these assertions into a Python 3 file and run it. An assertion failure means the actual result differs from the expectation. Add the current topic's exercise and boundary tests to deepen your understanding.

assert valid_brackets('([])')
assert not valid_brackets('([)]')
assert valid_brackets('')
assert warmer([73,71,74])==[2,1,0]
assert warmer([5,5,5])==[0,0,0]

CHECK YOUR UNDERSTANDING