Check that every bracket is closed by the right type, in the right order. Push each opener, and match each closer against the top of the stack.
▼The problem
Given a string of ()[]{}, decide whether it is valid: every opener is closed by the same type of bracket, in the right order.
Example: {[()]}() is valid.
The solution
def is_valid(s):
pairs = {')': '(', ']': '[', '}': '{'}
stack = []
for ch in s:
if ch in pairs: # a closer
if not stack or stack.pop() != pairs[ch]:
return False
else:
stack.append(ch) # an opener
return not stackTranscript
Valid Parentheses. You get a string of round, square and curly brackets. It's valid if every opener is closed by the same type, in the right order.
Take this one: curly, square, round, then their closers in reverse, then one more round pair. Every bracket finds its partner, so it's valid.
Why not just count them? Round, square, close round, close square has one of each, so the counts match. But the round closer arrives while the square is still open. Counting can't see that.
The fix is a stack. Push every opener on top. When a closer arrives, it must match the opener on top, the most recent one still open. If it does, pop that opener off. If it doesn't, or the stack is empty, the string is invalid. At the end, nothing may be left on the stack.
In code, a small map pairs each closer with its opener. Loop over the characters. A closer pops the top and compares; any mismatch returns false. Openers are pushed. Finally, return whether the stack is empty.
Let's play the example. Curly, square and round drop in. The round closer meets round on top: clear. Square meets square: clear. Curly meets curly: clear. Then round drops in, and its closer clears it too. The stack is empty: valid.
Each bracket is pushed and popped at most once, so the time is order n. If every bracket is an opener, the stack holds them all: order n space.
Push the openers, match the closers, finish empty. That's Valid Parentheses.