题意分析
给定一个 bool 运算表达式，求其值和两种布尔短路在运算途中发生的次数。
首先，对于这种让你“计算表达式”的题目，一般来讲就是栈、递归。
然而我们看到这之中，“运算优先级”就十分的烦人。
我们可以考虑手动给给定的表达式添加括号，也可以考虑转后缀或前缀表达式进行运算。
我们同样可以使用栈来模拟， & 直接算，而 | 在有括号时才计算。
在本文，给出一种基于递归的的做法。
处理策略
（不会有人不知道 $\and$ 是与，$\or$ 是或吧……）
对于给定表达式 $a$，我们一定可以将其拆分为若干表达式 $a[l_1,r_1],a[l_2,r_2],a[l_3,r_3],\cdots,a[l_p,r_p]$。
我们定义 $dfs(l,r)$ 表示 $a[l,r]$ 的值。
比如说对于表达式 1&(2|3)，$a[1,7]$ 就是 1&(2|3)，$a[4,6]$ 就是 2|3。
对应地，$dfs(1,7)=dfs(1,1)\and dfs(4,6)=1\and(2\or3)=1$。
那么，我们考虑 $dfs(l,r)$ 内部怎么写。
首先，当 $l,r$ 满足 $l=r$ 时，无疑 $dfs(l,r)=a_l=a_r$。（无需考虑 $a_l$ 是不是符号，是符号的话不会调用）
记 $f_1[i],f_2[i]$ 分别为离 $a_i$ 最近的同一层括号内 | 和 & 的位置。
那么当我们调用 $dfs(l,r)$ 时，先判断 $f_1[r],f_2[r]$ 的值是否在 $[l,r]$ 内，如果在，就说明需要进行计算。
以 $\large a_{f_1[r]}$ 为例：
我们将 $a[l,r]$ 拆分为两个表达式：$a[l,f_1[r]-1]\or a[f_1[r]+1,r]$，那么对应地就有递归式 $dfs(l,r)=dfs(l,f_1[r]-1)\or dfs(f_1[r]+1,r)$。
这样我们就可以递归求解。（其实就是形如 $a\and b$ 和 $a\or b$）。
如果 $f_1[r],f_2[r]$ 的值都不合法，两种情况：
-
$l=r$。
-
$a[l,r]$ 是形如 $(s)$ 的形式，其中 $s$ 为合法表达式；那么显然此时有 $dfs(l,r)=dfs(l+1,r-1)$。
但是，注意不要将此条件放在 $dfs(l,r)$ 的开始的同时判定条件写为
if(a[l]=='('&&a[r]==')')。因为，$a[l,r]$ 同样也能形如 $(b)\and(c)$。
AC 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
const int N=1e6;
//1:|,2:&
int n,cnt1,cnt2,pl1[N+1],pl2[N+1],f1[N+1],f2[N+1];
char a[N];
void pre(){
static int pl1[N+1],pl2[N+1];
int pl=0;
for(int i=1;i<=n;i++){
switch(a[i]){
case '(':
pl++;
break;
case ')':
pl--;
break;
case '|':
pl1[pl]=i;
break;
case '&':
pl2[pl]=i;
break;
}//i之前最近的 |和 &(同层括号内)
f1[i]=pl1[pl];
f2[i]=pl2[pl];
}
}
bool dfs(int l,int r){
if(l==r)return a[l]^48;
//a|b
if(f1[r]>l){
bool ans=dfs(l,f1[r]-1);
if(ans){
cnt2++;
return true;
}return dfs(f1[r]+1,r);
}//a&b
else if(f2[r]>l){
bool ans=dfs(l,f2[r]-1);
if(!ans){
cnt1++;
return false;
}return dfs(f2[r]+1,r);
}//(a) -> a
if(a[l]=='('&&a[r]==')')return dfs(l+1,r-1);
}
int main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
scanf("%s",a+1);
n=strlen(a+1);
pre();
int ans=dfs(1,n);
printf("%d\n%d %d\n",ans,cnt1,cnt2);
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
