这题有两个方法：

1.表达式树

第一步：转化为表达式树

先转化为后缀表达式：

定义一个列表存储 vector sf,用一个栈 stack ops存储符号

• 数字直接加入 sf
• 遇到 & 检查 ops的第一个是不是 &，如果是（a&b &）就将 *&*添加到 sf（ab &）,否则将 & 添加到 ops(a|b& -> abc&|)
• 遇到 | 检查 ops的第一个是不是运算符，如果是（a&b |）就将 ops.top添加到 sf（ab &）,否则将 | 添加到 ops(a| -> ab|)
• 如果遍历完了，将ops清空（加入sf）（a|b&c -> abc&|）
• 括号相当于一个表达式，遇到 ( 存入ops
• 遇到 ) 相当于遍历完了，将ops清理直到左括号（加入sf）（a&(b|c&d）-> abcd&| &)

for(int i=0;i<s.size();i++)
	{
		if(s[i]=='1'||s[i]=='0')sf.push_back(s[i]);
		else if(s[i]=='(')ops.push('(');
		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();
	}

转化为表达式树：

先定义变量

struct node
{
	int v,l,r;//值，左节点id,右节点id 
}tr[1000005];
int num,a1,a2;//num表示tr用了几个子节点 a1 a2:dfs用
stack<int> sta;//后缀栈

遍历 sf：

• 无论是数字还是符号，都要放进tr[num],压入sta
• 数字是叶子节点，l=r=-1
• 符号的叶子从sta取出

for(int i=0;i<sf.size();i++)
	{
		//cout << sf[i];
		if(sf[i]=='1'||sf[i]=='0')
		{
			tr[++num]={sf[i]-'0',-1,-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);
		}
	}

第二步：dfs求解

dfs(u)表示节点u的值：

• tr[u]是数字直接返回
• 不然就int l=dfs(tr[u].l)再判断有没有短路,有短路就将a1或a2++;
• 没有短路就返回dfs(tr[u].r)

最后调用dfs(num)得出答案

#include <iostream>
#include <vector>
#include <stack>
using namespace std;
struct node
{
	int v,l,r;//值，左节点id,右节点id 
}tr[1000005];
int num,a1,a2;

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)//0&x
	{
		a1++;
		return 0;
	}
	if(l==1&&tr[u].v==3)//1|x
	{
		a2++;
		return 1;
	}
	return dfs(tr[u].r);
}

int main()
{
	string s;
	cin >> s;
	//树：中缀表达式转化为后缀表达式（栈） 
    vector<char> sf;
	stack<char> ops;
	stack<int> sta;
	//数字pushback->sf
	//'('pushback->ops 这样右括号配对最近的左括号 
	//')'->ops.top pushback->sf, ops.pop()
	//'&' || '|' ops!=empty&&top=='&'->push->sf
	//    else push->pos
	//最后ops.top->sf 
	for(int i=0;i<s.size();i++)
	{
		if(s[i]=='1'||s[i]=='0')sf.push_back(s[i]);
		else if(s[i]=='(')ops.push('(');
		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();
	}

	for(int i=0;i<sf.size();i++)
	{
		//cout << sf[i];
		if(sf[i]=='1'||sf[i]=='0')
		{
			tr[++num]={sf[i]-'0',-1,-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);
		}
	}

	cout << dfs(num) << endl;
	cout << a1 << " " << a2;
	return 0;
}

2.模拟

模拟就简单了，只要逐步计算并且在合适的时候 打开曲速 短路跳过

bool val;//值
int a1,a2,off;//off表示短路状态

• 前面我们知道，只要不是短路，算式的结果就是右边的值(0 -> 0 0|1 -> 1 0|1&0 -> 0)

  if(str[i]=='1')val=1;
  if(str[i]=='0')val=0;
  

• 在没有短路的情况下，如果是符号就判断有没有短路

  if(val==0&&str[i]=='&')
  {
  	off=1;
  	a1++;
  }
  if(val==1&&str[i]=='|')
  {
  	off=2;
  	a2++;
  }
  

  ---

短路跳过

• 若遇到左括号 ( ,就跳过括号组

  if(str[i]=='(')
  {
  	int x=1;
  	while(x)
  	{
  		i++;
  		if(str[i]=='(')
  		{
  			x++;
  		}
  		if(str[i]==')')x--;
  	}
  }
  

• 或跳过(off==0)会一直到结束（前面说过，右括号等同于结束）

  else if(str[i]==')')
  {
  	off=0;
  }
  

• 与跳过(off==0)碰到 | 会结束

  else if(off==1&&str[i]=='|')
  {
  	off=0;
  }
  

• 跳过碰到同级（不在子括号里）相同符号算两个

  else if(off==1&&str[i]=='&')
  {
  	a1++;
  }
  else if(off==2&&str[i]=='|')
  {
  	a2++;
  }
  

  ---

上代码

#include <iostream>
using namespace std;
bool val;
int a1,a2,off;

int main()
{
	string str;
	cin >> str;

	for(int i=0;i<str.size();i++)
	{
		if(off==0)
		{
			if(str[i]=='1')val=1;
			if(str[i]=='0')val=0;
			if(val==0&&str[i]=='&')
			{
				off=1;
				a1++;
			}
			if(val==1&&str[i]=='|')
			{
				off=2;
				a2++;
			}
		}
		else
		{
			if(str[i]=='(')
			{
				int x=1;
				while(x)
				{
					i++;
					if(str[i]=='(')
					{
						x++;
					}
					if(str[i]==')')x--;
				}
			}
			else if(off==1&&str[i]=='|')
			{
				off=0;
			}
			else if(str[i]==')')
			{
				off=0;
			}
			else if(off==1&&str[i]=='&')
			{
				a1++;
			}
			else if(off==2&&str[i]=='|')
			{
				a2++;
			}
		}
	}
	cout<<val<<endl<<a1<<" "<<a2;
	return 0;
}