메모리 셀

태양이는 계산기로 아주 복잡한 식을 계산해야 한다. 계산기의 메모리 기능을 쓰고 싶지만 오래된 기종이라 메모리 셀이 하나뿐이다. 그래서 주어진 식에서 가장 큰 공통 부분식을 찾아 그 셀을 최대한 잘 쓰려고 한다.

다음 식을 보자.

$1 + (2 \times 3) + 5 / (1 + 2 \times 3)$

이 식에는 $2 \times 3$이 두 번 나오므로 $2 \times 3$은 공통 부분식이다. $1 + 2 \times 3$도 두 번 나온다. 그래서 이 식의 공통 부분식은 $2 \times 3$과 $1 + 2 \times 3$ 두 개이고, 그중 가장 큰 것은 $1 + 2 \times 3$이다. 입력 식의 첫 괄호 $(2 \times 3)$은 불필요하다. 연산자 우선순위 때문에 $1 + (2 \times 3)$은 $1 + 2 \times 3$과 같은 식이다. 태양이는 가장 큰 공통 부분식을 찾아 그 값을 하나뿐인 메모리 셀에 넣으려고 한다. 주어진 식에서 가장 큰 공통 부분식을 찾는 프로그램을 작성하라.

문제를 간단하게 하려고 이항 연산자는 덧셈 +, 뺄셈 -, 곱셈 *, 나눗셈 / 네 가지만 다룬다. 우선순위는 보통의 규칙을 따라 곱셈과 나눗셈이 덧셈과 뺄셈보다 높고, 모든 연산자는 왼쪽 결합이다. 그래서 위 식의 수식 트리는 그림 1과 같다.

그림 1. $1 + (2 \times 3) + 5 / (1 + 2 \times 3)$의 수식 트리.

수식 트리를 만들 때는 연산자의 우선순위와 결합 방향을 지켜야 하고(규칙 1), 입력 식에 나온 피연산자의 순서도 그대로 두어야 한다. 즉 식에서의 순서가 트리의 중위 순회 순서와 같다(규칙 2). 수식 트리는 뿌리가 하나인 순서 트리이고, 부분식은 잎 노드가 식에 나온 순서와 같은 순서로 피연산자를 나타내는 유일한 부분 트리에 대응한다. 따라서 수식 트리에 서로 겹치지 않는 동일한 부분 트리가 두 개 있으면 공통 부분식이 있다. 공통 부분식의 두 출현은 서로 겹치면 안 된다(규칙 3). 규칙 3은 규칙 1에서 자연히 따라오지만 분명히 하려고 따로 적는다.

식의 크기는 식에 든 연산자와 피연산자의 개수이고, 수식 트리의 노드 개수와 같다. 연산자와 피연산자의 결합을 분명히 하려고 쓴 괄호는 크기에 넣지 않는다. 예를 들어 식 $(50 + 50) \times ((2) + 3)$의 크기는 괄호가 여러 쌍 있어도 7이다. 공통 부분식은 진부분식이어야 하므로 그 크기는 전체 식의 크기보다 작다. 결국 가장 큰 공통 부분식을 찾는 일은, 대응하는 수식 트리에서 규칙 1, 규칙 2, 규칙 3을 만족하는 동일한 두 부분 트리 중 크기가 가장 큰 것을 찾는 일과 같다.

식 $(1 + 1) \times (1 + 1) \times (1 + 1) \times (1 + 1) \times (1 + 1)$을 보자. 가장 큰 공통 부분식이 $(1 + 1) \times (1 + 1) \times (1 + 1) \times (1 + 1)$이라고 생각할 수 있지만, 두 출현이 서로 겹치므로 규칙 3에 어긋난다. $(1 + 1) \times (1 + 1)$도 떠오르지만, 그림 2의 수식 트리에는 이 식에 대응하는 동일한 부분 트리가 겹치지 않게 두 개 있지 않으므로 공통 부분식이 아니다. 이 식의 공통 부분식은 $1 + 1$ 하나뿐이고, 그것이 가장 크다.

그림 2. $(1 + 1) \times (1 + 1) \times (1 + 1) \times (1 + 1) \times (1 + 1)$의 수식 트리.

마지막 예로 $(1 + 2 \times 3) + 5 / (2 \times 3 + 1)$의 공통 부분식은 $1 + 2 \times 3$이나 $2 \times 3 + 1$이 아니라 $2 \times 3$이다. 피연산자의 순서가 다르면 규칙 2에 어긋나기 때문이다.

첫째 줄에 계산할 식 하나가 주어진다. 식은 피연산자(양의 정수), 이항 연산자 +, -, *, /, 괄호로 이루어진다. 입력 줄의 길이는 개행 문자를 포함해 최대 1,000이다. 곱셈 기호는 $\times$ 대신 *로 쓴다. 연산자, 피연산자, 괄호 사이에는 공백이 없어도 되고 여러 개 있어도 된다.

올바른 식이 주어진 경우, 그 식에는 공통 부분식이 적어도 하나 있고 그 크기는 3 이상이라고 가정한다.

가장 큰 공통 부분식의 후위 표기를 한 줄에 출력한다. 식의 후위 표기는 수식 트리를 후위 순회한 결과다. 예를 들어 식 1 + 2 * 3의 후위 표기는 1 2 3 * +이다. 연산자와 피연산자는 공백 하나로 구분한다.

가장 큰 공통 부분식이 여러 개면 후위 표기 문자열이 사전순으로 가장 앞서는 것 하나만 출력한다. 문자는 아스키 코드 값으로 비교하므로 공백(32)이 *(42), +(43), -(45), /(47), 숫자 0(48)부터 9(57)보다 앞선다.

입력이 올바른 식이 아니면 ERROR를 출력한다.