Valid Parentheses in Java: Solution, Explanation & Practice

Check if parentheses string is valid

Problem summary

Given a string containing just '(', ')', '{', '}', '[', ']', determine if the input string is valid. Use stack!

Starter code

public class Main {
    public static void main(String[] args) {
        String s = "([{}])";
        
        // Push opening brackets onto stack
        // For closing brackets, check if matches top
        // Stack should be empty at end
        // Print: Is valid: true
    }
}

Expected output and test cases

([{}])
```
Is valid: true
```
([)]
```
Is valid: false
```
```
Is valid: true
```

Hints

Push opening brackets onto stack
For closing bracket, pop and check if it matches
If stack empty when trying to pop, invalid
After processing, stack should be empty

Validated solution

Reveal Java solution

import java.util.ArrayDeque;
import java.util.Deque;

public class Main {
    static boolean valid(String text) {
        Deque<Character> stack = new ArrayDeque<>();
        for (char ch : text.toCharArray()) {
            if (ch == '(' || ch == '[' || ch == '{') stack.push(ch);
            else {
                if (stack.isEmpty()) return false;
                char open = stack.pop();
                if ((ch == ')' && open != '(') || (ch == ']' && open != '[') || (ch == '}' && open != '{')) return false;
            }
        }
        return stack.isEmpty();
    }
    public static void main(String[] args) { System.out.println("Is valid: " + valid("([{}])")); }
}

How to approach the problem

A stack remembers the most recent opening delimiter that has not yet been matched. Each closer must match that top delimiter, and a valid string leaves no unmatched openers at the end.

Approach

Push every opening delimiter.
Reject a closer when the stack is empty.
Pop and verify the matching opener.

Time and space complexity

Time: O(n). Space: O(n).

Edge cases to test

An empty String is valid.
A closer before any opener is immediately invalid.

Common mistakes

Using one counter, which cannot distinguish ([)] from balanced nesting.
Forgetting the final stack-empty check.

Follow-up challenge

Report the first index that makes a delimiter string invalid.

Related Data Structures & Algorithms exercises

Practice all Data Structures & Algorithms exercises · Run this idea in the Java compiler