python/TangDou/CSP-J/J2_2020/3_Stack_BuJiang.cpp

#include <bits/stdc++.h>

using namespace std;
const int N = 1e6 + 10;
int e[N], el; // 表达式数组
int w[N];
int stk[N], tt;

/*
可以通过6个测试点，30分

学到的知识：
1、利用字符串读入后缀表达式
2、利用栈来计算后缀表达式
*/

// 计算表达式的值
int calc() {
    // 后缀表达式求值，需要借助栈
    tt = 0;
    // 枚举所有的表达式符号
    for (int i = 1; i <= el; i++) {
        // 如果是数字，直接入栈
        if (e[i] > 0) stk[++tt] = w[e[i]]; // e[i]=1 --> 1  --> x1---> w[1] <==> w[e[i]]
        // 如果是 非 操作符取一个数字出来　运算
        else if (e[i] == -3) { //! 非　运算符
            int n1 = stk[tt--];
            stk[++tt] = !n1; // 对n1取反，再放回去
        } else {
            // 如果是与和或的话，那么需要取两个操作符
            // 注意一个细节，这里从栈中取出的数字是反的，n1是后面的，n2是前面的
            int n1 = stk[tt--];
            int n2 = stk[tt--];
            // 根据e[i]的操作符不同，知道是与还是或
            if (e[i] == -1)
                stk[++tt] = n2 & n1;
            else
                stk[++tt] = n2 | n1;
        }
    }
    return stk[tt];
}

int main() {
    // 文件输入
    //  freopen("3.in", "r", stdin);
    // 读入整行
    string s;
    getline(cin, s); // 带空格的整行数据

    // 拆开
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == ' ') continue; // 跳过空格
        if (s[i] == 'x') {
            i++; // 跳过x
            int k = 0;
            while (i < s.size() && s[i] >= '0' && s[i] <= '9') k = k * 10 + s[i++] - '0';
            e[++el] = k; // 记录操作符 x1,x2,...,x332
        }
        // 因为e[]中需要区分是操作符，变量，不能直接使用ASCII，因为比如 ascii(&)=38,可是，人家k=38,也就是有x38这个变量存在，你就无法分清楚是&还是x38
        // 使用负数-1，-2，-3进行标识，就不存在这个问题，肯定能唯一标识是操作符还是操作数
        else if (s[i] == '&')
            e[++el] = -1;
        else if (s[i] == '|')
            e[++el] = -2;
        else if (s[i] == '!')
            e[++el] = -3;
    }

    // 打印表达式里面的值，看看有没有什么错误,单元测试
    //  for (int i = 1; i <= len; i++) cout << e[i] << " ";

    // 读入n个变量
    // 上面取入的是x1,x2,x3，也就是变量的下标，读入的是真正的操作数值
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> w[i];

    // Q次查询
    int Q, x;
    cin >> Q;
    for (int i = 1; i <= Q; i++) {
        // 对第x个操作数进行取反
        cin >> x;
        // 只时临时修改，不是永久修改
        w[x] = !w[x];
        // 重新计算表达式的值
        printf("%d\n", calc());
        // 还回来
        w[x] = !w[x];
    }
    return 0;
}