答案:<pre class="brush:cpp;toolbar:false">#include <bits/stdc++.h>
using namespace std;
/*
取反某一个操作数的值时,原表达式的值为多少
思路:
1.读入表达式,将表达式建成二叉树
2.计算出表达式的值
3.深搜,求出哪些结点的值修改后对结果有影响
*/
const int N = 1e6 + 10;
struct node{
int to,next;
}a[N];//邻接表
int pre[N],k;//存储以每个点为起点的最后一条边的编号
int num[N];//存储二叉树每个结点的值
char c[N];//存储操作符
int m;//表示c数组的下标
bool f[N];//标记哪些点的值修改后对结果有影响
int n;
string s,w;//w用来存储每个操作数的下标
stack<int> st;//用于计算后缀表达式
//建边
void add(int u,int v){
k++;
a[k].to = v;
a[k].next = pre[u];
pre[u] = k;
}
//深搜求哪些结点的值修改后对结果有影响
void dfs(int x){
f[x] = true;
if(x <= n) return;//如果是叶子结点
if(c[x] == '!') dfs(a[pre[x]].to);
else{
int n1 = a[pre[x]].to,n2 = a[a[pre[x]].next].to;
if(c[x] == '&'){
if(num[n1] == 1) dfs(n2);
if(num[n2] == 1) dfs(n1);
}else if(c[x] == '|'){
if(num[n1] == 0) dfs(n2);
if(num[n2] == 0) dfs(n1);
}
}
}
int main()
{
getline(cin,s);
cin>>n;
for(int i = 1;i <= n;i++){
scanf("%d",&num[i]);
}
//分析表达式,建树
int x,y;
m = n;
for(int i = 0;i < s.size();i++){
if(isdigit(s[i])){
w = w + s[i];
//如果连续数字结束
if(i==s.size()-1||!isdigit(s[i+1])){
st.push(atoi(w.c_str()));//将操作数的下标入栈
w = "";
}
}else if(s[i] == '!'){
//如果是取反操作符
m++;
c[m] = s[i];//操作符的编号是m
x = st.top();//取栈顶元素来运算
st.pop(); //出栈
//建边
add(m,x);
num[m] = !num[x];
st.push(m);
}else if(s[i] == '&' || s[i] == '|'){
//如果是& |操作符
m++;
c[m] = s[i];
//取2个操作数
x = st.top();
st.pop();
y = st.top();
st.pop();
//建边
add(m,x);
add(m,y);
//计算结点的值
if(s[i] == '&') num[m] = num[x] & num[y];
else if(s[i] == '|') num[m] = num[x] | num[y];
st.push(m);
}
}
int ans = num[st.top()];
//cout<<ans;
//深搜求哪些结点的值修改后对结果有影响
dfs(st.top());//从根开始深搜
//q次询问
int q;
cin>>q;
while(q--){
scanf("%d",&x);
if(f[x]==true) printf("%d\n",!ans);
else printf("%d\n",ans);
}
return 0;
}</pre><p><br/></p>
这道题暂未补解析。