既然老师要求那就写一下题解吧，正好之前一直都不会表达式树有关的芝士。

首先题意很明显，就不赘述了。但是这个题目看起来用直接的模拟会比较麻烦，而且越想越假。那么导致模拟麻烦的原因是什么呢？其实就时运算顺序对吧，那么接下来就要请出本次主角——后缀表达式

首先我们拿到的这个字符串是一个中缀表达式，它有个很麻烦的点就是计算优先级。但是本期主角后缀表达式就可以很好地解决这个问题，因为后缀表达式是没有括号的，而且计算优先级很明显（当然是对于计算机来说），从而可以更方便地计算。

那么首先要说地就是如何将中缀表达式转换成后缀表达式

对于输入的字符串，我们有 5 种可能：

1.这是数字，即 0或 1

2. 这是左边的括号

3.这是右边的括号

4.这是 & 运算符

5. 这是 |∣ 运算符

然后再回想一下中缀是怎么转后缀的，首先我们需要一个栈（用于存储括号或者运算符）与一个存储表达式的结果的 vector

对于情况 1，我们直接将其压入 vector

对于情况 2，我们将其放入栈中等待匹配

对于情况 3，我们要考虑将这个右括号与先前的左括号进行匹配。那么我们就使用 while循环找左括号，在遇到左括号之前的所有运算符都直接压入 vector，因为栈是先进后出，刚好符合转后缀表达式的需要

对于情况 4，我们同样遍历栈，如果前面遇到 & ，那么就放入我们的 vectorvector 中，因为遇到的 & 就说明遇到比自己更早或者同时要进行运算的运算符，所以要先放进去

对于情况 5，遍历栈，如果遇到左括号就停止。

对于人来说，这并没有简便多少；但是对于计算机来说，至于要从左往右将两个数用后面的一个运算符进行运算即可。

那么转好了后缀之后还是不行，因为还是不好算。所以我们还需要建表达式树。

struct node{
	int v,l,r;// 值 || 左儿子 || 右儿子
}tr[N];

我们直接遍历这个后缀表达式，如果遇到了 数字 ， 那么就直接建立一个节点，并且将其放入栈中。如果遇到的是运算符，那么就从栈里面取出两个数，建为右儿子和左儿子，然后根据这个运算符是 & 还是 | 对这个点进行赋值，注意和上面的 0 和 1 区分。

树建好后就开始深搜遍历整棵树并且进行计算。首先如果这个点它是叶子节点 ， 即代表数字 ， 那么直接返回该节点的值。因为我们还要进行短路的计算，所以要先看左儿子和该节点的运算符是否构成短路 。那么短路之后我们可以直接返回左儿子计算的值，因为如果不短路 ， 那么本次计算的结果就取决于右儿子的值。

怎么证明呢？有个很好的证明方法：

首先考虑数值与符号有几种构成方式 无非就 0& // 0| // 1& // 1| 四种那么反过来也一样 所以如果前面的这个数它与运算符不构成短路，那么后面的这个数和运算符 一定是可以构成短路的 （当然按照题目意思是不能计算再在短路计数中的） 所以最后如果不能短路那么久取决于右儿子的值

讲了那么多， ~相信你也没咋懂~ ，那么

OK上代码（

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
int n ,  ans1 , ans2 ,x,y;
struct node{
	int v,l,r;
}tr[N];
int num;
stack<char> ops;
vector<char> sf;
string s; 
stack<int> sta;
void change(){
	for(int i=0;i<n;i++){
		if(s[i] == '0' || s[i] == '1') sf.push_back(s[i]);
		else if(s[i] == '(') ops.push(s[i]);
		else if(s[i] == ')'){
			while(!ops.empty() && ops.top() != '('){
				sf.push_back(ops.top());
				ops.pop();
			}
			ops.pop();
			
		}
		else if(s[i] == '&'){
			while(!ops.empty() && ops.top() == '&'){
				sf.push_back(ops.top());
				ops.pop();
			}
			ops.push('&');
		}
		else if(s[i] == '|'){
			while(!ops.empty() && ops.top() != '('){
				sf.push_back(ops.top());
				ops.pop();
			}
			ops.push('|');
		}
	}
	while(!ops.empty()){
		sf.push_back(ops.top());
		ops.pop();
	}
}
void build(){

	for(int i=0;i<sf.size();i++){
		if(sf[i] == '0' || sf[i] == '1') {
			tr[++num] = {sf[i] - '0' , -1 , -1};
		//	cout << sf[i] << endl;
			sta.push(num);
		}
		else{
			int r = sta.top() ; sta.pop();
			
			int l = sta.top() ; sta.pop();
			
			int v = (sf[i] == '&') ? 2 : 3;
			tr[++num] = {v , l , r};
			sta.push(num);
		}
	}
}
int dfs(int u){
	if(tr[u].v == 0 || tr[u].v == 1) return tr[u].v;
	int l = dfs(tr[u].l) ;
//	cout << ans1 << " " << ans2 << endl;
	if(l == 0 && tr[u].v == 2){
		ans1++;
	//	x = max(x , ans1);
		return 0;
	}
	if(l == 1 && tr[u].v == 3){
		ans2++;
	//	y =  ans2;
		return 1;
	}
	int r = dfs(tr[u].r); //没有短路， 结果取决于r
	return r;
	
}
int main(){
	cin >> s;
	n = s.size();
	change();
	build();
	int t = dfs(num);
	cout << t << endl << ans1 << " " << ans2; 
	return 0; 
}

谢谢观看 QwQ !