Balanced Parentheses — Why Counters Fail on ([)] Patterns

Every compiler, code editor, and browser in the world checks whether your brackets match up before it does anything else. When VS Code underlines a missing closing brace in red, or when Java throws a compilation error about unexpected tokens, it's running a version of the balanced parentheses check under the hood. This is not a toy problem — it's the gatekeeper that runs before your code ever executes.

The problem itself is simple to state: given a string of brackets like '({[]})' or '([)]', decide whether every opening bracket has a matching closing bracket in the right order. The tricky part is 'in the right order' — because '([)]' has the same number of openers and closers, yet it's wrong. Order matters, and that's exactly what a stack was designed to track.

By the end of this article you'll understand what a stack is and why it's the perfect tool here, you'll be able to write a complete Java solution from memory, you'll know the two mistakes that trip up nearly every beginner, and you'll be ready to answer the three versions of this question that interviewers love to ask.

Why Simple Counters Fail on ([)] Patterns

The balanced parentheses problem asks whether every opening bracket in a string has a matching closing bracket of the same type in the correct order. The core mechanic is not just counting — it's matching pairs: '(' with ')', '[' with ']', '{' with '}'. A string like "([)]" has equal counts of each bracket type but is not balanced because the order is wrong.

To solve it correctly, you need a stack. Push each opening bracket onto the stack; when you see a closing bracket, pop the top of the stack and check that it matches. This gives O(n) time and O(n) space in the worst case. The key property: the most recent unmatched opening bracket must match the current closing bracket — that's the LIFO constraint that counters miss.

Use this problem to teach stack fundamentals, but its real value is in validating structured data: JSON/XML parsers, code linters, and expression evaluators all rely on this matching logic. Getting it wrong means silent data corruption or security holes in parsers.

How Balanced Parentheses Works — Step by Step

The stack-based algorithm processes the string character by character:

1. Create an empty stack. Define matching pairs: ')' matches '(', ']' matches '[', '}' matches '{'.
2. For each character c in the string:
3. a. If c is an opening bracket ('(', '[', '{'), push it onto the stack.
4. b. If c is a closing bracket, check if the stack is empty. If empty, return False (no matching open).
5. c. Otherwise, pop the top of stack and verify it is the correct opening bracket for c. If not, return False.
6. After processing all characters, return True if the stack is empty (all opens were matched), False otherwise (unmatched opens remain).

For '()[]{}': push '(', pop-match ')' OK; push '[', pop-match ']' OK; push '{', pop-match '}' OK. Stack empty → True. For '([)]': push '(', push '['. See ')': pop '[', but '[' != '(' (wrong pair) → False. For '((': push '(', push '('. End: stack non-empty → False.

Worked Example — Tracing Nested Brackets

Check '{[()]}': step-by-step stack trace. 1. '{': push. Stack: ['{']. 2. '[': push. Stack: ['{','[']. 3. '(': push. Stack: ['{','[','(']. 4. ')': closing. Pop '(' — matches ')'. Stack: ['{','[']. 5. ']': closing. Pop '[' — matches ']'. Stack: ['{']. 6. '}': closing. Pop '{' — matches '}'. Stack: []. 7. Stack empty → balanced = True.

Check '({[}])': 1. push '(', push '{', push '['. 2. See '}': pop '[' — '[' does not match '}' → return False immediately.

Time complexity: O(n) — each character is processed once, push/pop are O(1). Space: O(n) for the stack in the worst case (all opening brackets).

How Balanced Parentheses Works — Algorithm

Use a stack to check if opening brackets are matched and closed in the correct order.

Algorithm: 1. Create an empty stack and a matching map: ')':'(', '}':'{', ']':'['. 2. For each character c in the string: a. If c is an opening bracket ('(', '{', '['): push c. b. If c is a closing bracket: if stack is empty or stack.top != matching[c]: return False. Else pop. 3. Return True only if stack is empty at the end.

Worked example — '({[]})': '(': push. stack=['('] '{': push. stack=['(','{'] '[': push. stack=['(', '{', '['] ']': top='[', matches. pop. stack=['(','{'] '}': top='{', matches. pop. stack=['('] ')': top='(', matches. pop. stack=[] Stack empty. True.

Worked example — '([)]' (wrong order): '(': push. '[': push. ')': top='[', does NOT match '('. Return False.

What Is a Stack and Why Does It Fit This Problem Perfectly?

A stack is a collection with one rule: the last thing you put in is the first thing you get out. Programmers call this LIFO — Last In, First Out. Think of a stack of plates at a buffet. You add a clean plate to the top, and when someone takes a plate, they always grab from the top. Nobody digs from the bottom.

A stack supports three core operations. Push adds an item to the top. Pop removes and returns the item from the top. Peek looks at the top item without removing it. That's it. Simple, but powerful.

Now think about why this fits bracket matching perfectly. When you see an opening bracket like '(' or '{' or '[', you don't know yet what will close it — so you push it onto the stack and move on. When you later see a closing bracket like ')' or '}' or ']', the most recently opened bracket — sitting right on top of the stack — is the one that should match it. If it does match, pop it off and keep going. If it doesn't match, or the stack is empty when you expected something there, the string is unbalanced.

The stack's LIFO nature mirrors the natural nesting of brackets. The most recently opened bracket must be the first one closed. That's not a coincidence — stacks exist precisely to handle this kind of nested, ordered structure.

package io.thecodeforge;

import java.util.Stack;

public class StackDemo {
    public static void main(String[] args) {

        // Java's built-in Stack class — we'll use this throughout the article
        Stack<Character> bracketStack = new Stack<>();

        // PUSH: add items to the top of the stack
        bracketStack.push('(');  // stack is now: ['(']
        bracketStack.push('[');  // stack is now: ['(', '[']
        bracketStack.push('{');  // stack is now: ['(', '[', '{']

        System.out.println("Stack after pushing three brackets: " + bracketStack);
        System.out.println("Top of stack (peek): " + bracketStack.peek()); // looks without removing

        // POP: remove and return the top item
        char topBracket = bracketStack.pop(); // removes '{' — the last thing we pushed
        System.out.println("Popped: " + topBracket);  // Output: {
        System.out.println("Stack after one pop: " + bracketStack); // ['(', '[']

        // isEmpty: crucial check before popping to avoid EmptyStackException
        System.out.println("Is stack empty? " + bracketStack.isEmpty()); // false
    }
}

The Algorithm: Walking Through the Logic Step by Step

Here's the core insight stated plainly: scan the string character by character. If the character is an opening bracket ('(', '[', or '{'), push it onto the stack. If it's a closing bracket (')', ']', or '}'), check whether the top of the stack holds the matching opener. If yes, pop and continue. If no — or if the stack is empty — the string is unbalanced, stop and return false.

When you finish scanning every character, check whether the stack is empty. An empty stack means every opener found its closer. A non-empty stack means there are openers left hanging with no closers — also unbalanced.

Let's trace through '({[]})' manually before writing any code. - Read '(' → push. Stack: ['('] - Read '{' → push. Stack: ['(', '{'] - Read '[' → push. Stack: ['(', '{', '['] - Read ']' → top is '[', which matches ']'. Pop. Stack: ['(', '{'] - Read '}' → top is '{', which matches '}'. Pop. Stack: ['('] - Read ')' → top is '(', which matches ')'. Pop. Stack: [] - End of string, stack is empty → BALANCED.

The mismatch detection happens in the middle of the string. That's what makes this algorithm elegant — it fails fast.

package io.thecodeforge;

import java.util.Stack;

public class BalancedParenthesesChecker {

    /**
     * Returns true if every opening bracket in the input string
     * has a correctly ordered, matching closing bracket.
     */
    public static boolean isBalanced(String inputString) {

        // Our stack holds opening brackets as we encounter them
        Stack<Character> openingBrackets = new Stack<>();

        // Walk through every character in the string one at a time
        for (int i = 0; i < inputString.length(); i++) {
            char currentChar = inputString.charAt(i);

            // --- CASE 1: It's an opening bracket → push and move on ---
            if (currentChar == '(' || currentChar == '[' || currentChar == '{') {
                openingBrackets.push(currentChar);

            // --- CASE 2: It's a closing bracket → check if it matches the top ---
            } else if (currentChar == ')' || currentChar == ']' || currentChar == '}') {

                // If the stack is empty, there's no opener to match this closer
                if (openingBrackets.isEmpty()) {
                    return false; // e.g. input starts with ')' — immediately wrong
                }

                // Look at the most recently pushed opener
                char mostRecentOpener = openingBrackets.pop();

                // Check whether the opener and closer are a valid pair
                boolean isMatchingPair =
                    (mostRecentOpener == '(' && currentChar == ')') ||
                    (mostRecentOpener == '[' && currentChar == ']') ||
                    (mostRecentOpener == '{' && currentChar == '}');

                if (!isMatchingPair) {
                    return false; // e.g. '([)]' — opener and closer don't match
                }

                // If they matched, the pop already removed the opener — carry on
            }
            // Any other character (letters, digits, spaces) is ignored
        }

        // After scanning everything, the stack must be empty.
        // If it's not, some openers never found their closers.
        return openingBrackets.isEmpty();
    }

    public static void main(String[] args) {
        String[] testCases = {
            "({[]})",   // all three bracket types, properly nested
            "(())",     // nested parentheses
            "([)]",     // wrong order — should fail
            "(((",      // openers with no closers — should fail
            ")))",      // closers with no openers — should fail
            "",         // empty string — technically balanced
            "{[()()]}", // complex valid nesting
            "({)}",     // looks close but order is wrong
        };

        for (String testCase : testCases) {
            String result = isBalanced(testCase) ? "BALANCED" : "UNBALANCED";
            // Padding the test case for clean console output
            System.out.printf("%-15s → %s%n",
                testCase.isEmpty() ? "(empty)" : testCase,
                result);
        }
    }
}

Common Gotchas That Trip Up Nearly Every Beginner

Even after understanding the algorithm, there are two specific bugs that show up in beginner solutions so frequently they're almost a rite of passage. Let's look at them directly, see the broken code, and then see the fix.

The first gotcha is forgetting the final isEmpty() check. Many beginners return true as soon as the loop finishes without errors, not realising that unmatched openers sitting in the stack also make the string invalid.

The second gotcha is popping without checking whether the stack is empty first. If your input string starts with a closing bracket, the stack is empty when you try to pop — and Java throws an EmptyStackException that crashes your program instead of gracefully returning false.

There's also a subtler third mistake: using == to compare String objects instead of char values. This only applies if you accidentally store brackets as Strings rather than chars, but it produces silent wrong answers — one of the nastiest kinds of bugs.

The runnable examples below show each broken scenario and the one-line fix for each.

package io.thecodeforge;

import java.util.Stack;

public class CommonMistakesDemo {

    // ❌ BUGGY VERSION 1: Missing the final isEmpty() check
    public static boolean buggyNoEmptyCheck(String input) {
        Stack<Character> stack = new Stack<>();
        for (char ch : input.toCharArray()) {
            if (ch == '(' || ch == '[' || ch == '{') {
                stack.push(ch);
            } else if (ch == ')' || ch == ']' || ch == '}') {
                if (stack.isEmpty()) return false;
                stack.pop(); // simplified — ignoring mismatch for this demo
            }
        }
        return true; // ❌ BUG: returns true even when '(((' is the input!
        // Fix: return stack.isEmpty();
    }

    // ❌ BUGGY VERSION 2: Popping without checking isEmpty first
    public static boolean buggyNoEmptyGuard(String input) {
        Stack<Character> stack = new Stack<>();
        for (char ch : input.toCharArray()) {
            if (ch == '(' || ch == '[' || ch == '{') {
                stack.push(ch);
            } else if (ch == ')' || ch == ']' || ch == '}') {
                char top = stack.pop(); // ❌ BUG: crashes with EmptyStackException if input starts with ')'
                // Fix: if (stack.isEmpty()) return false;  ← add this line BEFORE calling pop()
            }
        }
        return stack.isEmpty();
    }

    public static void main(String[] args) {
        // Demonstrate Bug 1: '(((' has 3 openers and no closers
        System.out.println("Bug 1 — '(((' should be UNBALANCED:");
        System.out.println("Buggy result: " + buggyNoEmptyCheck("((("));  // prints true — WRONG

        // Demonstrate Bug 2: input starts with ')'
        System.out.println("\nBug 2 — ')))' should be UNBALANCED:");
        try {
            System.out.println("Buggy result: " + buggyNoEmptyGuard(")))"));
        } catch (java.util.EmptyStackException e) {
            System.out.println("CRASHED with EmptyStackException! Fix: check isEmpty() before pop()");
        }

        // Show the correct version handles both gracefully
        System.out.println("\nCorrect isBalanced('((('):  " + BalancedParenthesesChecker.isBalanced("((("));
        System.out.println("Correct isBalanced('))):  " + BalancedParenthesesChecker.isBalanced(")))"));
    }
}

Interview Prep: Variations Interviewers Add to the Core Problem

Once you've nailed the base algorithm, interviewers don't stop there. They mutate the problem to see if you truly understand it or just memorised the solution. Here are the three most common extensions, with the key insight for each.

Variation 1: 'What if the string contains non-bracket characters like letters and numbers?' The answer is: ignore them. Your loop only acts when a character is a bracket. Everything else passes through. The code already handles this — add any character to a test string and verify it yourself.

Variation 2: 'Can you solve this without a stack?' Yes, but only if the input uses a single type of bracket — say, only parentheses. In that case you can use a counter: increment for '(', decrement for ')'. If counter goes negative, return false. If counter is zero at the end, return true. This breaks immediately with multiple bracket types because you lose ordering information.

Variation 3: 'What's the minimum number of bracket additions or removals to make a string balanced?' This is a harder follow-up (LeetCode 921). The trick is to track two counters — open (unmatched openers) and close (unmatched closers) — and return their sum at the end. Knowing this follow-up exists and describing the approach impresses interviewers even if you don't code it live.

The code below implements the counter shortcut for single-bracket strings, so you can see where it works — and understand exactly why it breaks with mixed brackets.

package io.thecodeforge;

public class SingleBracketCounterApproach {

    /**
     * Counter-only approach — ONLY works correctly for a single bracket type.
     * Fails silently for mixed brackets like '([)]'.
     * Use this ONLY when you're certain the input has one bracket type.
     */
    public static boolean isBalancedSingleType(String input) {
        int openCount = 0; // tracks how many unmatched '(' we've seen so far

        for (char ch : input.toCharArray()) {
            if (ch == '(') {
                openCount++;       // found an opener — remember it
            } else if (ch == ')') {
                openCount--;       // found a closer — cancel one opener
                if (openCount < 0) {
                    return false;  // more closers than openers so far — can't recover
                }
            }
        }

        // openCount == 0 means all openers were matched
        return openCount == 0;
    }

    public static void main(String[] args) {
        // Works correctly for parentheses-only strings
        System.out.println("'(())' → " + isBalancedSingleType("(())"));    // true
        System.out.println("'())(' → " + isBalancedSingleType("())(" ));    // false
        System.out.println("'(((' → " + isBalancedSingleType("((("));       // false

        // ❌ Where the counter approach SILENTLY gives wrong answers
        // '([)]' has 2 openers and 2 closers, but they're in wrong order
        // Counter sees: +1, +1(ignored [), -1, -1(ignored ]) = 0 → reports BALANCED
        // But it's actually UNBALANCED — use the stack solution for mixed brackets!
        System.out.println("\n'([)]' counter result (WRONG): " + isBalancedSingleType("([)]"));
        System.out.println("'([)]' stack result  (CORRECT): " + BalancedParenthesesChecker.isBalanced("([)]"));
    }
}

The Hidden Cost: Why Stack Space Matters in Production

Every senior engineer has seen it — a perfectly correct solution that melts the heap at scale. The stack-based approach is clean, but it burns O(n) memory. In embedded systems, real-time trading platforms, or high-frequency parsers, allocating a new stack per request is a luxury you cannot afford.

Here's the hard truth: each push is a heap allocation. In Java, that Stack<Character> object carries overhead. In C++, std::stack wraps a deque by default. The next time you're parsing a 10MB log file with deeply nested JSON, watch the GC pause.

But there is a cheaper path. Since we only track three bracket types, we can use an integer counter per type with a clever twist — treat the nesting depth as a state machine. This drops memory to O(1) and eliminates allocation entirely.

Before you dismiss this as premature optimization, ask yourself: is your parser running in a tight loop inside a kernel module? Does it handle untrusted input that could push 100,000 open brackets? That's when the simple counter betrays you, and the stack starves your system.

// io.thecodeforge
public class CounterParser {
    private int round, curly, square; // Track open brackets

    public boolean isBalanced(String input) {
        round = curly = square = 0;

        for (char c : input.toCharArray()) {
            switch (c) {
                case '(' -> round++;
                case ')' -> { if (--round < 0) return false; }
                case '{' -> curly++;
                case '}' -> { if (--curly < 0) return false; }
                case '[' -> square++;
                case ']' -> { if (--square < 0) return false; }
                default -> { /* skip non-brackets */ }
            }
        }

        return round == 0 && curly == 0 && square == 0;
    }
}

Production Walkthrough: What Goes Wrong on Real Input

Last quarter, a team pushed code that passed every unit test. On the first deployment, it crashed 57 times per hour. The culprit? They assumed balanced parentheses meant exactly one bracket per line. Real logs are messy.

Consider an API gateway that validates JSON configuration files. The naive stack approach fails in three common scenarios:

1. Non-bracket characters: Most tutorials skip this. Your input will contain 'a', '9', '#', spaces. The classic algorithm just ignores them — but what if a stray ')' slips through in user content? Should that fail?
2. Empty strings: Are they balanced? Yes, by definition. But your validator should return true, not throw NullPointerException because stack operations ran on a null string.
3. Unicode brackets: Python accepts fullwidth parentheses '（' and '）'. JavaScript does not. As a senior dev, you must decide: do you treat these as balanced brackets or invalid characters? The spec usually doesn't say.

Here's the fix: preprocess your input to strip non-bracket characters OR throw an explicit error when unexpected symbols appear. Add a whitelist for acceptable characters. And always — always — test with empty strings, strings of length 1, and strings that are 50KB of uninterrupted opening brackets.

// io.thecodeforge
import java.util.Set;
import java.util.Stack;

public class RobustValidator {
    private static final Set<Character> OPENERS = Set.of('(', '{', '[');
    private static final Set<Character> CLOSERS = Set.of(')', '}', ']');

    public boolean isBalanced(String raw) {
        if (raw == null || raw.isEmpty()) return true;

        Stack<Character> stack = new Stack<>();

        for (char c : raw.toCharArray()) {
            if (OPENERS.contains(c)) {
                stack.push(c);
            } else if (CLOSERS.contains(c)) {
                if (stack.isEmpty()) return false;
                char top = stack.pop();
                if (!matches(top, c)) return false;
            }
            // else: non-bracket - skip or throw? Uncomment line below to fail
            // else throw new IllegalArgumentException("Unexpected char: " + c);
        }

        return stack.isEmpty();
    }

    private boolean matches(char open, char close) {
        return (open == '(' && close == ')') ||
               (open == '{' && close == '}') ||
               (open == '[' && close == ']');
    }
}

Interview Trap: The One Test Case That Breaks Your Code

You've written the stack solution, passes the basic tests. The interviewer says: 'What about [{()}]?' You say balanced. 'What about ([)]?' You say not balanced. Good. Then they ask: 'What about [(])?'

That's the one. Your stack code will return false — correctly — because the ']' closes before the '('. But the follow-up is: 'How would you modify this to handle that pattern if the requirement changed?'

This is the rotating brackets variant. It measures depth but not strict ordering. The trick is to use a counter per bracket type and also track a separate stack of 'still open' bracket types. You can also encode depth as a bitmask: each bracket type gets a bit. When a bracket closes, check that the last opened bracket's type matches.

Senior engineers spot this trap because they recognize the problem translates to checking a context-free grammar. The stack is your parse stack. That's why the problem is never actually about parentheses — it's about whether you understand how to validate strict hierarchical structure.

Here's a quick implemention using a bitmask: assign bits 1, 2, 4 to round, curly, square. Each opening bracket sets its bit. Each closing bracket checks if the bit is set, then clears it. Balanced if final mask is 0. The problem? It fails on '([)]' — the mask can be zero while order is wrong. That's why we still need the stack.

But if you combine the bitmask with a secondary ordering check, you gain both memory efficiency and strict validation. That's a senior-level optimization.

// io.thecodeforge
public class OrderedMaskValidator {
    public boolean isStrictlyBalanced(String s) {
        int mask = 0;
        // Stack encodes order of opened bracket types
        int order = 0;
        for (char c : s.toCharArray()) {
            int bit = switch (c) {
                case '(' -> 1;
                case ')' -> -1;
                case '{' -> 2;
                case '}' -> -2;
                case '[' -> 4;
                case ']' -> -4;
                default -> 0;
            };
            if (bit > 0) {
                mask |= bit;
                order = (order << 3) | (Integer.numberOfTrailingZeros(bit));
            } else if (bit < 0) {
                int expectedBit = -bit;
                if ((mask & expectedBit) == 0) return false;
                // Check last opened matches this closer
                int lastOpenedType = order & 7;
                if (lastOpenedType != Integer.numberOfTrailingZeros(expectedBit)) 
                    return false;
                mask ^= expectedBit;
                order >>= 3;
            }
        }
        return mask == 0;
    }
}