复赛三：表达式(expr)

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113

/**************************************************************** 
 * Description: 2020 CSP-J 第三题 表达式 
 * Author: Alex Li
 * Date: 2024-08-06 21:21:01
 * LastEditTime: 2024-10-18 18:45:44
****************************************************************/
#include <iostream>
#include <vector>
#include <stack>
using namespace std;

const int N = 1e6 + 10; // 定义常量 N，表示数组的最大长度
int num[N]; // 存储每个结点的值
char c[N]; // 存储运算符
int m; // 表示当前操作数的数量
bool f[N]; // 存储每个结点的值修改后是否对表达式有影响

// 使用 vector 来构建邻接表
vector<vector<int>> adj(N); // 邻接表，adj[i] 表示第 i 个节点指向的其他节点

stack<int> st; // 用于存储后缀表达式中运算操作的栈
int n; // 变量的数量
string s; // 输入的后缀表达式

// 判断是否为数字字符
bool isDigit(char &i){
    return (i >= '0' && i <= '9');
}

// 将字符串转换为整数
int stringToInt(string &w) {
    int result = 0; // 保存最终的整数结果
    for (char ch : w) {
        result = result * 10 + (ch - '0'); // 将字符转为数字并累积到结果中
    }
    return result;
}

// 深度优先搜索，确定修改某个操作数是否影响表达式的最终值
void dfs(int x) {
    f[x] = true; // 标记当前结点会影响表达式的结果
    if (x <= n) return; // 如果是变量，则结束递归

    if (c[x] == '!') { // 如果是取反操作
        dfs(adj[x][0]); // 递归处理子表达式
    } else { // 如果是与运算或或运算
        int n1 = adj[x][0]; // 获取第一个操作数的结点
        int n2 = adj[x][1]; // 获取第二个操作数的结点
        if (c[x] == '&') { // 与运算
            if (num[n1] == 1) dfs(n2); // 若第一个操作数为1，递归检查第二个操作数是否影响结果
            if (num[n2] == 1) dfs(n1); // 若第二个操作数为1，递归检查第一个操作数是否影响结果
        } else if (c[x] == '|') { // 或运算
            if (num[n1] == 0) dfs(n2); // 若第一个操作数为0，递归检查第二个操作数是否影响结果
            if (num[n2] == 0) dfs(n1); // 若第二个操作数为0，递归检查第一个操作数是否影响结果
        }
    }
}

int main() {
    getline(cin, s); // 读取后缀表达式
    cin >> n; // 输入变量数量
    for (int i = 1; i <= n; i++) {
        cin >> num[i]; // 读取每个变量的初始值
    }
    string w = ""; // 临时字符串，用于存储变量的索引
    int x, y; // 临时变量，用于存储操作数
    m = n; // 初始化 m 为变量数量

    // 遍历后缀表达式，构造计算逻辑
    for (int i = 0; i < s.size(); i++) {
        if (isDigit(s[i])) { // 如果是数字
            w += s[i]; // 拼接数字，忽略 'x'，只用数字下标当变量
            // 如果下一个字符不是数字或者已经到了表达式末尾
            if (i == s.size() - 1 || !isDigit(s[i + 1])) {
                st.push(stringToInt(w)); // 将完整的变量索引(数字)入栈
                w = ""; // 清空临时字符串
            }
        } else if (s[i] == '!') { // 如果是取反操作
            m++;
            c[m] = s[i]; // 记录取反运算符
            x = st.top(); st.pop(); // 取出栈顶的变量
            num[m] = !num[x]; // 计算取反后的结果
            st.push(m); // 将结果入栈
            adj[m].push_back(x); // 添加边，构造子表达式关系
        } else if (s[i] == '&' || s[i] == '|') { // 如果是与运算或或运算
            m++;
            c[m] = s[i]; // 记录运算符
            x = st.top(); st.pop(); // 取出第一个操作数
            y = st.top(); st.pop(); // 取出第二个操作数
            // 根据运算符进行计算
            if (s[i] == '&') num[m] = num[x] & num[y];
            else if (s[i] == '|') num[m] = num[x] | num[y];
            st.push(m); // 将计算结果入栈
            adj[m].push_back(x); // 构造子表达式关系，添加边
            adj[m].push_back(y);
        }
    }

    int r = st.top(); // r是表达式的最终结果的编号，对应的是整个逻辑表达式计算完成后栈中的最后一个元素
    int ans = num[r]; // 即表达式的最终结果
    dfs(r); // 深度优先搜索，确定哪些变量会影响表达式结果

    int q;
    cin >> q; // 输入询问次数
    while (q--) {
        cin >> x; // 输入要取反的变量下标
        // 判断该变量是否影响结果
        if (f[x] == true) cout << !ans << endl;
        else cout << ans << endl;
    }

    return 0;
}