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.
Loaded input
The outlined character is the current one. Green pairs have matched. Red marks a failure.
Ready
An empty stack
Python
Lecture algorithmdef 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 bracketsThe 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
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