시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB82232139.623%

문제

두 식 (((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이다.

출력

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

예제 입력 1

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

예제 출력 1

x
x+y+z
x+yz
x+y(x+t)
x+y+xt
W3sicHJvYmxlbV9pZCI6IjQ4MTciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFkMDRcdWQ2MzgiLCJkZXNjcmlwdGlvbiI6IjxwPlxyXG5cdFx1YjQ1MCBcdWMyZGQgKCgoeCkrKHkpKSh0KSlcdWM2NDAgKHgreSl0XHViMjk0IFx1YWMxOVx1Yzc0MCBcdWMyZGRcdWM3NzRcdWIyZTQuICZuYnNwO1x1YzViNFx1YjVhNCBcdWMyZGRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjZDVjXHViMzAwXHVkNTVjIFx1YWQwNFx1ZDYzOFx1Yjk3YyBcdWM4MWNcdWFjNzBcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjMmRkXHVjNWQwXHViMjk0IFx1YjM2N1x1YzE0OCBcdWI2MTBcdWIyOTQgXHVhY2YxXHVjMTQ4XHVjNzNjXHViODVjXHViOWNjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWFjZTAsIFx1YmNjMFx1YzIxOFx1YjI5NCBcdWJhYThcdWI0NTAgXHVjNTRjXHVkMzBjXHViY2IzIFx1YzE4Y1x1YmIzOFx1Yzc5MCAxXHVhZTAwXHVjNzkwXHVjNzc0XHViMmU0LiBcdWMyZGRcdWM3NDAgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWJiMzhcdWJjOTVcdWM3M2NcdWI4NWMgXHVjODE1XHVjNzU4XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwcmU+XHJcbkUgOiBQIHwgUCAmIzM5OysmIzM5OyBFXHJcblAgOiBGIHwgRiBQXHJcbkYgOiBWIHwgJiMzOTsoJiMzOTsgRSAmIzM5OykmIzM5O1xyXG5WIDogJiMzOTthJiMzOTsgfCAmIzM5O2ImIzM5OyB8IC4uIHwgJiMzOTt6JiMzOTs8XC9wcmU+XHJcblxyXG48cD5cclxuXHRcdWIzNjdcdWMxNDhcdWFjZmMgXHVhY2YxXHVjMTQ4XHVjNzQwIFx1YWNiMFx1ZDU2OSBcdWJjOTVcdWNlNTlcdWM3NDQgXHVjMGFjXHVjNmE5XHVkNTc0XHViM2M0IFx1YjQxY1x1YjJlNC4geCsoeSt6KSA9ICh4K3kpK3ogPSB4K3kreiwgeCh5eikgPSAoeHkpeiA9IHh5ei4gXHVkNTU4XHVjOWMwXHViOWNjLCBcdWFkNTBcdWQ2NTggXHViYzk1XHVjZTU5XHVhY2ZjIFx1YmQ4NFx1YmMzMCBcdWJjOTVcdWNlNTlcdWM3NDAgXHVjMGFjXHVjNmE5XHVkNTU4XHViYTc0IFx1YzU0OCBcdWI0MWNcdWIyZTQuIFx1YWQwNFx1ZDYzOFx1Yzc1OCBcdWM2YjBcdWMxMjAgXHVjMjFjXHVjNzA0XHVhYzAwIFx1YWMwMFx1YzdhNSBcdWIxOTJcdWM3M2NcdWJhNzAsIFx1YWRmOCBcdWIyZTRcdWM3NGNcdWM3NDAgXHVhY2YxXHVjMTQ4LCBcdWIzNjdcdWMxNDggXHVjMjFjXHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHJcblx0XHVjNzg1XHViODI1XHVjNzQwIFx1YzVlY1x1YjdlYyBcdWFjMWNcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWJiMzhcdWM4MWMgXHVjMTI0XHViYTg1XHVjNzU4IFx1YmIzOFx1YmM5NVx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NThcdWIyOTQgXHVjMmRkXHVjNzc0XHViYTcwLCBcdWQ1NWMgXHVjOTA0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YzJkZFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWIyOTQgXHVjZDVjXHViMzAwIDEwMDBcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHJcblx0XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCBcdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0IFx1YzJkZFx1YzVkMFx1YzExYyBcdWNkNWNcdWIzMDBcdWQ1NWMgXHVhZDA0XHVkNjM4XHViOTdjIFx1YzgxY1x1YWM3MFx1ZDU1YyBcdWI0YTQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjQ4MTciLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJQYXJlbnRoZXNpcyIsImRlc2NyaXB0aW9uIjoiPHA+VG8gYSBjb21wdXRlciwgdGhlcmUgaXMgbm8gZGlmZmVyZW5jZSBiZXR3ZWVuIHRoZSBleHByZXNzaW9uICgoKHgpKyh5KSkodCkpIGFuZCAoeCt5KXQ7IGJ1dCwgdG8gYSBodW1hbiwgdGhlIGxhdHRlciBpcyBlYXNpZXIgdG8gcmVhZC4gV2hlbiB3cml0aW5nIGF1dG9tYXRpY2FsbHkgZ2VuZXJhdGVkIGV4cHJlc3Npb25zIHRoYXQgYSBodW1hbiBtYXkgaGF2ZSB0byByZWFkLCBpdCBpcyB1c2VmdWwgdG8gbWluaW1pemUgdGhlIG51bWJlciBvZiBwYXJlbnRoZXNlcyBpbiBhbiBleHByZXNzaW9uLiBXZSBhc3N1bWUgZXhwcmVzc2lvbnMgY29uc2lzdCBvZiBvbmx5IHR3byBvcGVyYXRpb25zOiBhZGRpdGlvbiAoKykgYW5kIG11bHRpcGxpY2F0aW9uIChqdXh0YXBvc2l0aW9uKSwgYW5kIHRoZXNlIG9wZXJhdGlvbnMgYWN0IG9uIHNpbmdsZSBsb3dlci1jYXNlIGxldHRlciB2YXJpYWJsZXMgb25seS4gU3BlY2lcdWZiMDFjYWxseSwgaGVyZSBpcyB0aGUgZ3JhbW1hciBmb3IgYW4gZXhwcmVzc2lvbiBFOjxcL3A+XHJcblxyXG48cHJlPlxyXG5FIDogUCB8IFAgJiMzOTsrJiMzOTsgRVxyXG5QIDogRiB8IEYgUFxyXG5GIDogViB8ICYjMzk7KCYjMzk7IEUgJiMzOTspJiMzOTtcclxuViA6ICYjMzk7YSYjMzk7IHwgJiMzOTtiJiMzOTsgfCAuLiB8ICYjMzk7eiYjMzk7PFwvcHJlPlxyXG5cclxuPHA+VGhlIGFkZGl0aW9uICgrLCBhcyBpbiB4K3kpIGFuZCBtdWx0aXBsaWNhdGlvbiAoanV4dGFwb3NpdGlvbiwgYXMgaW4geHkpIG9wZXJhdG9ycyBhcmUgYXNzb2NpYXRpdmU6IHgrKHkreik9KHgreSkrej14K3kreiBhbmQgeCh5eik9KHh5KXo9eHl6LiBDb21tdXRhdGl2aXR5IGFuZCBkaXN0cmlidXRpdml0eSBvZiB0aGVzZSBvcGVyYXRpb25zIHNob3VsZCBub3QgYmUgYXNzdW1lZC4gUGFyZW50aGVzZXMgaGF2ZSB0aGUgaGlnaGVzdCBwcmVjZWRlbmNlLCBmb2xsb3dlZCBieSBtdWx0aXBsaWNhdGlvbiBhbmQgdGhlbiBhZGRpdGlvbi48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBpbnB1dCBjb25zaXN0cyBvZiBhIG51bWJlciBvZiBjYXNlcy4gRWFjaCBjYXNlIGlzIGdpdmVuIGJ5IG9uZSBsaW5lIHRoYXQgc2F0aXNmaWVzIHRoZSBncmFtbWFyIGFib3ZlLiBFYWNoIGV4cHJlc3Npb24gaXMgYXQgbW9zdCAxMDAwIGNoYXJhY3RlcnMgbG9uZy48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCBjYXNlLCBwcmludCBvbiBvbmUgbGluZSB0aGUgc2FtZSBleHByZXNzaW9uIHdpdGggYWxsIHVubmVjZXNzYXJ5IHBhcmVudGhlc2VzIHJlbW92ZWQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==