s1、中缀转后缀

1，我们将其压入 vector{如果是数字，直接入后缀表达式。 }

2，我们将其放入栈中等待匹配

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

{如果是 ( 压入运算符栈。如果是 ) 输运算符栈不断出栈到后缀表达式，直到碰到 (。}

4，我们同样遍历栈，如果前面遇到 & ，放入vectorvector 中.先进先出，后进后出，比较符号优先级。（优先级别：第一级是(),第二级是&,第三级是|。）

5，不断出栈到后缀表达式。

s2、 直接遍历这个后缀表达式,如果符号是操作数，那么我们就建立一个儿子树并将一个指向它的指针推入栈中，成一颗以操作符为根的树，其中 T1 为右儿子，T2 为左儿子；

然后将新的树压入栈中。（根据这个运算符是 & 还是 | 对这个点进行赋值，注意和上面的 0 和 1 区分。）

s3、遍历DFS 。

数值 0 或 1，非叶子一定是 & 或者 | 。

DFS ：

遍历到叶子直接返回叶子的值；||遍历到非叶子时，先递归在返回对应的子树的值。

然后，判断是否会短路：1| 会发生“或短路”，并且返回 1；||0& 会发生“与短路”，并且返回 0。

非上面两种情况，计算右子树的值并返回其结果即可：0 或 1，结果都是数。

代码：

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6+5;

string s;

struct Node{

int v,l,r;

} tr[N];//数组tr用于存放树的每个节点的值v,左子树位置和右子树位置l和r

int num, ans1, ans2;

stack ops;//运算符栈

stack sta;//声明一个栈sta来缓存每个节点的位置

vector sf; // sf后缀表达式

void change(){// 中缀表达式转后缀，1、 运算符转移到sf，直到ops为空或者计算级别不同，再将此运算符push进去。

for(int i=0;i<s.size();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()); // keepgoing，直到碰到) 

			ops.pop();

		}

		ops.pop(); // 弹出多（ 

	}

	else if(s[i] == '&') {// &

		while(!ops.empty()&&ops.top()=='&'){

			sf.push_back(ops.top());

			ops.pop();

		}

		ops.push('&');

	}

	else {//  |

		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 buildtree(){// 利用后缀表达式构建表达式树 2、

for(int i=0;i<sf.size();i++){

	if(sf[i]=='0'||sf[i] == '1') {

		tr[++num]={sf[i]-'0',-1,-1};

		sta.push(num);

	}

	else{//最后将剩下的ops全部移到sf中。

		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){// 通过dfs (深搜)来访问表达式树并计算。

if(tr[u].v==0||tr[u].v==1)return tr[u].v; 

int l=dfs(tr[u].l);//判断是否会短路

if(l==0&&tr[u].v == 2) {// 0&

	ans1++;

	return 0;

}

if(l==1&&tr[u].v == 3) {// 1|

	ans2++;

	return 1;

}

int r=dfs(tr[u].r); 

return r; // 不短路，结果取决于右值  1& || 0|

}

int main(){//简单主程序

cin>>s;

change(); // 把中缀表达式转后缀

buildtree(); // 利用后缀表达式构建表达式树

cout<<dfs(num)<<'\n'; // 后缀表达式下，从根 dfs

cout<<ans1<<' '<<ans2;//输出 

return 0;

}