Stack / Monotonic Stack

1// Bracket matching — push openers, match on closers
2bool isValid(string s)
3{
4    stack<char> st;
5 
6    for (char c : s)
7    {
8        if (c == '(' || c == '[' || c == '{')
9        {
10            st.push(c);         // push opener
11        }
12        else
13        {
14            // closer — stack must have a matching opener
15            if (st.empty()) return false;
16 
17            char top = st.top(); st.pop();
18 
19            if ((c == ')' && top != '(') ||
20                (c == ']' && top != '[') ||
21                (c == '}' && top != '{'))
22            {
23                return false;   // mismatched pair
24            }
25        }
26    }
27 
28    return st.empty();          // all openers matched
29}