思路： (1)将中缀表达式转后缀表达式； (2)转化成表达式树； (3)dfs访问。

用vector装后缀表达式，用栈装表达式内的符号（如：'(' '&'等），再用一个字符串（string) 存最初输入的表达式(中缀)。 vector sf; stack ops;

★符号优先级为 () > & > | ；

(1) 哪些符号入栈？入栈顺序是？ 1、如果为数字(0或1)，存入sf； 2、如果为 ( ，压入ops； 3、如为 ) ，将ops中与其配对的 ( （也就是最近的'('）之上的运算符全部输出并加到sf，最后删掉配对的 ( （记住右括号不压入栈）；

4、如为&(与)，从栈顶弹出所有运算符&加入sf直到碰见 ( 或 | 或栈空； 5、如为 | (或)，从栈顶弹出所有&和|加入sf直到碰见 ( 或 | 或栈空； (接下来重复上面几点直到ops为空）

(2) 转化表达式树 建立结构体（node）存放每个节点的值v,及左子树方位l和右子树方位r，再建立栈sta缓存节点位置。 所有非叶节点都为运算符对应的值(我们设&=2，|=3)。

(3)dfs

1、叶节点返回值(v)； 2、非叶节点通过左子树判断是否为短路(详见题目)，如出现短路，返回左子树值。

具体代码： #include<bits/stdc++.h> using namespace std; const int N=1e6+10; vector sf; stack ops; stack sta; struct node{ int v,l,r; }tr[N]; int num,ans1,ans2; string s;

void change(){//中缀转后缀 for(int i=0;i<s.size();i++){ if(s[i]'0' || s[i]'1') sf.push_back(s[i]);//插入sf else if(s[i]'('){ ops.push(s[i]);//插入栈 }else if(s[i]')'){ while(!ops.empty() && ops.top()!='('){ sf.push_back(ops.top());//(放入sf尾(?)) 一直输出到sf直到遇到左括号'(' 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].v0 || tr[u].v1){ 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);//如果没走结果取决于r(后面的数） 
return r;

}

int main(){ cin>>s; change(); build(); //cout<<1; cout<<dfs(num)<<endl; cout<<ans1<<" "<<ans2<<endl; return 0; }