논리식 동치 판별

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

요약
C 언어식 연산자 우선순위를 가진 두 논리식을 한 줄에서 분리해 파싱하고, 모든 변수 대입에 대해 두 식이 논리적으로 동치인지 판별합니다.
난이도

보통10점 중 6점

유형
문자열, 완전 탐색, 비트 연산
정답자
아직 제출이 없습니다

문제

두 논리식이 주어진다. 각 테스트 케이스마다 두 논리식이 모든 변수 값에 대해 같은 결과를 내는지 판별하라.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다.

각 테스트 케이스는 한 줄로 주어지며, 비교해야 할 두 논리식이 구분자 없이 이어져 있다. 프로그램은 한 줄 안에서 두 논리식을 직접 분리해야 한다.

논리식에는 변수 a부터 z, 이항 연산자 |, &, ^, 단항 연산자 ~, 괄호가 사용된다. 그 밖의 문자는 무시한다.

연산자 우선순위는 C 언어의 ~, &, ^, | 순서를 따른다. 이항 연산자는 같은 우선순위 안에서 왼쪽부터 결합한다.

각 논리식에는 서로 다른 변수가 최대 10개, 연산자가 최대 100개 포함된다.

출력

각 테스트 케이스에 대해 N을 1부터 시작하는 테스트 케이스 번호라고 하자.

두 논리식이 논리적으로 같으면 다음 형식으로 출력한다.

Data set N: Equivalent

논리적으로 다르면 다음 형식으로 출력한다.

Data set N: Different

예제1

  1. 예제 1

    입력
    3
a ^b&(b|a)~b^ a
a^b&(b|a)(a^(b&(b|a)))
~~~~z~~z
    예상 출력
    Data set 1: Different
Data set 2: Equivalent
Data set 3: Equivalent