논리식 동치 판정

명제 논리식은 다음 문법으로 만든다.

<논리식> ::= <변수> | ~<논리식> | ( <논리식> ) | <논리식> <연산자> <논리식>
<연산자> ::= ^ | V
  <변수> ::= a-z, A-Z 중 문자 V를 뺀 한 글자

^는 논리곱(AND), V는 논리합(OR), ~는 부정(NOT)이다.

해석은 논리식에 나오는 모든 변수에 참이나 거짓을 하나씩 배정한 것이다. 해석이 정해지면 변수 값에 논리 연산을 보통의 방식으로 적용해서 논리식의 진리값이 정해진다.

가능한 모든 해석에서 두 논리식의 진리값이 같으면 두 논리식은 동치다. 이때 해석은 두 논리식 중 한쪽에라도 나오는 변수 전부에 값을 배정한다.

논리식 두 개가 주어진다. 두 식이 동치인지 판정하라.

첫째 줄과 둘째 줄에 논리식이 하나씩 주어진다. 변수는 알파벳 한 글자이고, 문자 V는 OR 연산자로만 쓰므로 변수 이름이 되지 않는다. 공백은 각 줄 안 어디에나 올 수 있다.

각 줄의 길이는 공백을 넣어 1000자 이하이고, 두 논리식에 나오는 서로 다른 변수는 합쳐서 16개 이하다.

두 논리식이 동치면 1을, 아니면 0을 출력한다.

~는 바로 뒤에 오는 항 하나에만 적용하고 ^와 V보다 먼저 묶인다. ^와 V는 우선순위가 같고 왼쪽부터 차례로 묶인다. 예를 들어 x ^ y V z는 (x ^ y) V z와 같고, ~x ^ y는 (~x) ^ y와 같다.