괄호 제거

면접 대비

시간 제한1초메모리 제한128 MB

요약

덧셈과 곱셈, 한 글자 변수로 이루어진 식이 주어질 때 값을 바꾸지 않으면서 지울 수 있는 괄호를 모두 제거해 출력한다.

난이도: 보통10점 중 6점
유형: 스택, 문자열, 구현, 재귀
정답자: 아직 제출이 없습니다

문제

두 식 (((x)+(y))(t)) 와 (x+y)t 는 서로 같은 식이다. 어떤 식이 주어졌을 때, 식의 값을 바꾸지 않는 한도에서 괄호를 최대한 많이 제거한 결과를 출력하는 프로그램을 작성하시오.

식은 덧셈과 곱셈만으로 이루어지며, 변수는 모두 알파벳 소문자 한 글자이다. 식은 다음 문법으로 정의된다.

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이다. 입력은 파일의 끝(EOF)까지 계속된다.

출력

각 테스트 케이스마다, 주어진 식에서 값을 유지한 채 괄호를 최대한 제거한 식을 한 줄에 하나씩 출력한다.

예제2

예제 1

입력

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

예제 2
입력
```
a
```
예상 출력
```
a
```