栈模板

#include <bits/stdc++.h>
using namespace std;

// 括号匹配
bool isValid(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();
}

// 后缀表达式求值
int evalRPN(vector<string> &tokens) {
    stack<int> st;
    for (auto &t : tokens) {
        if (t == "+" || t == "-" || t == "*" || t == "/") {
            int b = st.top(); st.pop();
            int a = st.top(); st.pop();
            if (t == "+") st.push(a + b);
            else if (t == "-") st.push(a - b);
            else if (t == "*") st.push(a * b);
            else st.push(a / b);
        } else {
            st.push(stoi(t));
        }
    }
    return st.top();
}

int main() {
    cout << isValid("({[]})") << endl;  // 1
    cout << isValid("({[})") << endl;   // 0
    return 0;
}

📖 要点说明

• 栈：后进先出，push/pop/top
• 括号匹配是栈的经典应用
• 后缀表达式天然适合栈求值

⚠️ 常见错误

• 访问空栈的 top（先检查 empty）
• 括号匹配忘处理栈非空的情况
• 后缀表达式运算符弹栈顺序 a,b 搞反