논리식 항등식 판별

시간 제한8초메모리 제한512 MB

요약

두 논리식을 파싱한 뒤 변수 a부터 k에 어떤 값을 넣어도 두 식의 진릿값이 항상 같은지 판정한다.

난이도: 쉬움10점 중 3점
유형: 문자열, 완전 탐색, 재귀, 구현
정답자: 아직 제출이 없습니다

문제

논리 연산에서는 값으로 T와 F 두 가지만 다룬다.

"-"는 단항 연산자(입력이 하나인 연산을 나타내는 기호)이고, "*", "+", "->"는 이항 연산자(입력이 둘인 연산을 나타내는 기호)이다. "-"는 논리 부정(NOT), "*"는 논리곱(AND), "+"는 논리합(OR), "->"는 논리 함의(IMP)를 나타낸다. 이 논리 연산들의 진리표는 아래 표와 같다.

x	y	-x	(x*y)	(x+y)	(x->y)
T	T	F	T	T	T
T	F	F	F	T	F
F	T	T	F	T	T
F	F	T	F	F	T

논리식은 다음 중 하나의 형식이다. X, Y는 논리식이고, 이항 연산자는 반드시 괄호로 감싼다.

상수: T, F
변수: a, b, c, d, e, f, g, h, i, j, k
논리 부정: -X
논리곱: (X*Y)
논리합: (X+Y)
논리 함의: (X->Y)

두 논리식을 등호 "="로 결합한 등식이 주어진다. 항등식이란 식에 나타나는 변수가 어떤 값을 가지더라도 성립하는 등식을 말한다. 주어진 등식이 항등식인지 판별하는 프로그램을 만들고자 한다.

입력

입력은 여러 줄로 이루어지며, 각 줄이 데이터셋 하나이다. 데이터셋은 T, F, a, b, c, d, e, f, g, h, i, j, k, (, ), =, -, +, *, >로 이루어진 문자열이고, 공백 등 다른 문자는 포함하지 않는다. 한 줄의 길이는 1000자 이하라고 가정해도 된다.

데이터셋 하나는 등식 하나를 포함한다. 등식의 문법은 다음 BNF로 주어진다. 모든 등식은 이 구문 규칙을 따른다.

<equation> ::= <formula> "=" <formula>
<formula>  ::= "T" | "F" |
"a" | "b" | "c" | "d" | "e" | "f" |
"g" | "h" | "i" | "j" | "k" |
"-" <formula> |
"(" <formula> "*" <formula> ")" |
"(" <formula> "+" <formula> ")" |
"(" <formula> "->" <formula> ")"

입력의 끝은 "#"만으로 이루어진 줄로 나타내며, 이 줄은 데이터셋이 아니다.

출력

각 데이터셋에 대해 등식이 항등식이면 "YES"를, 아니면 "NO"를 각각 한 줄에 출력한다. 출력에는 여분의 문자를 포함해서는 안 된다.

예제1

예제 1

입력

-(a+b)=(-a*-b)
(a->b)=(-a+b)
((a*T)+b)=(-c+(a*-b))
#

예상 출력

YES
YES
NO