불 표현식 압축기

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

요약

네 변수로 이루어진 불리언 식이 주어질 때, NOT, XOR, AND로 표현한 가장 짧은 동치 식의 길이를 구한다.

문제

뜻을 그대로 유지하면서 불 식을 가장 짧은 형태로 바꾸는 압축기를 만든다.

불 식의 문법은 단말 기호 0 1 a b c d - ^ * ( ), 시작 기호 <E>, 그리고 다음 생성 규칙으로 이루어진다.

<E> ::= 0 | 1 | a | b | c | d | -<E> | (<E>^<E>) | (<E>*<E>)

a, b, c, d는 값이 0 또는 1인 불 변수다. 연산자는 아래 표대로 계산한다. -는 부정(NOT), ^는 배타적 논리합(XOR), *는 논리곱(AND)이다.

x	y	`-x`	`(x^y)`	`(x*y)`
0	0	1	0	0
0	1	1	1	0
1	0	0	1	0
1	1	0	0	1

표: 연산자의 계산 결과

네 변수에 어떤 값을 넣어도 주어진 식과 값이 같은 식 가운데, 가장 짧은 식의 길이를 구하는 프로그램을 작성한다.

예를 들어 0은 더 줄일 수 없으므로 가장 짧은 길이가 1이다. (a*(1*b))는 변수 값이 무엇이든 (a*b), (b*a)와 값이 같고 이 둘이 가장 짧으므로 답은 5다.

입력은 여러 데이터 세트로 이루어진다. 데이터 세트 하나는 위 문법을 따르는 식이 적힌 한 줄이다. 식의 길이는 16자 이하다.

입력의 끝은 마침표 하나(.)만 있는 줄로 나타낸다. 데이터 세트는 최대 200개다.

각 데이터 세트마다, 네 변수의 모든 값 조합에서 주어진 식과 값이 같은 식 가운데 가장 짧은 식의 길이를 정수 하나로 한 줄에 출력한다.

예제 1

입력

0
(a*(1*b))
(1^a)
(-(-a*-b)*a)
(a^(b^(c^d)))
.

예상 출력

예제 3

입력

0
1
a
b
c
d
-a
--a
---a
---------------a
-0
-1
--------0
.

예상 출력

예제 4

입력

(a*-a)
(a^a)
(a^-a)
(a*a)
(a*1)
(a*0)
(a^0)
(a^1)
(1*1)
(0^0)
(1^1)
(0*1)
.

예상 출력

예제 5

입력

(-(-a*-b)*a)
(-(-a*-b)^a)
-(-a*-b)
-(-a*-c)
(a*-(-a*-b))
-(--a*--b)
(-a^-b)
-(a^b)
.

예상 출력

예제 6

입력

(a^(b^(c^d)))
((a^b)^(c^d))
(((a^b)^c)^d)
(a*(b*(c*d)))
((a*b)*(c*d))
(((a*b)*c)*d)
(a^(b*(c^d)))
.

예상 출력