Balanced Parentheses Problem Explained Using Stacks — Step by Step

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
    }
}

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);
        }
    }
}

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

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