Balanced Brackets (Stack Match)

Implement is_balanced(s) where s is a non-empty string made only of the six bracket characters ()[]{}. Return whether every bracket is matched: each closer closes the most recently opened unclosed bracket, and nothing is left open at the end.

The stack is the whole mechanic. Push every opener. On a closer, the stack must be non-empty and its top must be the matching opener, which you pop; a mismatched top or an empty stack means the string is unbalanced on the spot. When the loop ends, an empty stack means balanced and anything left on it means an opener never got closed. The tempting shortcut is a counter per bracket type, and it is exactly wrong: counters know how many of each bracket are open but not in what order they were opened, so they happily accept ([)], where the counts balance but the ) arrives while [ is the innermost open bracket.

Example: is_balanced("{[()]}") returns true: each closer meets its own opener on top of the stack, and the stack drains to empty. is_balanced("([)]") returns false: when ) arrives the stack holds (, [ with [ on top, and ) does not match [.

Input format: each test in tests/*.in is laid out as:

• Line 1: the bracket string passed to is_balanced.

Test 04.in reads:

(()

This is ((), which opens twice but closes only once, so the answer is no.

Where you'll use it:

• 20. Valid Parentheses
• 1249. Minimum Remove to Make Valid Parentheses
• 394. Decode String
• 856. Score of Parentheses