Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

Parentheses Checker

Problem Statement

Write a Java program that uses a stack to check if a string of parentheses, including round '()', curly '{}', and square '[]' brackets, is balanced. The program should push opening brackets onto the stack and pop them when a matching closing bracket is found, returning true if the string is balanced and false otherwise. Test the implementation with various inputs, including valid and invalid parentheses strings, empty strings, and strings with non-bracket characters. You can visualize this as stacking open locks and checking if each closing lock perfectly matches and removes its corresponding open lock, ensuring no locks are left unmatched.

Input: A string containing parentheses and possibly other characters (e.g., "{[()]}", "((}", ""). Output: A boolean indicating if the parentheses are balanced (e.g., true for "{[()]}", false for "((}"). Constraints:

  • String length is between 0 and 10^5.
  • The string may contain '(', ')', '{', '}', '[', ']', and other ASCII characters.
  • The input may be empty or null. Example:
  • Input: "{[()]}"
  • Output: true
  • Explanation: Each opening bracket has a matching closing bracket in the correct order: { → }, [ → ], ( → ).
  • Input: "((}"
  • Output: false
  • Explanation: The second '(' has no matching ')', and '}' has no matching '{'.
  • Input: ""
  • Output: true
  • Explanation: An empty string is considered balanced.

Pseudocode

CLASS CharStack
    SET array to new character array of size 1000
    SET top to -1
    
    FUNCTION push(char)
        IF top equals array length - 1 THEN
            RETURN false (stack full)
        ENDIF
        INCREMENT top
        SET array[top] to char
        RETURN true
    ENDFUNCTION
    
    FUNCTION pop()
        IF top equals -1 THEN
            RETURN null (stack empty)
        ENDIF
        SET char to array[top]
        DECREMENT top
        RETURN char
    ENDFUNCTION
    
    FUNCTION isEmpty()
        RETURN top equals -1
    ENDFUNCTION
ENDCLASS

FUNCTION isBalanced(input)
    IF input is null THEN
        RETURN true
    ENDIF
    CREATE stack as new CharStack
    FOR each char in input
        IF char is '(', '{', or '[' THEN
            PUSH char to stack
        ELSE IF char is ')', '}', or ']' THEN
            IF stack is empty THEN
                RETURN false
            ENDIF
            SET popped to stack.pop()
            IF popped does not match char THEN
                RETURN false
            ENDIF
        ENDIF
    ENDFOR
    RETURN stack is empty
ENDFUNCTION

FUNCTION main()
    SET testStrings to array of strings including various cases
    FOR each string in testStrings
        PRINT input string
        CALL isBalanced(string)
        PRINT whether string is balanced
    ENDFOR
ENDFUNCTION

Algorithm Steps

  1. Define a CharStack class with: a. An array to store characters, with a top index. b. Methods: push (add character), pop (remove and return character), isEmpty (check if empty).
  2. In the isBalanced method: a. If the input is null, return true (considered balanced). b. Create a new CharStack. c. Iterate through each character in the input:
    • If it’s an opening bracket ('(', '{', '['), push it onto the stack.
    • If it’s a closing bracket (')', '}', ']'):
      • If the stack is empty, return false (no matching opening bracket).
      • Pop the top character and check if it matches the closing bracket.
      • If no match (e.g., '(' with '}'), return false. d. After iteration, return true if the stack is empty (all brackets matched), false otherwise.
  3. In the main method, test with valid, invalid, empty, and non-bracket strings, printing the input and result.

Java Implementation

public class ParenthesesChecker {
    // Custom stack implementation for characters
    static class CharStack {
        private char[] array;
        private int top;
        private static final int DEFAULT_SIZE = 1000;

        public CharStack() {
            array = new char[DEFAULT_SIZE];
            top = -1;
        }

        public boolean push(char c) {
            if (top == array.length - 1) {
                return false; // Stack full
            }
            array[++top] = c;
            return true;
        }

        public Character pop() {
            if (top == -1) {
                return null; // Stack empty
            }
            return array[top--];
        }

        public boolean isEmpty() {
            return top == -1;
        }
    }

    // Checks if a string of parentheses is balanced
    public boolean isBalanced(String input) {
        if (input == null) {
            return true;
        }
        CharStack stack = new CharStack();
        
        for (char c : input.toCharArray()) {
            if (c == '(' || c == '{' || c == '[') {
                stack.push(c);
            } else if (c == ')' || c == '}' || c == ']') {
                if (stack.isEmpty()) {
                    return false; // No matching opening bracket
                }
                Character popped = stack.pop();
                if (popped == null || !isMatchingPair(popped, c)) {
                    return false; // Mismatched brackets
                }
            }
        }
        return stack.isEmpty(); // Balanced only if stack is empty
    }

    // Helper method to check if brackets match
    private boolean isMatchingPair(char open, char close) {
        return (open == '(' && close == ')') ||
               (open == '{' && close == '}') ||
               (open == '[' && close == ']');
    }

    // Main method to test parentheses checker
    public static void main(String[] args) {
        ParenthesesChecker checker = new ParenthesesChecker();

        // Test cases
        String[] testStrings = {
            "{[()]}",          // Valid, balanced
            "((}",            // Invalid, mismatched
            "",               // Empty string
            "abc",            // No brackets
            "({[]})",         // Valid, nested
            "([)",            // Invalid, unmatched
            null,             // Null input
            "((()))"          // Valid, deeply nested
        };

        for (int i = 0; i < testStrings.length; i++) {
            System.out.println("Test case " + (i + 1) + ":");
            System.out.println("Input: \"" + (testStrings[i] != null ? testStrings[i] : "null") + "\"");
            boolean result = checker.isBalanced(testStrings[i]);
            System.out.println("Balanced: " + result + "\n");
        }
    }
}

Output

Running the main method produces:

Test case 1:
Input: "{[()]}"
Balanced: true

Test case 2:
Input: "((}"
Balanced: false

Test case 3:
Input: ""
Balanced: true

Test case 4:
Input: "abc"
Balanced: true

Test case 5:
Input: "({[]})"
Balanced: true

Test case 6:
Input: "([)"
Balanced: false

Test case 7:
Input: "null"
Balanced: true

Test case 8:
Input: "((()))"
Balanced: true

Explanation:

  • Test case 1: "{[()]}" → All brackets match: {→}, [→], (→) → true.
  • Test case 2: "((}" → Second '(' unmatched, '}' has no '{' → false.
  • Test case 3: "" → Empty string, no brackets → true.
  • Test case 4: "abc" → No brackets, ignored → true.
  • Test case 5: "({[]})" → All brackets match in nested order → true.
  • Test case 6: "([)" → '[' does not match ')' → false.
  • Test case 7: null → Considered balanced → true.
  • Test case 8: "((()))" → Deeply nested, all match → true.

How It Works

  • CharStack:
    • Uses an array to store characters, with top tracking the latest element.
    • push: Adds an opening bracket if the stack isn’t full.
    • pop: Removes and returns the top bracket if the stack isn’t empty.
    • isEmpty: Checks if the stack is empty.
  • isBalanced:
    • Pushes opening brackets ('(', '{', '[') onto the stack.
    • For closing brackets, pops the top bracket and checks for a match.
    • Returns false if the stack is empty when a closing bracket is found or if brackets don’t match.
    • Returns true if the stack is empty after processing (all brackets matched).
  • Example Trace (Test case 1):
    • Input: "{[()]}".
    • Push '{': stack = ['{'].
    • Push '[': stack = ['{', '['].
    • Push '(': stack = ['{', '[', '('].
    • Pop for ')': Matches '(', stack = ['{', '['].
    • Pop for ']': Matches '[', stack = ['{'].
    • Pop for '}': Matches '{', stack = [].
    • Stack empty → true.
  • Main Method: Tests valid, invalid, empty, non-bracket, and null inputs.

Complexity Analysis Table

OperationTime ComplexitySpace Complexity
Push (per char)O(1)O(1)
Pop (per char)O(1)O(1)
Full AlgorithmO(n)O(n)

Note:

  • n is the length of the input string.
  • Time complexity: O(n) for iterating through the string, with O(1) for each push/pop operation.
  • Space complexity: O(n) for the stack in the worst case (all opening brackets).
  • Worst case: O(n) time and O(n) space for a string like "(((((...".

✅ Tip: Use a stack to check balanced parentheses, as its LIFO nature naturally tracks nested brackets. Test with nested, mismatched, and non-bracket inputs to ensure robustness.

⚠ Warning: Handle null inputs and empty stacks to avoid NullPointerException or incorrect results. Ensure matching logic covers all bracket types ('()', '{}', '[]').