복잡한 수식

시간 제한

1초

메모리 제한

128 MB

문제

ACM은 GSM 네트워크를 운영하는 이동통신 사업자로서 자체 송신소를 세워야 하며, 전자기파가 어떻게 움직이는지를 정확히 계산하는 일이 매우 중요하다. 그러나 전자기장을 예측하는 일은 매우 복잡하고, 이를 기술하는 수식은 길고 읽기 어렵다. 예를 들어 아래는 전기공학의 기본 법칙을 기술하는 맥스웰 방정식이다.

\nabla \times \vec{\mathbf{B}} = 0 \\ \nabla \cdot \vec{\mathbf{E}} = \frac{\rho}{\varepsilon_0} \\ \nabla \times \vec{\mathbf{H}} = \vec{\mathbf{j}} + \frac{\partial \vec{\mathbf{D}}}{\partial t} \\ \nabla \times \vec{\mathbf{E}} = -\frac{\partial \vec{\mathbf{B}}}{\partial t}

ACM은 이러한 장(field) 계산을 수행하여 결과를 수식 형태로 내놓는 자체 컴퓨터 시스템을 설계했다. 그런데 여러 단계를 거쳐 수식을 생성하다 보니 결과 수식에는 언제나 불필요한 괄호가 남는다. 여러분의 과제는 이러한 중간 결과 수식을 받아, 의미를 바꾸지 않으면서 불필요한 괄호를 모두 제거해 '깔끔하게' 만드는 것이다.

입력

첫 줄에 양의 정수 $T$ 가 주어진다. 이는 뒤따르는 수식의 개수이다. 각 수식은 한 줄에 주어지며, 소문자 알파벳과 연산자(+, -, *, /), 그리고 괄호((, ))만으로 이루어진다. 알파벳은 임의의 값을 가질 수 있는 변수이고, 연산자와 괄호는 통상적인 의미를 갖는다. 곱셈과 나눗셈은 덧셈과 뺄셈보다 우선순위가 높다. 우선순위가 같은 연산은 모두 왼쪽에서 오른쪽으로 계산한다(즉 연산자는 왼쪽 결합이다). 수식 안에는 공백이 없다. 각 입력 줄의 길이는 250자를 넘지 않는다.

출력

각 수식마다 한 줄씩 출력한다. 그 줄에는 불필요한 괄호를 제거한, 원래와 의미가 같은 수식을 담아야 한다. 의미를 바꾸지 않는 범위에서 가능한 한 많은 괄호를 제거해야 한다. 다음 조건 중 하나가 성립할 때에만 두 수식의 의미가 같다고 본다.

연산의 순서가 그대로 유지된다. 즉 (a+b)+c는 a+b+c와 같고, a+(b/c)는 a+b/c와 같다.
덧셈과 곱셈의 결합법칙에 의해 일부 연산의 순서가 바뀌어도 결과가 달라지지 않는다. 즉 a+(b+c)와 (a+b)+c는 같다. 또한 뺄셈이나 나눗셈이 두 번째 연산일 때에는 덧셈과 뺄셈을, 그리고 곱셈과 나눗셈을 서로 결합할 수 있다. 예를 들어 a+(b-c)는 a+b-c와 같다.

그 밖의 어떤 법칙도 사용할 수 없다. 특히 좌우 피연산자를 서로 바꿀 수 없으며, a-(b-c)를 a-b+c로 바꿀 수도 없다.