How do you check whether the brackets in a string are balanced?
You use a stack. Every time you see an opening bracket you push it, and every time you see a closing bracket you check that the top of the stack is the matching opening bracket.
def is_valid(text):
pairs = {")": "(", "]": "[", "}": "{"}
stack = []
for char in text:
if char in "([{":
stack.append(char)
else:
if not stack or stack.pop() != pairs.get(char):
return False
return not stack
So how does it work? The stack holds the opening brackets that have been seen but not yet matched. When you meet an opening bracket you push it on top. When you meet a closing bracket you look at the top of the stack, and the top has to be the opening bracket that matches it. If it is then you pop it off and the pair is done. If it is not then the brackets are not balanced and you can stop straight away.
And why is a stack the right shape for this? Because of the order of the work. The most recent opening bracket is the first one that a closing bracket has to match, and that is exactly what a stack gives you. A queue would be wrong, because a queue gives you the oldest one first.
the text the stack after each step the result
----------- ------------------------- ----------
() empty good
(] ] is not on top bad
(] the top is ] bad
([)] the top is ] not ( bad
[] empty good
And there are two ways the answer can be bad. The first one is a closing bracket with nothing to match it, which is the check inside the loop. The second one is a closing bracket that matches the wrong opening bracket, which is the same check. And the third one is that the stack is not empty at the end, which is the last line.
And the complexity is O of n for the time, because every character is looked at once and every push and pop is constant, and O of n for the space in the worst case, when every bracket is an opening one.
So the rule to remember is this. A closing bracket has to match the top of the stack, and the stack must be empty at the end.
The next two questions in this topic look at the edge cases.