逻辑表达式是计算机科学中的重要概念和工具,包含逻辑值、逻辑运算、逻辑运算优先级等内容。
在一个逻辑表达式中,元素的值只有两种可能:
0
(表示假)和
1
(表示真)。元素之间有多种可能的逻辑运算,本题中只需考虑如下两种:“与”(符号为 &
)和“或”(符号为 |
)。其运算规则如下:
0 \mathbin{\&} 0 = 0 \mathbin{\&} 1 = 1 \mathbin{\&} 0 = 0
,
1 \mathbin{\&} 1 = 1
;
0 \mathbin{|} 0 = 0
,
0 \mathbin{|} 1 = 1 \mathbin{|} 0 = 1 \mathbin{|} 1 = 1
。
在一个逻辑表达式中还可能有括号。规定在运算时,括号内的部分先运算;两种运算并列时,&
运算优先于 |
运算;同种运算并列时,从左向右运算。
比如,表达式 0|1&0
的运算顺序等同于 0|(1&0)
;表达式 0&1&0|1
的运算顺序等同于 ((0&1)&0)|1
。
此外,在 C++ 等语言的有些编译器中,对逻辑表达式的计算会采用一种“短路”的策略:在形如 a&b
的逻辑表达式中,会先计算 a
部分的值,如果
a = 0
,那么整个逻辑表达式的值就一定为
0
,故无需再计算 b
部分的值;同理,在形如 a|b
的逻辑表达式中,会先计算 a
部分的值,如果
a = 1
,那么整个逻辑表达式的值就一定为
1
,无需再计算 b
部分的值。
现在给你一个逻辑表达式,你需要计算出它的值,并且统计出在计算过程中,两种类型的“短路”各出现了多少次。需要注意的是,如果某处“短路”包含在更外层被“短路”的部分内则不被统计,如表达式 1|(0&1)
中,尽管 0&1
是一处“短路”,但由于外层的 1|(0&1)
本身就是一处“短路”,无需再计算 0&1
部分的值,因此不应当把这里的 0&1
计入一处“短路”。