시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 3 3 2 100.000%

문제

두 식 (((x)+(y))(t))와 (x+y)t는 같은 식이다.  어떤 식이 주어졌을 때, 최대한 괄호를 제거하는 프로그램을 작성하시오.

식에는 덧셈 또는 곱셈으로만 이루어져 있고, 변수는 모두 알파벳 소문자 1글자이다. 식은 다음과 같은 문법으로 정의할 수 있다.

E : P | P '+' E
P : F | F P
F : V | '(' E ')'
V : 'a' | 'b' | .. | 'z'

덧셈과 곱셈은 결합 법칙을 사용해도 된다. x+(y+z) = (x+y)+z = x+y+z, x(yz) = (xy)z = xyz. 하지만, 교환 법칙과 분배 법칙은 사용하면 안된다. 괄호의 우선 순위가 가장 높으며, 그 다음은 곱셈, 덧셈 순이다.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 문제 설명의 문법을 만족하는 식이며, 한 줄로 이루어져 있다. 식의 길이는 최대 1000이다.

출력

각 테스트 케이스에 대해서, 입력으로 주어진 식에서 최대한 괄호를 제거한 뒤 출력한다.

예제 입력

x
(x+(y+z))
(x+(yz))
(x+y(x+t))
x+y+xt

예제 출력

x
x+y+z
x+yz
x+y(x+t)
x+y+xt

힌트