Balanced Parentheses Problem Using Stack in DSA Java

Mental Model

We use a stack to keep track of opening brackets and check if each closing bracket matches the last opened one.

Analogy: Imagine you are stacking plates. Each time you get an opening bracket, you put a plate on the stack. When you get a closing bracket, you remove the top plate and check if it matches the type of bracket.

Stack (top at right): []
Expression: ( [ { } ] )
↑ start reading from left to right

Dry Run Walkthrough

Input: expression: "({[]})"

Goal: Check if the expression has balanced parentheses, meaning every opening bracket has a matching closing bracket in the correct order.

Step 1: Read '(' and push it onto the stack

Stack: [ '(' ]
Expression: ( { [ ] } )
           ↑

Why: We store opening brackets to match them later with closing brackets

Step 2: Read '{' and push it onto the stack

Stack: [ '(', '{' ]
Expression: ( { [ ] } )
             ↑

Why: Keep track of nested opening brackets

Step 3: Read '[' and push it onto the stack

Stack: [ '(', '{', '[' ]
Expression: ( { [ ] } )
               ↑

Why: Add the next opening bracket to stack

Step 4: Read ']' and check top of stack; it is '[' so pop it

Stack: [ '(', '{' ]
Expression: ( { [ ] } )
                 ↑

Why: Closing bracket matches last opening bracket, so remove it

Step 5: Read '}' and check top of stack; it is '{' so pop it

Stack: [ '(' ]
Expression: ( { [ ] } )
                   ↑

Why: Match found, pop the opening bracket

Step 6: Read ')' and check top of stack; it is '(' so pop it

Stack: []
Expression: ( { [ ] } )
                     ↑

Why: Final closing bracket matches the last opening bracket

Result:

Stack: []
Expression fully processed
Result: Balanced parentheses

Annotated Code

DSA Java

import java.util.Stack;

public class BalancedParentheses {

    public static boolean isBalanced(String expression) {
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < expression.length(); i++) {
            char ch = expression.charAt(i);
            if (ch == '(' || ch == '{' || ch == '[') {
                stack.push(ch); // push opening bracket
            } else if (ch == ')' || ch == '}' || ch == ']') {
                if (stack.isEmpty()) {
                    return false; // no matching opening bracket
                }
                char top = stack.pop(); // pop last opening bracket
                if (!matches(top, ch)) {
                    return false; // brackets do not match
                }
            }
        }
        return stack.isEmpty(); // true if all brackets matched
    }

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

    public static void main(String[] args) {
        String expression = "({[]})";
        boolean result = isBalanced(expression);
        System.out.println(result ? "Balanced parentheses" : "Not balanced");
    }
}

stack.push(ch); // push opening bracket

Add opening bracket to stack to match later

if (stack.isEmpty()) { return false; }

If closing bracket found but stack empty, no match possible

char top = stack.pop();

Remove last opening bracket to check match

if (!matches(top, ch)) { return false; }

Check if popped opening bracket matches current closing bracket

return stack.isEmpty();

If stack empty at end, all brackets matched

Output

Balanced parentheses

Complexity Analysis

Time: O(n) because we scan the expression once, pushing and popping at most once per character

Space: O(n) in worst case when all characters are opening brackets stored in the stack

vs Alternative: Compared to checking pairs by scanning multiple times, stack approach is efficient and linear

Edge Cases

Empty string

Returns true because no brackets means balanced

DSA Java

return stack.isEmpty();

String with only opening brackets like "((("

Returns false because stack is not empty at end

DSA Java

return stack.isEmpty();

String with closing bracket first like ")("

Returns false because stack is empty when closing bracket found

DSA Java

if (stack.isEmpty()) { return false; }

When to Use This Pattern

When you see a problem asking if brackets or symbols are properly matched and nested, use a stack to track opening symbols and verify closing ones.

Common Mistakes

Mistake: Not checking if stack is empty before popping, causing errors
Fix: Always check stack.isEmpty() before popping to avoid exceptions

Mistake: Matching brackets by comparing characters directly without a helper function
Fix: Use a separate matches function to clearly check pairs

Summary

Checks if every opening bracket has a matching closing bracket in correct order using a stack

Use when validating expressions with nested brackets or symbols

The key insight is to push opening brackets and pop them only when a matching closing bracket appears

Practice

1. What does the Balanced Parentheses problem using a stack check for in a string?

easy

A. Whether every opening bracket has a matching closing bracket in correct order

B. If the string contains only alphabets

C. If the string length is even

D. Whether the string contains any digits

Solution

1. Step 1: Understand the problem goal

   The Balanced Parentheses problem checks if all opening brackets like '(' have a matching closing bracket ')' in the correct order.

2. Step 2: Role of stack in checking

   A stack helps track opening brackets and ensures each is closed properly in sequence.

3. Final Answer:

   Whether every opening bracket has a matching closing bracket in correct order -> Option A

4. Quick Check:

   Balanced parentheses = matching pairs [OK]

Hint: Match each '(' with ')' using stack push/pop [OK]

Common Mistakes:

• Thinking it checks string length
• Ignoring order of brackets
• Checking only for digits or alphabets

2. Which of the following Java code snippets correctly initializes a stack to check balanced parentheses?

easy

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

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

C. Stack<Character> stack = Stack();

D. Stack<Character> stack = new Stack<Character>;

Solution

1. Step 1: Check correct Stack initialization syntax

   In Java, to create a stack of Characters, use: Stack<Character> stack = new Stack<>(); which uses diamond operator for type inference.

2. Step 2: Identify errors in other options

   Stack stack = new Stack<Character>(); misses generic type on right side; Stack<Character> stack = Stack(); misses 'new' keyword; Stack<Character> stack = new Stack<Character>; misses parentheses after constructor.

3. Final Answer:

   Stack<Character> stack = new Stack<>(); -> Option A

4. Quick Check:

   Correct Java stack init = Stack<Character> stack = new Stack<>(); [OK]

Hint: Use diamond operator <> with new Stack<>() [OK]

Common Mistakes:

• Omitting 'new' keyword
• Missing parentheses after constructor
• Incorrect generic type syntax

3. What will be the output of the following Java code snippet?

String s = "({[]})";
System.out.println(isBalanced(s));

public static boolean isBalanced(String s) {
    Stack<Character> stack = new Stack<>();
    for (char c : s.toCharArray()) {
        if (c == '(' || c == '{' || c == '[') {
            stack.push(c);
        } else {
            if (stack.isEmpty()) return false;
            char top = stack.pop();
            if ((c == ')' && top != '(') ||
                (c == '}' && top != '{') ||
                (c == ']' && top != '[')) {
                return false;
            }
        }
    }
    return stack.isEmpty();
}

medium

A. Compilation error

B. false

C. true

D. Runtime exception

Solution

1. Step 1: Trace the input string "({[]})" character by character

   Push '(' '{' '[' onto stack; then pop matching pairs for ']' '}' ')'. Stack ends empty.

2. Step 2: Check final stack state

   Stack is empty after processing all characters, so return true.

3. Final Answer:

   true -> Option C

4. Quick Check:

   All brackets matched = true [OK]

Hint: Stack empty at end means balanced [OK]

Common Mistakes:

• Not checking stack empty at end
• Mismatching brackets order
• Ignoring empty stack before pop

4. Identify the error in this Java method for checking balanced parentheses:

public static boolean checkBalanced(String s) {
    Stack<Character> stack = new Stack<>();
    for (char c : s.toCharArray()) {
        if (c == '(' || c == '{' || c == '[') {
            stack.push(c);
        } else {
            char top = stack.pop();
            if ((c == ')' && top != '(') ||
                (c == '}' && top != '{') ||
                (c == ']' && top != '[')) {
                return false;
            }
        }
    }
    return stack.isEmpty();
}

medium

A. For loop syntax is incorrect

B. Wrong comparison operators used

C. Stack should store Strings not Characters

D. Missing check if stack is empty before pop

Solution

1. Step 1: Analyze stack pop operation

   Pop is called without checking if stack is empty, which can cause runtime exception if closing bracket appears first.

2. Step 2: Identify missing empty check

   Must check stack.isEmpty() before pop to avoid EmptyStackException.

3. Final Answer:

   Missing check if stack is empty before pop -> Option D

4. Quick Check:

   Always check stack empty before pop [OK]

Hint: Check stack empty before pop to avoid errors [OK]

Common Mistakes:

• Ignoring empty stack before pop
• Assuming input always starts with opening bracket
• Not handling runtime exceptions

5. Given the string "[{()}]({[]})", which of the following modifications to the balanced parentheses algorithm will correctly handle this input and return true?

hard

A. Use two stacks, one for opening and one for closing brackets separately

B. Use a stack and check matching pairs for all bracket types, ensuring stack is empty at end

C. Only check if the string length is even and contains brackets

D. Ignore curly braces '{}' and only check parentheses '()'

Solution

1. Step 1: Understand input complexity

   The string contains multiple types of brackets nested and sequentially combined.

2. Step 2: Apply stack-based matching for all bracket types

   Push opening brackets, pop and match closing brackets; ensure stack empty at end for balanced check.

3. Step 3: Evaluate other options

   Length check or ignoring bracket types will fail; two stacks unnecessary and incorrect.

4. Final Answer:

   Use a stack and check matching pairs for all bracket types, ensuring stack is empty at end -> Option B

5. Quick Check:

   Stack matching all brackets = true [OK]

Hint: Match all bracket types with one stack, check empty at end [OK]

Common Mistakes:

• Ignoring some bracket types
• Relying on string length only
• Using multiple stacks unnecessarily