这道题是j组第三题——逻辑表达式

第一步，将表达式进行转换（中序表达式转后序表达式）

需用到vector，栈and字符串中序表达式即正常方式表达后序表达式即不需要括号表达

第二步，建表达式树

需要结构体数组and栈

第三步，dfs

大家都知道，不赘述了（~~应该不用吧） ~~

AC Code

#include<vector>
#include<stack>
using namespace std;
string s;
const int N=1e6+5;
struct Node{
	int v,l,r;
}tr[N];
int num,ans1,ans2;
stack<char>ops;
stack<int>sta;
vector<char>sf;
void change()
{
	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());
				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 build(){
	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{
			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);
	if(l==0&&tr[u].v==2){
		ans1++;
		return 0;
	}
	if(l==1&&tr[u].v==3){
		ans2++;
		return 1;
	}
	int r=dfs(tr[u].r);
	return r;
}
int main(
{
	cin>>s;
	change();
	build();
	cout<<dfs(num)<<endl;
	cout<<ans1<<" "<<ans2;
	return 0;
})