정규형

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

요약
홀수 레벨은 AND, 짝수 레벨은 OR인 완전 괄호화 AND/OR 트리를 여러 개의 긴 입력에 대해 평가한다.
난이도

보통10점 중 5점

유형
트리, 구현, 재귀, 문자열
정답자
아직 제출이 없습니다

문제

모든 불리언 식은 논리합 정규형(DNF, Disjunctive Normal Form) 또는 논리곱 정규형(CNF, Conjunctive Normal Form)으로 나타낼 수 있다. 이 문제에서 DNF는 하나 이상의 CNF 식을 OR로 연결한 식이고, CNF는 하나 이상의 DNF 식을 AND로 연결한 식이다.

AND/OR 트리는 이러한 DNF 또는 CNF 불리언 식을 트리 형태로 표현한 것이다. DNF와 CNF는 서로를 부분식으로 포함하므로, 어떤 서브 트리가 트리에서 몇 번째 레벨에 있는지만 알면 그 서브 트리가 AND 트리인지 OR 트리인지 알 수 있다.

레벨은 트리의 맨 위(루트)를 레벨 1로 하여 아래로 한 단계 내려갈 때마다 1씩 증가한다. 예를 들어 식 (A∨(B∧C))∧(D∨E)(A \lor (B \land C)) \land (D \lor E) 를 트리로 나타내면 루트인 레벨 1과 레벨 3은 AND 트리이고 레벨 2는 OR 트리이다. 즉 홀수 레벨은 AND 트리, 짝수 레벨은 OR 트리이다.

AND/OR 트리가 주어졌을 때, 그 식의 값을 계산하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄이며, 길이는 32,000글자를 넘지 않는다.

각 트리는 다음과 같은 형식으로 주어진다.

(E1 E2 ... En)

여기서 항상 n>0n > 0 이며, 각 EiE_i 는 값이 참인 리터럴 T, 값이 거짓인 리터럴 F, 또는 같은 형식으로 주어지는 부분식(서브 트리) 중 하나이다.

트리의 맨 위(레벨 1, 루트)는 AND 트리이다. 입력의 마지막 줄에는 () 가 주어지며, 이는 입력의 끝을 나타낸다.

출력

각 테스트 케이스마다 다음 형식으로 한 줄씩 출력한다.

k. E

여기서 kk 는 테스트 케이스의 번호(1부터 시작)이고, EE 는 입력으로 주어진 식의 값으로 true 또는 false 이다.

예제1

  1. 예제 1

    입력
    ((F(TF))(TF))
(TFT)
((TFT)T)
()
    예상 출력
    1. false
2. false
3. true