题目描述
逻辑表达式是计算机科学中的重要概念和工具,包含逻辑值、逻辑运算、逻辑运算优先级等内容。在一个逻辑表达式中,元素的值只有两种可能:00(表示假)和 11(表示真)。元素之间有多种可能的逻辑运算,本题中只需考虑如下两种:“与”(符号为 &)和“或”(符号为|)。其运算规则如下:
0&0=0&1=1&0=0,1&1=1;
0|0=0,0|1=1|0=1|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计入一处“短路”。
输入格式
输入共一行,一个非空字符串s表示待计算的逻辑表达式。
输出格式
输出共两行,第一行输出一个字符0或1,表示这个逻辑表达式的值;第二行输出两个非负整数,分别表示计算上述逻辑表达式的过程中,形如a&b和a|b的“短路”各出现了多少次。
样例数据
input
0&(1|0)|(1|1|1&0)
output
1
1 2
数据规模与约定
时间限制:$1 \text{s}$
空间限制:$256 \text{MB}$