시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 6 3 3 50.000%

문제

컴퓨터 프로그램에서는 논리식(logic expression)이 자주 나온다. 논리식의 요소들은 다음과 같다.

  • true 또는 false의 값을 가지고 있는 변수
  • 단항(unary), 이항(binary) 논리 연산자
  • 연산이 수행되는 순서에 영향을 주는 괄호

단항 연산자(Unary operators)는 하나의 변수에서 동작한다. 그에 반해 이항 연산자(Binary operators)는 두 개의 변수에서 동작한다. 일반적인 단항 논리 연산자에는 NOT이 있고, 이항 연산자에는 AND, OR, XOR, NAND, NOR 등이 있다.

하나의 논리 연산자는 ‘진리표(truth table)‘로 정의 될 수 있다. (단항 연산자는 1차원, 이항 연산자에는 2차원) 예를 들어, 아래의 그림을 보자.

논리식의 두 가지 예 :

  1. (x AND (NOT(y NAND z)))
  2. (x OR ((NOT y) XOR z))

이 프로그램의 목적을 위해, 하나의 논리식의 정확한 구조가 문법적으로 정의되어 있다:

<expression> = <variable> | ( <expression> <operator> <expression> ) | ( <operator> <expression>)
<variable> = <lowercase_letter>
<operator> = <uppercase_letter> | <operator> <uppercase_letter>

(여기에서 수직 막대 ‘|’는 ‘or’로 발음되고 문법적으로 정의되어 있다; 이는 실제 표현에서는 표시되지 않는다.) <lowercase_letter>와 <uppercase_letter>은 각각 소문자, 대문자를 의미한다.

일부 경우에서는 모든 변수의 값이 정해지지 않더라도 논리식의 값을 구하는 것이 가능하다. 위의 예시 (1)에서 y = false 이고 x, z의 값은 모른다고 가정해 보아라. 그러면 변수 x, z의 값에 관계없이 주어진 논리식은 false가 되는 것을 확인할 수 있다. 다른 한 편으로는, 예시 (1)에서 x = true, y = true, z는 모른다고 가정해보자. 이 때는 z의 값을 알지 못하면 논리식의 값을 정할 수 없다.

입력

입력은 하나 또는 그보다 많은 test cases를 포함한다. 각각의 test case에서, 입력의 첫 번째 줄에서는 두 개의 양의 정수(100을 초과하지 않음)를 입력 받는다. 하나는 그 case에서 사용될 단항 연산자의 개수이고, 다른 하나는 이항 연산자의 개수이다.

첫 째 줄 다음에는(아래의 두 단락에 설명 되어있는 것처럼) 연산자의 이름과 진리표 형태의 연산자 정의를 입력 받기 위한 여러 줄(several lines)이 따라올 것이다. 연산자의 이름은 20문자를 넘지 않도록 한다. 그리고 다른 연산자의 이름과 중복되지 않도록 한다.

첫째, 각각의 단항 연산자는 두 줄 안에 정의 되도록 한다. : 두 줄 중, 첫 번째 줄에는 연산자의 이름을 입력 받는다; 두 번 째 줄에는 true/false 항목을 두 번 입력 받는다. 이는 진리표를 정의하는 것이다.

단항 연산자의 정의를 마친 이후에, 각각의 이항 연산자는 세 줄 안에 정의 되도록 한다. : 세 줄 중 첫 번째 줄에는 연산자의 이름을 입력받는다; 두 번째, 세 번째 줄에는 true/false 항목을 각각 두 번 씩 입력 받는다. 이 두 줄은 이항 연산자의 진리표를 정의 하는 것이다.

연산자 표 이후에는 위의 문법을 만족하는 유효한 논리식을 입력 받는다. 변수들은 하나 이상의 공백으로 인접한 논리 연산자로부터 구분 될 수 있다. 괄호는 인접한 식의 원소들로부터 공백문자를 이용해 분리될 수도 있고 아닐 수도 있다. 당신은 하나의 식 안에서 한번 이상 나오는 변수가 없다고 가정할지도 모른다. 그 식은 최소 1에서 500을 넘지 않는 문자들로 구성되어 있다.

식 이후의 줄(lines, 0개 이상의 줄)에서는 변수의 값을 표로 입력 받는다. 각각의 줄은 두 가지 형태 중 하나를 갖는다. :

<variable> true
<variable> false

그 표에서 변수는 하나 이상 나타나지 않는다.

각 test case의 끝은 ‘*’로 표시된다. 두 개의 음의 정수를 입력하는 것으로 입력의 끝을 표시할 수 있다.

출력

각 test case의 출력을 한 줄씩 표시한다. case 번호를 표시한다. 그 이후에 문자 true, false, unknown 중 하나를 출력한다.; 위의 설명대로 주어진 식에 적합한 것이 출력됨.

출력 포맷은 예제 출력을 통해 확인할 수 있다.

예제 입력

1 2
NOT
true false
AND
false false
false true
TWEEK
true false
true false
(x AND (NOT(y TWEEK z)))
x true
y true
*
1 1
MOCK
true true
NAND
true true
true false
(x NAND (MOCK (y NAND z)))
x false
y false
*
0 2
XOR
false true
true false
FAKE
true true
false false
((p XOR q) FAKE r)
p true
q false
*
-1 -1

예제 출력

Case 1: unknown
Case 2: true
Case 3: false

힌트