Stack Matching Validation

Description

Brackets in code, tags in HTML, parentheses in a formula: every opener must be closed by the matching closer, and the most recently opened one must close first. Counting openers and closers isn't enough - "([)]" has balanced counts and is still wrong. A stack records exactly the order that matters.

This skill covers bracket matching with a stack: push openers, check each closer against the top, and require an empty stack at the end. It also covers pushing indices instead of characters, which measures the longest valid stretch.

We'll go from simple to more technical:

1. The pattern: push openers, match each closer with the most recent one, finish empty.
2. A second flavor: push indices with a base, to find the longest valid substring.
3. Where matching shows up (editors, parsers, compilers, undo histories).
4. What breaks it: popping empty, counting instead of stacking, the final check, contiguity.

The approach

boolean isValid(String s) {
    Deque<Character> stack = new ArrayDeque<>();
    for (char c : s.toCharArray()) {
        if (c == '(' || c == '[' || c == '{') {
            stack.push(c);
        } else {
            if (stack.isEmpty()) return false;              // a closer with nothing open
            char open = stack.pop();                        // it must match the MOST RECENT opener
            if ((c == ')' && open != '(') || (c == ']' && open != '[') || (c == '}' && open != '{')) return false;
        }
    }
    return stack.isEmpty();                                 // anything left was never closed
}

def is_valid(s: str) -> bool:
    stack = []                                      # a list is Python's stack: append / pop / [-1]
    for c in s:
        if c in "([{":
            stack.append(c)
        else:
            if not stack:
                return False                        # a closer with nothing open
            open_ = stack.pop()                     # it must match the MOST RECENT opener
            if (c == ")" and open_ != "(") or (c == "]" and open_ != "[") or (c == "}" and open_ != "{"):
                return False
    return not stack                                # anything left was never closed

Three checks, three distinct bugs if one is missing: a closer arriving at an empty stack (")"), a closer that doesn't match the top ("([)]"), and openers still waiting at the end ("(("). ArrayDeque is the stack to use; java.util.Stack is a legacy synchronized class built on Vector, and its own documentation recommends Deque instead. In Python a plain list is the stack (append, pop, stack[-1] to peek); queue.LifoQueue is the synchronized one, meant for passing work between threads.

A second flavor: push indices, not characters

"How long is the longest valid (well-formed, contiguous) substring?" Push each '(' index, and keep one extra index at the bottom: the position just before the current valid run.

int longestValidParentheses(String s) {
    Deque<Integer> stack = new ArrayDeque<>();
    stack.push(-1);                                   // base: just before the current valid run
    int best = 0;
    for (int i = 0; i < s.length(); i++) {
        if (s.charAt(i) == '(') {
            stack.push(i);
        } else {
            stack.pop();                              // match the latest '(' (or drop the base)
            if (stack.isEmpty()) stack.push(i);       // an unmatched ')' becomes the new base
            else best = Math.max(best, i - stack.peek());
        }
    }
    return best;
}

def longest_valid_parentheses(s: str) -> int:
    stack = [-1]                                    # base: just before the current valid run
    best = 0
    for i, c in enumerate(s):
        if c == "(":
            stack.append(i)
        else:
            stack.pop()                             # match the latest '(' (or drop the base)
            if not stack:
                stack.append(i)                     # an unmatched ')' becomes the new base
            else:
                best = max(best, i - stack[-1])
    return best

After a match, the top of the stack is the index just before the valid stretch ending at i, so its length is i - stack.peek(). Counting matched pairs instead gives the total, not the longest contiguous stretch: "()(()" has 2 pairs but its longest valid substring is 2, not 4. Measuring only from the matched '(' misses runs that join: "()(())" is 6, not 4.

Where you'll see it

Editors highlight the matching bracket and flag unclosed ones; JSON, XML and HTML parsers track open elements on a stack; compilers check nested blocks; and "undo" histories are stacks of the most recent actions.

Which tool for which job?

Common mistakes

Check yourself

Try to answer before opening each one - recalling beats re-reading.

1. Why isn't counting openers and closers of each type enough?

2. What must happen when a closer arrives and the stack is empty?

3. In longest valid parentheses, why keep a base index at the bottom of the stack?

Key takeaways

• Push openers; each closer must match the top; the stack must end empty.
• Check for an empty stack before popping.
• Use ArrayDeque, not java.util.Stack.
• Push indices with a base to measure the longest valid stretch.