불 표현식 압축기

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

불 식의 문법은 단말 기호 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)이다.

표: 연산자의 계산 결과

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

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

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

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

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