P8815 [CSP-J 2022] Logical Expression

Logical expressions are important concepts and tools in computer science. They involve logical values, logical operations, and operation precedence. In a logical expression, each element can only take one of two values: $0$ (false) and $1$ (true). There are several possible logical operations between elements. In this problem, you only need to consider the following two: “AND” (symbol `&`) and “OR” (symbol `|`). Their rules are: $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$。 A logical expression may also contain parentheses. When evaluating, the part inside parentheses is evaluated first. When `&` and `|` appear together, `&` has higher precedence than `|`. When the same operation appears consecutively, evaluate from left to right. For example, the evaluation order of the expression `0|1&0` is equivalent to `0|(1&0)`. The evaluation order of `0&1&0|1` is equivalent to `((0&1)&0)|1`. In addition, in some compilers for languages such as C++, evaluating logical expressions uses a “short-circuit” strategy: in an expression of the form `a&b`, it evaluates `a` first. If $a = 0$, then the whole expression must be $0$, so there is no need to evaluate `b`. Similarly, in an expression of the form `a|b`, it evaluates `a` first. If $a = 1$, then the whole expression must be $1$, so there is no need to evaluate `b`. Now you are given a logical expression. You need to compute its value, and count how many times each of the two types of “short-circuit” occurs during evaluation. Note that if a short-circuit is inside a part that is short-circuited at an outer level, then it is not counted. For example, in `1|(0&1)`, although `0&1` would be a short-circuit, the outer `1|(0&1)` is itself a short-circuit, so there is no need to evaluate `0&1`, and thus `0&1` should not be counted as a short-circuit.

The input contains one line: a non-empty string $s$ representing the logical expression to be evaluated.

Output two lines. The first line outputs a character `0` or `1`, representing the value of the logical expression. The second line outputs two non-negative integers, representing the number of “short-circuits” of the forms `a&b` and `a|b` that occur during the evaluation of the expression.

**[Sample Explanation \#1]** The evaluation process of the logical expression is as follows. The comment on each line explains the process from the previous line: ```plain 0&(1|0)|(1|1|1&0) =(0&(1|0))|((1|1)|(1&0)) //use parentheses to show the evaluation order =0|((1|1)|(1&0)) //evaluate the leftmost &, this is one “short-circuit” of the form a&b =0|(1|(1&0)) //then evaluate the middle |, this is one “short-circuit” of the form a|b =0|1 //then evaluate the middle |, this is one “short-circuit” of the form a|b =1 ``` **[Sample \#3]** See `expr/expr3.in` and `expr/expr3.ans` in the attachment. **[Sample \#4]** See `expr/expr4.in` and `expr/expr4.ans` in the attachment. **[Constraints]** Let $\lvert s \rvert$ be the length of the string $s$. For all testdata, $1 \le \lvert s \rvert \le {10}^6$. It is guaranteed that $s$ contains only the characters `0`, `1`, `&`, `|`, `(`, `)` and is a valid logical expression. It is guaranteed that there are no extra spaces at the beginning, in the middle, or at the end of the input string. It is guaranteed that there is no repeated parenthesis nesting in $s$ (i.e., there is no substring of the form `((a))`, where `a` is a valid logical expression). | Test Point ID | $\lvert s \rvert \le$ | Special Condition | |:-:|:-:|:-:| | $1 \sim 2$ | $3$ | None | | $3 \sim 4$ | $5$ | None | | $5$ | $2000$ | 1 | | $6$ | $2000$ | 2 | | $7$ | $2000$ | 3 | | $8 \sim 10$ | $2000$ | None | | $11 \sim 12$ | ${10}^6$ | 1 | | $13 \sim 14$ | ${10}^6$ | 2 | | $15 \sim 17$ | ${10}^6$ | 3 | | $18 \sim 20$ | ${10}^6$ | None | Where: Special Condition 1: it is guaranteed that there is no character `&` in $s$. Special Condition 2: it is guaranteed that there is no character `|` in $s$. Special Condition 3: it is guaranteed that there are no characters `(` and `)` in $s$. **[Hint]** A formal definition of a “valid logical expression” is given below: - The strings `0` and `1` are valid. - If the string `s` is valid, and `s` is not of the form `(t)` (where `t` is valid), then the string `(s)` is also valid. - If the strings `a` and `b` are both valid, then the strings `a&b` and `a|b` are both valid. - All valid logical expressions can be generated by the methods above. Translated by ChatGPT 5