Chapter 29

Home

Refactoring: Stack for Parentheses

The parentheses problem from Chapter 28 works with a single bracket type. But real problems throw multiple bracket types at you. The naive counter approach breaks — the stack approach scales cleanly to any bracket set.

Before: The Counter Hack

For a single bracket type (just ()), many beginners use a counter: +1 for (, -1 for ). It works for one type, but fails the moment you add [] or {}.

C++ — fragile counter approach

bool is_balanced(const string& s) {
    int count = 0;
    for (char c : s) {
        if (c == '(') count++;
        else if (c == ')') count--;
        if (count < 0) return false;
    }
    return count == 0;
}

🚨 Why the counter breaks

[(]) — the counter would say this is balanced (two opens, two closes), but it's clearly malformed. The ] matches the wrong opener. Only a stack captures the nesting order.

After: Stack-Based Solution

The stack preserves ordering. When you see a close bracket, it must match the most recent unmatched open bracket — which is exactly what top() gives you.

C++ — robust stack approach

bool is_balanced(const string& s) {
    stack<char> st;
    for (char c : s) {
        if (c == '(' || c == '[' || c == '{') {
            st.push(c);
        } else {
            if (st.empty()) return false;
            char top = st.top(); st.pop();
            if ((c == ')' && top != '(') ||
                (c == ']' && top != '[') ||
                (c == '}' && top != '{'))
                return false;
        }
    }
    return st.empty();
}

Rust — robust stack approach

fn is_balanced(s: &str) -> bool {
    let mut st: Vec<char> = Vec::new();
    for c in s.chars() {
        match c {
            '(' | '[' | '{' => st.push(c),
            ')' => if st.pop() != Some('(') { return false; }
            ']' => if st.pop() != Some('[') { return false; }
            '}' => if st.pop() != Some('{') { return false; }
            _ => {}
        }
    }
    st.is_empty()
}

💡 The stack mirrors the call stack

When you call functions inside functions, the CPU uses a call stack. Each call is pushed, each return pops. Nested parentheses are the same idea — a stack perfectly models nested structure.

A Real-World Extension: Longest Valid Parentheses

A harder problem: find the length of the longest valid (well-formed) parentheses substring. The stack can track indices too.

C++ — longest valid parentheses (single type)

int longest_valid(const string& s) {
    stack<int> st;
    st.push(-1);  // base index
    int max_len = 0;

    for (int i = 0; i < s.size(); i++) {
        if (s[i] == '(') {
            st.push(i);
        } else {
            st.pop();
            if (st.empty()) {
                st.push(i);  // new base
            } else {
                max_len = max(max_len, i - st.top());
            }
        }
    }
    return max_len;
}

📐 How the index stack works

Store indices of unmatched (. When you see a ), pop one. If the stack is empty afterward, push the current index as the new "base." The distance from the current index to st.top() is the length of the valid segment ending here.

Key Takeaways

Practice