Practice: Balanced Brackets
Every opener has a closer.
Code editors check that every bracket is closed, in the right order. Round brackets, square brackets, and curly braces. Pause. Why would a stack be perfect for this?

- Every bracket closed
- In the right order
- Why a stack?
Matching with a stack
Each opening bracket is pushed onto the stack. When a closing bracket arrives, the top of the stack must be its partner. If it isn't, or the stack is empty, the brackets are broken. At the end, the stack must be empty, or something was never closed. Run it. The first two are balanced. The last two are not.
def balanced(text):
pairs = {")": "(", "]": "[", "}": "{"}
stack = []
for ch in text:
if ch in "([{":
stack.append(ch)
elif ch in pairs:
if not stack or stack.pop() != pairs[ch]:
return False
return not stack
for t in ["(a[b]{c})", "{[()()]}", "([)]", "(("]:
print(t, balanced(t))(a[b]{c}) True
{[()()]} True
([)] False
(( FalseStacks are everywhere
Whenever the most recent thing must be dealt with first, think stack. Matching brackets, undo history, and evaluating maths expressions. Even Python itself uses a stack to keep track of which function is running, and where to return to. We'll see that soon, in recursion.
| key | value |
|---|---|
| Brackets | match the latest opener |
| Undo | reverse the latest change |
| Calculators | evaluate expressions |
| Function calls | the call stack |
Summary
Push the openers, and pop to check each closer. An empty stack at the end means balanced. Next, queues. First in, first out.
Key takeaways- Push openers
- Pop on closers
- Empty at the end