Introduction to Digital Circuits

Time limit1sMemory limit128 MB

Summary

Parse three-valued logic expressions over P, Q, R and count how many of the 27 assignments make the expression evaluate to 2.

Level: Medium5 of 10
Topics: Recursion, Implementation, Brute force, String
Solved: No attempts yet

Problem

Three-valued logic is a logic system whose truth values are "false", "unknown", and "true". In this system "false" has the value 0, "unknown" has the value 1, and "true" has the value 2.

The unary operator - denotes NOT, and the binary operators * and + denote AND and OR respectively. The three operators are defined as follows.

NOT -X = 2 - X

X	`-X`
0	2
1	1
2	0

AND (X*Y) = min(X, Y)

AND	1	2
0	0	0
1	1	1
2	1	2

OR (X+Y) = max(X, Y)

OR	0	1	2
0	0	1	2
1	1	1	2
2	2	2	2

Let P, Q, R be variables that take three-valued logic values. Given an expression, write a program that counts the number of ordered triples (P, Q, R) that make the value of the expression equal to 2. An expression has one of the following forms (X and Y denote expressions).

Constant: 0, 1, 2
Variable: P, Q, R
NOT: -X
AND: (X*Y)
OR: (X+Y)

AND and OR are always enclosed in parentheses.

For example, given (P*Q), the triples (P, Q, R) that make the value equal to 2 are (2, 2, 0), (2, 2, 1), and (2, 2, 2) — 3 in total.

Input

The input consists of several test cases. Each test case is a single line containing one expression, made up only of the characters 0, 1, 2, P, Q, R, -, *, +, (, ).

The BNF grammar of an expression is as follows.

<formula> ::= 0 | 1 | 2 | P | Q | R |
              -<formula> | (<formula>*<formula>) | (<formula>+<formula>)

The length of a single expression does not exceed 80 characters. The last line contains a single ., which marks the end of the input.

Output

For each test case, print the number of ordered triples (P, Q, R) that make the value of the given expression equal to 2, one per line.

Examples1

Example 1

Input

(P*Q)
(--R+(P*Q))
(P*-P)
2
1
(-1+(((---P+Q)*(--Q+---R))*(-R+-P)))
.

Expected output