Balanced Parentheses

Problem Statement

You're given a single line made up only of the six bracket characters ( ) [ ] { }, possibly none at all. Decide whether the brackets are "balanced": every opening bracket must be closed by the same type of bracket, and closing brackets must appear in the correct order relative to how their matching opening brackets were nested. Print true if the line satisfies both conditions, and false otherwise.

Input Format

The input is exactly one line containing zero or more of the characters ( ) [ ] { }, with no spaces or any other characters mixed in. The line can be empty.

Output Format

Print exactly one line containing the word true or the word false, in lowercase with no surrounding quotes or extra text. Print true if the brackets are properly matched and nested, and false if any bracket is left unclosed, closed by the wrong type, or closed out of order.

Example Walkthrough

Take the third sample, {[()]}. We scan left to right, keeping a stack of opening brackets that are still waiting to be closed. At index 0 we see {, an opening bracket, so we push it — the stack is now {. At index 1 we see [, also opening, so we push it too — the stack is {, [. At index 2 we see ( and push it as well — the stack is {, [, (. At index 3 we hit our first closing bracket, ). It must match whatever is on top of the stack, which is ( — it does, so we pop it, leaving the stack as {, [. At index 4 we see ], which must match the new top of the stack, [ — it does, so we pop it, leaving just {. At index 5 we see the final character, }, which must match the last remaining stack entry, { — it does, so we pop it and the stack is now empty. We've reached the end of the string with every opening bracket successfully matched and the stack empty, so the brackets are properly balanced and we print true.

Approach

The key insight is that the most recently opened, not-yet-closed bracket is always the one that the next closing bracket has to match — that "last opened, first closed" behavior is exactly what a stack gives you. Scan the string once from left to right. Whenever you see an opening bracket ((, [, or {), push it onto the stack. Whenever you see a closing bracket, it needs a partner: if the stack is empty at that point, there's nothing for it to close, so the string is immediately unbalanced. Otherwise, pop the top of the stack and check whether it's the opening bracket that matches the closing one you just saw (for example, ) must match a popped (, not a popped [ or {). If it doesn't match, the string is unbalanced right there and you can stop early.

If you make it through the entire string without hitting either of those failure conditions, there's one more thing to check before declaring the string balanced: the stack must be empty. If any opening brackets are still sitting on the stack after the scan finishes, it means they were never closed at all, so the string is still unbalanced even though every closing bracket that did appear matched correctly.

A convenient way to check "does this closing bracket match that opening bracket" is a small mapping from each closing character to the opening character it pairs with (or the reverse), so the comparison is a single dictionary lookup rather than a chain of if/elif statements for each of the three bracket types.

Common Mistakes

• Forgetting to check that the stack is empty at the end. A string like ((()) matches every closing bracket correctly as it's scanned — no mismatch is ever detected — but it still has one unclosed ( left over. If your code only reports false when it detects a mismatch during the scan and never checks the stack's final state, this case slips through and gets wrongly reported as true.
• Popping from the stack without first checking if it's empty. If a closing bracket like ) shows up before any opening bracket has been pushed, trying to pop or peek at an empty stack should immediately mean the string is unbalanced. Skipping that check causes a crash on inputs like ) instead of a clean false.
• Matching brackets by type but not by nesting order. Some incorrect approaches just count how many of each bracket type appear and check that the counts are equal, without paying attention to the order they show up in. That passes ()[]{} but wrongly accepts something like ([)], where the counts of each bracket type match but the ) incorrectly closes before the [ that opened after the ( does.