2022 CSP-J 逻辑表达式

/*
模拟题，对应我们的表达式建立树，表达式树
遍历计算两种短路次数，先计算左子树
如果短路那么我们剩下的右子树就不需要计算
栈：
1.储存表达式树的节点编号/值
2.运算符
一个括号就是一个树，全部算是一个整体
括号内部的值满足同优先级从左到右
从结点编号取出两个元素，运算符栈取出符号
连边建树：
1.遇到左括号，直接入栈
2.遇到右括号，出栈，一直出栈到对应的左括号
3.遇到数字，建立叶子节点
4.遇到运算符，循环查看栈顶是否优先级高于
当前运算符，处理，把运算符入栈
5.处理运算符栈最后剩余的运算
*/

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 5;
int ck;
char s[N],a[N];//节点信息
int rk[200];//优先级
stack<int> num;//表达式树的编号
stack<char> op;//符号
int son[N][2];//左右两个儿子 
void cz(){//出栈过程 
	//取出x和y
	int y=num.top();num.pop();
	int x=num.top();num.pop();
	a[++ck]=op.top();op.pop();//取出优先级
	son[ck][0]=x;
	son[ck][1]=y;
	num.push(ck);
}
int cnt1,cnt2;
int dfs(int u){
	if(a[u]=='0') return 0;
	if(a[u]=='1') return 1;
	if(a[u]=='&'){
		if(dfs(son[u][0])==0){
			cnt1++;
			return 0;
		}
		return dfs(son[u][1]);
	}
	//当1的是|的短路 
	if(dfs(son[u][0])==1){
		cnt2++;
		return 1;
	}
	return dfs(son[u][1]); 
}
int main(){
	rk['|']=1;rk['&']=2;
	scanf("%s",s+1);//输入 
	int n=strlen(s+1);//求出长度
	for(int i=1;i<=n;i++){
		//遇到左括号，直接入栈
		if(s[i]=='(')op.push(s[i]);
		//遇到右括号，出栈，一直出栈到对应的左括号
		else if(s[i]==')'){
			while(op.top()!='('){
				cz();
			}
			op.pop();
		}
		//遇到与运算
		else if(s[i]=='&'){
			while(op.size()>0&&rk[op.top()]>=rk[s[i]]){
				cz();
			}
			op.push(s[i]);
		} 
		else if(s[i]=='|'){
			while(op.size()>0&&rk[op.top()]>=rk[s[i]]){
				cz();
			}
			op.push(s[i]);
		}
		else{
			a[++ck]=s[i];
			num.push(ck); 
		} 
	}
	while(op.size()){
		cz();
	}
	int ans=dfs(ck);
	cout<<ans<<"\n"<<cnt1<<" "<<cnt2<<endl; 
	return 0;
}