2390. How can I satisfy thee? Let me count the ways...

单点时限: 2.0 sec

内存限制: 256 MB

Three-valued logic is a logic system that has, in addition to “true” and “false”, “unknown” as a valid value. In the following, logical values “false”, “unknown” and “true” are represented by 0, 1 and 2 respectively.

Let “-” be a unary operator (i.e. a symbol representing one argument function) and let both “*” and “+” be binary operators (i.e. symbols representing two argument functions). These operators represent negation (NOT), conjunction (AND) and disjunction (OR) respectively. These operators in three-valued logic can be defined in Table C-1.

Let P, Q and R be variables ranging over three-valued logic values. For a given formula, you are asked to answer the number of triples (P,Q,R) that satisfy the formula, that is, those which make the value of the given formula 2. A formula is one of the following form (X and Y represent formulas).

  • Constants: 0, 1 or 2
  • Variables: P, Q or R
  • Negations: -X
  • Conjunctions: (X*Y)
  • Disjunctions: (X+Y)

Note that conjunctions and disjunctions of two formulas are always parenthesized.

For example, when formula (P*Q) is given as an input, the value of this formula is 2 when and only when (P,Q,R) is (2,2,0), (2,2,1) or (2,2,2). Therefore, you should output 3.


The input consists of one or more lines. Each line contains a formula. A formula is a string which consists of 0, 1, 2, P, Q, R, -, *, +, (, ). Other characters such as spaces are not contained. The grammar of formulas is given by the following BNF.

 ::= 0 | 1 | 2 | P | Q | R |

- | (*) | (+)

All the formulas obey this syntax and thus you do not have to care about grammatical errors. Input lines never exceed 80 characters.

Finally, a line which contains only a “.” (period) comes, indicating the end of the input.


You should answer the number (in decimal) of triples (P,Q,R) that make the value of the given formula 2. One line containing the number should be output for each of the formulas, and no other characters should be output.



5 人解决,6 人已尝试。

5 份提交通过,共有 9 份提交。

6.6 EMB 奖励。

创建: 11 年,4 月前.

修改: 2 年,6 月前.

最后提交: 9 年,1 月前.

来源: Japan 2008 Domestic