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.

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("([)]"));
    }
}