2020 表达式 · 方案一每次重算后缀式

CSP-J 标程 · 复赛真题 · 代码 · cpp · 难度 3/5 · 共 1597 字

用栈求后缀表达式，每次询问重算一遍

2020
栈

正文

// CSP-J 2020 复赛 T3 · 表达式
// 原题：https://oj.yecheng.tv/p/CSPJ2020C
// 题意：给一个后缀逻辑表达式（运算是 & | !，变量是 x1, x2, ...且每个变量只出现一次），
// 每次询问「把某个变量取反后，整个表达式的值是多少」，询问之间互不影响。
//
// 方案一 · 每次询问重新算一遍（暴力，q 大时会超时）
// 先把整行按空格切成 token，再用栈按后缀表达式的规则求值：
//   遇到变量就压栈；遇到 & 或 | 就弹出两个算完再压回去；遇到 ! 就弹出一个取反。
// 每次询问临时改一下那个变量的值，算完再改回来。
// 一次求值 O(|s|)，q 次就是 O(q|s|)，只能过小数据 —— 但它最能帮助理解后缀表达式。

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

int evalExpr(const vector<string>& tok, const vector<int>& v) {
    stack<int> st;
    for (const string& s : tok) {
        if (s == "&") {
            int b = st.top(); st.pop();
            int a = st.top(); st.pop();
            st.push(a & b);
        } else if (s == "|") {
            int b = st.top(); st.pop();
            int a = st.top(); st.pop();
            st.push(a | b);
        } else if (s == "!") {
            int a = st.top(); st.pop();
            st.push(!a);
        } else {
            st.push(v[stoi(s.substr(1))]);   // 形如 x10，去掉首字母就是下标
        }
    }
    return st.top();
}

int main() {
    freopen("expr.in", "r", stdin);
    freopen("expr.out", "w", stdout);

    string line;
    getline(cin, line);
    vector<string> tok;
    stringstream ss(line);
    string s;
    while (ss >> s) tok.push_back(s);

    int n;
    cin >> n;
    vector<int> v(n + 1);
    for (int i = 1; i <= n; i++) cin >> v[i];

    int q;
    cin >> q;
    while (q--) {
        int idx;
        cin >> idx;
        v[idx] ^= 1;                       // 临时取反
        cout << evalExpr(tok, v) << "\n";
        v[idx] ^= 1;                       // 改回来，不影响下一次询问
    }
    return 0;
}

2020 表达式 · 方案一 每次重算后缀式

正文

CSP-J 标程 · 复赛真题的其它内容

2020 表达式 · 方案一每次重算后缀式