[CSP-J2020] 表达式 题解

短路

这道题目中所含的运算符只有3个:与、或、非.

在与运算和或运算中有2个性质.

进行与运算时，若其中有一个值为0，则这个运算的结果就为0，即无需判断

另1个数是否是0或1.

进行或运算时，若其中有一个值为1，则这个运算的结果就为1，也无需判断

另一个数是否是0或1.

表达式树

根据短路的性质，可以得知，在与运算时，如果当前值为1，则需额外判断另

一个数是否为0,1，因为它的值可能会影响整个表达式的值.因此，需要构造一

棵表达式树.

其中，需要存储节点的编号，值，左孩子，右孩子.

染色

在递归的过程中，可以通过染色，判断这个节点对树的值是否有影响.

代码

#include<bits/stdc++.h>
using namespace std;
string s;
int n, x[100005], cnt, num, c[100002], f[1000002];
int q, k;
struct node { // 定义结构体 
	int id, v, lc, rc;
	// 编号，值，左孩子，右孩子 
}t[1000002]; // tree 
stack<int> st;
void post_to_tree() { // 转成表达式树的形式，以链式的方法存储
	// !为-1，|为-2，&为-3 
	for (int i = 0; i < s.size(); i++) {
		if (s[i] == 'x') num = 0; // 如果说当前字符是x，则下一个字符一定是x的下表 
		else if (s[i] >= '0' && s[i] <= '9')
			num = num * 10 + (s[i] - '0'); // 用num存储下来下标的值 
		else if (s[i] == ' ') {
			if (s[i-1] >= '0' && s[i-1] <= '9') { // 上一个是下标 
				t[++cnt] = (node){cnt, num, -1, -1}; // lc, rc = -1, 表示没有 
				st.push(cnt); // 放入栈 
			}
		}
		else if (s[i] == '!') {
			int t1 = st.top();st.pop(); // 拿出栈顶元素
			// 因为!为单目运算符，所以只要存左孩子就行了 
			t[++cnt] = (node){cnt, -1, t1, -1}; // 创建新节点 
			st.push(cnt); // 存编号 
		}
		else if (s[i] == '|') { // | 和 & 为双目运算符，所以要弹2个，并存左孩子和右孩子 
			int t1 = st.top();st.pop();
			int t2 = st.top();st.pop();
			t[++cnt] = (node){cnt, -2, t1, t2};
			st.push(cnt);
		}
		else if (s[i] == '&') {
			int t1 = st.top();st.pop();
			int t2 = st.top();st.pop();
			t[++cnt] = (node){cnt, -3, t1, t2};
			st.push(cnt);
		}
	}
}
bool calc_tree(int u) { // 计算树的原值 
	// 用f数组存值 
	if (t[u].v > 0) // 不是运算符 
		return f[u]=x[t[u].v]; // 在存入f数组中 
	if (t[u].v == -1) // !
		return f[u]=!calc_tree(t[u].lc);
	// 这里千万不能直接或和与，因为根据短路性质，第2个值可能就不算了 
	if (t[u].v == -2) { // |
		bool f1 = calc_tree(t[u].lc);
		bool f2 = calc_tree(t[u].rc);
		return f[u] = f1 || f2; 
	}
	// 这里分开算与或同理 
	if (t[u].v == -3) { // &
		bool f1 = calc_tree(t[u].lc);
		bool f2 = calc_tree(t[u].rc);
		return f[u] = f1 && f2;
	}
}
void solve_tree(int u) {
	if (t[u].v > 0) { // 如果是一个值，那可能会对值造成影响
		c[t[u].v] = 1; // 进行染色 
		return ;
	}
	if (t[u].v == -1) // !运算递归染色 
		solve_tree(t[u].lc);
	if (t[u].v == -2) { // &运算 
		if (f[t[u].lc] == 0) solve_tree(t[u].rc); // 一个为0，则会有短路	
		if (f[t[u].rc] == 0) solve_tree(t[u].lc); // 右边同理 
	}
	if (t[u].v == -3) {
		if (f[t[u].lc] == 1) solve_tree(t[u].rc); // 一个为1，则也会有短路 
		if (f[t[u].rc] == 1) solve_tree(t[u].lc); // 右边同理 
	}
}
int main() {
//	freopen("expr2.in", "r", stdin);
//	freopen("expr2.out", "w", stdout);
	getline(cin, s);
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%d", &x[i]);
	// 构建表达式树
	post_to_tree();
	// 计算原值 
	calc_tree(cnt);
	// 递归自己的改变是否影响原值 
	solve_tree(cnt);
	scanf("%d", &q);
	for (int i = 1; i <= q; i++) {
		scanf("%d", &k);
		if (c[k]) printf("%d\n", !f[cnt]); // 被染色，说明会影响原值，取反 
		else printf("%d\n", f[cnt]);
	}
	return 0;
}