2022 CSP-J 第二轮 T3｜逻辑表达式

一、完整题目

题目描述

给定一个布尔表达式，其中只包含：

• 数字 0 和 1；
• 与运算符 &；
• 或运算符 |；
• 左、右括号 (、)。

运算优先级为：括号最高，& 高于 |；相同优先级的运算从左到右进行。表达式一定合法。

求值时采用短路规则：

• 对 a&b，若左侧 a 的值为 0，结果已经确定为 0，右侧 b 不再求值，称这里发生一次 & 的短路；
• 对 a|b，若左侧 a 的值为 1，结果已经确定为 1，右侧 b 不再求值，称这里发生一次 | 的短路。

如果某一整段表达式因为外层运算短路而没有被求值，那么这段表达式内部原本可能发生的短路也不计入答案。

请输出整个表达式的值，以及实际求值过程中 & 和 | 分别发生短路的次数。

输入格式

从文件 expr.in 中读入数据。

输入仅一行，一个不含空格的合法布尔表达式 s。

输出格式

输出到文件 expr.out 中。

第一行输出表达式的值。

第二行输出两个整数，依次表示 & 的短路次数和 | 的短路次数。

样例 1

0&(1|0)|(1|1|1&0)

1
1 2

样例 2

(0|1&0|1|1|(1|1))&(0&1&(1|0)|0|1|0)&0

0
2 3

数据范围与测试点

所有数据保证表达式合法、只含上述字符、没有多余的连续套括号，并且 1≤|s|≤10^6。

| 测试点 | |s| | 特殊性质 | |:---:|:---:|:---| | 1～2 | ≤3 | 无 | | 3～4 | ≤5 | 无 | | 5 | ≤2000 | 不含 & | | 6 | ≤2000 | 不含 | | | 7 | ≤2000 | 不含括号 | | 8～10 | ≤2000 | 无 | | 11～12 | ≤10^6 | 不含 & | | 13～14 | ≤10^6 | 不含 | | | 15～17 | ≤10^6 | 不含括号 | | 18～20 | ≤10^6 | 无 |