这道题是CSP-J的T3

我会详细的写出解题步骤，尽量让所有人看懂 题面我就不放出来了 那么这道题思路如下↓↓↓

第一步，把中缀表达式转换成后缀表达式

定义

中缀表达式就是正常人使用的表达式，包含括号、数字/变量和运算符，例如(a+b)*(b-c)-(d-c) 而后缀表达式不需要括号先是数字/变量，遇到运算符后，取出前两个值计算，将计算结果重新存入算式，代替原来的两个数字/变量和运算符，将中缀表达式的例子转换后就是ab+bc-*dc--

需求

首先声明一个vectorsf用来装后缀表达式，一个栈ops用来缓存符号，一个字符串s存输入的表达式 我们要让在同一个维度(括号)内,保持&在栈的位置比|高

规则

1. 优先级:()=1，&=2，|=3
2. 如果是0或1，直接输出到sf中
3. 如果是(，存入ops
4. 如果是)，就将ops中位于最近的(之上的所有符号输出进sf，再删除(
5. 如果是&，就从栈顶输出优先级≤&的逻辑运算符到sf(只有&)直到栈空或者遇到(或者遇到|
6. 如果是|，就从栈顶输出优先级≤|的逻辑运算符到sf(有&和|)直到栈空或者遇到(

注意，最后ops中还剩下一些运算符，要将其全部输出到sf 完成了转换部分，就要为后缀表达式建立表达式树

第二步，建立表达式树

我们需要声明一个结构体数组tr用于存放树的每个节点的值v,左子树位置l和右子树位置r，声明一个栈sta来缓存每个节点的位置

所有叶子节点的值都为其对应的数字，用于计算 所有非叶子节点的值都为其对应运算符的值，也就是&=2，|=3 所有叶子节点的左子树和右子树位置都为-1因为叶子结点根本就没有左子树和右子树

第三步，dfs

我们通过dfs ~~~~(不会有人不知道深度优先搜索吧)~~~~来访问表达式树

dfs规则

1. 叶子结点直接返回它的值v
2. 非叶子节点递归获取子树的值来计算
3. 非叶子节点通过左子树判断是否出现短路，如果出现短路，直接返回左子树的值，跳过右子树

第四步,ACCODE

现在前三个部分的思路都清楚了，我们直接上代码:

#include<bits/stdc++.h>
using namespace std;
string s;
struct st{
	int v,l,r;
}tr[1000001];
int num,ans1,ans2;//num是节点数量,ans1和ans2统计两种短路 
vector<char>sf;//后缀表达式 
stack<char>ops;//符号缓存 
stack<int>sta;//节点位置缓存 
void change()//中缀to后缀 
{
	for(int i=0;i<s.size();i++)
	{
		if(s[i]=='1'||s[i]=='0')//数字直接放入sf 
		{
			sf.push_back(s[i]);
		}else if(s[i]=='(')//左括号入栈 
		{
			ops.push('(');
		}else if(s[i]==')')//遇到右括号就将运算符输出到sf直到遇到左括号 
		{
			while(ops.top()!='(')
			{
				sf.push_back(ops.top());
				ops.pop();
			}
			ops.pop();//将无用的左括号出栈 
		}else if(s[i]=='&')//遇到&就将前面的&输出到sf直到栈空或者遇到其他符号 
		{
			while(!ops.empty()&&ops.top()=='&')
			{
				sf.push_back(ops.top());
				ops.pop();
			}
			ops.push('&');//将当前的&入栈 
		}else//只剩下|的情况了,将前面的&和|输出到sf直到栈空或者遇到左括号 
		{
			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]=='1'||sf[i]=='0')//数字存入叶子节点，值就是sf中对应的值 
		{
			tr[++num]=(st){sf[i]-'0',-1,-1};//没有子树 
			sta.push(num);//将节点位置入栈 
		}else//运算符作为非叶子节点要获取两个子节点 
		{
			int v,r,l;
			r=sta.top(),sta.pop();//从栈顶取出两个节点作为子节点 
			l=sta.top(),sta.pop();
			v=(sf[i]=='&'?2:3);//三目运算符,如果是&,值为2,否则为3 
			tr[++num]=(st){v,l,r};
			sta.push(num);//将节点位置入栈 
		}
	}
}
int dfs(int b)//开始运算 
{
	if(tr[b].v==1||tr[b].v==0)//如果是叶子节点,那么返回节点的值 
	{
		return tr[b].v;
	}
	int l=dfs(tr[b].l);//递归获取左子树返回值 
	if(l==0&&tr[b].v==2)//如果是&且满足&的短路条件,短路加一并且直接返回 
	{
		ans1++;
		return 0;
	}
	if(l==1&&tr[b].v==3)//这里是判断|的短路 
	{
		ans2++;
		return 1;
	}
	int r=dfs(tr[b].r);//获取右子树返回值 
	return r;//不满足短路,那么返回值为右子树的返回值 
}
int main()
{
	cin>>s;
	change();//中缀->后缀 
	build();//建立表达式树 
	cout<<dfs(num)<<endl;//从根节点进入dfs,dfs后的返回值就是最终结果 
	cout<<ans1<<" "<<ans2;//注意输出必须分成两次，否则短路的统计输出为0 
	return 0;
}

以上是本蒟蒻的代码，希望您能看懂，如果有错，欢迎指出，有问题欢迎提问