Parentheses Problems

The stack stores unmatched opening brackets

In a string of brackets, not only the number of opening and closing symbols matters, but also their nesting. When we encounter an opening bracket, we do not yet know where it will be closed, so we push it onto the stack. A closing bracket must match the most recent unmatched opening bracket — the top of the stack.

static boolean isValid(String text) {
    Deque<Character> stack = new ArrayDeque<>();

    for (char ch : text.toCharArray()) {
        if (ch == '(' || ch == '[' || ch == '{') {
            stack.push(ch);
            continue;
        }

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

        char open = stack.pop();
        if ((ch == ')' && open != '(')
                || (ch == ']' && open != '[')
                || (ch == '}' && open != '{')) {
            return false;
        }
    }

    return stack.isEmpty();
}

Why counting alone is not enough

The string "([)]" contains the same number of opening and closing brackets, but the order is invalid: the round bracket tries to close while a square bracket is on top of the stack. The stack preserves the nesting structure rather than only a count.

Two common mistakes

If a closing bracket appears while the stack is empty, there is nothing for it to close, so the string is invalid immediately. If the stack is not empty after the whole string has been processed, some opening brackets never received a matching pair. Both checks are necessary.

Each character is processed once, so the time complexity is O(n), with O(n) additional memory in the worst case.