시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 11 4 3 60.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이다.

출력

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

예제 입력 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+XHJcblxyXG48cD5cclxuXHRcdWIzNjdcdWMxNDhcdWFjZmMgXHVhY2YxXHVjMTQ4XHVjNzQwIFx1YWNiMFx1ZDU2OSBcdWJjOTVcdWNlNTlcdWM3NDQgXHVjMGFjXHVjNmE5XHVkNTc0XHViM2M0IFx1YjQxY1x1YjJlNC4geCsoeSt6KSA9ICh4K3kpK3ogPSB4K3kreiwgeCh5eikgPSAoeHkpeiA9IHh5ei4gXHVkNTU4XHVjOWMwXHViOWNjLCBcdWFkNTBcdWQ2NTggXHViYzk1XHVjZTU5XHVhY2ZjIFx1YmQ4NFx1YmMzMCBcdWJjOTVcdWNlNTlcdWM3NDAgXHVjMGFjXHVjNmE5XHVkNTU4XHViYTc0IFx1YzU0OFx1YjQxY1x1YjJlNC4gXHVhZDA0XHVkNjM4XHVjNzU4IFx1YzZiMFx1YzEyMCBcdWMyMWNcdWM3MDRcdWFjMDAgXHVhYzAwXHVjN2E1IFx1YjE5Mlx1YzczY1x1YmE3MCwgXHVhZGY4IFx1YjJlNFx1Yzc0Y1x1Yzc0MCBcdWFjZjFcdWMxNDgsIFx1YjM2N1x1YzE0OCBcdWMyMWNcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cclxuXHRcdWM3ODVcdWI4MjVcdWM3NDAgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1YmIzOFx1YzgxYyBcdWMxMjRcdWJhODVcdWM3NTggXHViYjM4XHViYzk1XHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1OFx1YjI5NCBcdWMyZGRcdWM3NzRcdWJhNzAsIFx1ZDU1YyBcdWM5MDRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVjMmRkXHVjNzU4IFx1YWUzOFx1Yzc3NFx1YjI5NCBcdWNkNWNcdWIzMDAgMTAwMFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cclxuXHRcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMsIFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzQgXHVjMmRkXHVjNWQwXHVjMTFjIFx1Y2Q1Y1x1YjMwMFx1ZDU1YyBcdWFkMDRcdWQ2MzhcdWI5N2MgXHVjODFjXHVhYzcwXHVkNTVjIFx1YjRhNCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNDgxNyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlBhcmVudGhlc2lzIiwiZGVzY3JpcHRpb24iOiI8cD5UbyBhIGNvbXB1dGVyLCB0aGVyZSBpcyBubyBkaWZmZXJlbmNlIGJldHdlZW4gdGhlIGV4cHJlc3Npb24gKCgoeCkrKHkpKSh0KSkgYW5kICh4K3kpdDsgYnV0LCB0byBhIGh1bWFuLCB0aGUgbGF0dGVyIGlzIGVhc2llciB0byByZWFkLiBXaGVuIHdyaXRpbmcgYXV0b21hdGljYWxseSBnZW5lcmF0ZWQgZXhwcmVzc2lvbnMgdGhhdCBhIGh1bWFuIG1heSBoYXZlIHRvIHJlYWQsIGl0IGlzIHVzZWZ1bCB0byBtaW5pbWl6ZSB0aGUgbnVtYmVyIG9mIHBhcmVudGhlc2VzIGluIGFuIGV4cHJlc3Npb24uIFdlIGFzc3VtZSBleHByZXNzaW9ucyBjb25zaXN0IG9mIG9ubHkgdHdvIG9wZXJhdGlvbnM6IGFkZGl0aW9uICgrKSBhbmQgbXVsdGlwbGljYXRpb24gKGp1eHRhcG9zaXRpb24pLCBhbmQgdGhlc2Ugb3BlcmF0aW9ucyBhY3Qgb24gc2luZ2xlIGxvd2VyLWNhc2UgbGV0dGVyIHZhcmlhYmxlcyBvbmx5LiBTcGVjaVx1ZmIwMWNhbGx5LCBoZXJlIGlzIHRoZSBncmFtbWFyIGZvciBhbiBleHByZXNzaW9uIEU6PFwvcD5cclxuXHJcbjxwcmU+XHJcbkUgOiBQIHwgUCAmIzM5OysmIzM5OyBFXHJcblAgOiBGIHwgRiBQXHJcbkYgOiBWIHwgJiMzOTsoJiMzOTsgRSAmIzM5OykmIzM5O1xyXG5WIDogJiMzOTthJiMzOTsgfCAmIzM5O2ImIzM5OyB8IC4uIHwgJiMzOTt6JiMzOTs8XC9wcmU+XHJcblxyXG48cD5UaGUgYWRkaXRpb24gKCssIGFzIGluIHgreSkgYW5kIG11bHRpcGxpY2F0aW9uIChqdXh0YXBvc2l0aW9uLCBhcyBpbiB4eSkgb3BlcmF0b3JzIGFyZSBhc3NvY2lhdGl2ZTogeCsoeSt6KT0oeCt5KSt6PXgreSt6IGFuZCB4KHl6KT0oeHkpej14eXouIENvbW11dGF0aXZpdHkgYW5kIGRpc3RyaWJ1dGl2aXR5IG9mIHRoZXNlIG9wZXJhdGlvbnMgc2hvdWxkIG5vdCBiZSBhc3N1bWVkLiBQYXJlbnRoZXNlcyBoYXZlIHRoZSBoaWdoZXN0IHByZWNlZGVuY2UsIGZvbGxvd2VkIGJ5IG11bHRpcGxpY2F0aW9uIGFuZCB0aGVuIGFkZGl0aW9uLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IGNvbnNpc3RzIG9mIGEgbnVtYmVyIG9mIGNhc2VzLiBFYWNoIGNhc2UgaXMgZ2l2ZW4gYnkgb25lIGxpbmUgdGhhdCBzYXRpc2ZpZXMgdGhlIGdyYW1tYXIgYWJvdmUuIEVhY2ggZXhwcmVzc2lvbiBpcyBhdCBtb3N0IDEwMDAgY2hhcmFjdGVycyBsb25nLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIGNhc2UsIHByaW50IG9uIG9uZSBsaW5lIHRoZSBzYW1lIGV4cHJlc3Npb24gd2l0aCBhbGwgdW5uZWNlc3NhcnkgcGFyZW50aGVzZXMgcmVtb3ZlZC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=