디지털 회로 개론

시간 제한1초메모리 제한128 MB

요약

P, Q, R에 대한 3진 논리식을 파싱하고, 27가지 대입 중 식의 값이 2가 되는 경우의 수를 센다.

문제

3진 논리는 논리값으로 "false", "unknown", "true"를 갖는 논리 체계이다. 이 체계에서 "false"는 0, "unknown"은 1, "true"는 2의 값을 갖는다.

단항 연산자 -는 NOT을, 이항 연산자 *와 +는 각각 AND와 OR을 나타낸다. 세 연산자는 다음과 같이 정의된다.

NOT -X = 2 - X

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

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

P, Q, R을 3진 논리값을 갖는 변수라고 하자. 식이 주어졌을 때, 식의 값을 2로 만드는 순서쌍 (P, Q, R)의 개수를 구하는 프로그램을 작성하시오. 식은 다음 중 하나의 형태를 갖는다. (X와 Y는 식을 의미한다.)

AND와 OR은 항상 괄호로 둘러싸여 있다.

예를 들어 (P*Q)가 주어지면, 식의 값을 2로 만드는 (P, Q, R)은 (2, 2, 0), (2, 2, 1), (2, 2, 2)의 3가지이다.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 한 줄에 하나의 식으로 주어지며, 식은 문자 0, 1, 2, P, Q, R, -, *, +, (, )로만 이루어진다.

식의 BNF 문법은 다음과 같다.

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

한 식의 길이는 80글자를 넘지 않는다. 마지막 줄에는 . 하나만 주어지며, 이는 입력의 끝을 의미한다.

각 테스트 케이스마다, 주어진 식의 값을 2로 만드는 순서쌍 (P, Q, R)의 개수를 한 줄에 하나씩 출력한다.

예제 1

입력

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

예상 출력