트리 변환 퍼즐

퍼즐을 시작해 보자!

먼저 정수, 연산자 기호 +와 −, 괄호로만 이루어진 산술식을 하나 받는다. (4−1)−(2+3)−(5+6)이 그런 식의 한 예다. 잘 알려져 있듯이 산술식의 구조는 자연스럽게 트리로 표현된다. 예를 들어 Figure C-1의 트리는 (4−1)−(2+3)−(5+6)을 나타낸다.

Figure C-1: (4−1)−(2+3)−(5+6)의 트리 표현

그림의 트리에서 각 상자는 정수로 표시된 리프 노드이고, 각 원은 연산자 기호 + 또는 −로 표시된 비리프 노드다. 정수로 표시된 리프 노드의 값은 그 정수다. 연산자 기호 +를 가진 노드의 값은 모든 자식 노드 값의 합이다. 연산자 기호 −를 가진 노드의 값은 가장 왼쪽 자식 노드의 값에서 나머지 모든 자식 노드의 값을 뺀 것이다. 이렇게 계산한 루트 노드의 값은 당연히 주어진 식을 일반적인 산술 규칙으로 계산한 값과 같다.

이 퍼즐에서 주어지는 산술식을 나타내는 트리는 모두 루트 노드가 자식 노드 세 개를 가지고, 나머지 비리프 노드는 부모 하나와 자식 둘을 가진다. 따라서 모든 비리프 노드는 정확히 세 노드와 직접 연결된다.

주어진 산술식에 대응하는 트리 구조를, 전체 트리나 그 임의의 부분 트리에 다음 연산 중 하나를 임의 횟수 적용해서 변환하는 것을 생각하자.

• 비리프 노드의 자식 노드 두 개를 맞바꾼다.
• 루트의 가장 왼쪽(또는 가장 오른쪽) 자식 노드가 비리프라면, 그것을 트리의 새 루트로 만들고 기존 루트 노드를 새 루트의 가장 오른쪽(각각 가장 왼쪽) 자식 노드로 만든다.

위에 명시된 경우를 제외하면, 이 연산들은 두 노드 사이의 부모-자식 관계도, 같은 부모를 공유하는 자식 노드 사이의 왼쪽에서 오른쪽 순서도 바꾸지 않는다.

이런 연산으로 얻은 새 트리는 값이 다를 수도 있는 다른 산술식을 나타낸다. 이 퍼즐의 목표는 위에 설명한 연산을 임의 횟수 적용해서 얻을 수 있는 식의 값 중 최댓값을 찾는 것이다.

예를 들어 Figure C-1에서 연산자 기호 −를 가진 가장 왼쪽 비리프 노드의 자식 노드 두 개를 맞바꾸면 Figure C-2의 트리가 된다.

Figure C-2: 가장 왼쪽 리프 노드 두 개를 맞바꾼 결과

그다음 Figure C-2에서 루트의 가장 왼쪽 자식 노드와 가장 오른쪽 자식 노드를 맞바꾸면 Figure C-3의 트리가 된다. 원래 산술식 (4−1)−(2+3)−(5+6)의 값은 −13이고, Figure C-2와 Figure C-3의 두 트리가 나타내는 식의 값은 각각 −19와 9다.

Figure C-3: 루트의 가장 왼쪽 노드와 가장 오른쪽 노드를 맞바꾼 결과

또 Figure C-3에서 루트의 가장 왼쪽 자식 노드를 새 루트로 만들고 기존 루트를 새 루트의 가장 오른쪽 자식 노드로 만들면 Figure C-4의 트리가 된다. 이 트리가 나타내는 식은 5+6+((2+3)−(1−4))이고 그 값은 19로, 이 경우에 가질 수 있는 최댓값이다.

Figure C-4: 가장 왼쪽 비리프 노드를 새 루트로 만든 결과

입력은 여러 데이터셋으로 이루어지고, 각 데이터셋은 다음에 정의하는 루트 식을 한 줄에 담는다.

• 루트 식은 비루트 식 세 개와, 그 사이를 구분하는 플러스(+) 두 개 또는 마이너스(−) 두 개로 이루어진 문자열이다.
• 비루트 식은 한 자리 정수를 나타내는 숫자 하나이거나, 비루트 식 두 개와 그 사이를 구분하는 플러스 또는 마이너스 기호 하나, 그리고 둘을 감싸는 여는 괄호와 닫는 괄호로 이루어진 문자열이다.

각 데이터셋은 적어도 다섯 글자(즉 숫자 세 개와 기호 두 개)를 가진다. 입력에 있는 모든 데이터셋의 총 글자 수는 500,000 이하다. 중첩된 괄호의 깊이는 100 이하다.

입력의 끝은 −1 하나를 담은 줄로 표시된다.

각 데이터셋마다 퍼즐의 답을 한 줄에 출력한다.