시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 553 148 121 29.227%

문제

어떤 수식이 주어졌을 때, 괄호를 제거해서 나올 수 있는 서로 다른 식의 개수를 계산하는 프로그램을 작성하시오.

이 수식은 괄호가 올바르게 쳐져 있다. 예를 들면, 1+2, (3+4), (3+4*(5+6))와 같은 식은 괄호가 서로 쌍이 맞으므로 올바른 식이다.

하지만, 1+(2*3, ((2+3)*4 와 같은 식은 쌍이 맞지 않는 괄호가 있으므로 올바른 식이 아니다.

괄호를 제거할 때는, 항상 쌍이 되는 괄호끼리 제거해야 한다.

예를들어 (2+(2*2)+2)에서 괄호를 제거하면, (2+2*2+2), 2+(2*2)+2, 2+2*2+2를 만들 수 있다. 하지만, (2+2*2)+2와 2+(2*2+2)는 만들 수 없다. 그 이유는 쌍이 되지 않는 괄호를 제거했기 때문이다.

어떤 식을 여러 쌍의 괄호가 감쌀 수 있다.

입력

첫째 줄에 음이 아닌 정수로 이루어진 수식이 주어진다. 이 수식은 괄호가 올바르게 쳐져있다. 숫자, '+', '*', '-', '/', '(', ')'로만 이루어져 있다. 수식의 길이는 최대 200이고, 괄호 쌍은 적어도 1개, 많아야 10개이다. 

출력

올바른 괄호 쌍을 제거해서 나올 수 있는 서로 다른 식을 사전 순으로 출력한다.

예제 입력 1

(0/(0))

예제 출력 1

(0/0)
0/(0)
0/0
W3sicHJvYmxlbV9pZCI6IjI4MDAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFkMDRcdWQ2MzggXHVjODFjXHVhYzcwIiwiZGVzY3JpcHRpb24iOiJcclxuPHA+XHJcblx0XHVjNWI0XHViNWE0IFx1YzIxOFx1YzJkZFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWFkMDRcdWQ2MzhcdWI5N2MgXHVjODFjXHVhYzcwXHVkNTc0XHVjMTFjIFx1YjA5OFx1YzYyYyBcdWMyMTggXHVjNzg4XHViMjk0IFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggXHVjMmRkXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWFjYzRcdWMwYjBcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjNzc0IFx1YzIxOFx1YzJkZFx1Yzc0MCBcdWFkMDRcdWQ2MzhcdWFjMDAgXHVjNjJjXHViYzE0XHViOTc0XHVhYzhjIFx1Y2NkMFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWJhNzQsIDErMiwgKDMrNCksICgzKzQqKDUrNikpXHVjNjQwIFx1YWMxOVx1Yzc0MCBcdWMyZGRcdWM3NDAgXHVhZDA0XHVkNjM4XHVhYzAwIFx1YzExY1x1Yjg1YyBcdWMzMGRcdWM3NzQgXHViOWRlXHVjNzNjXHViYmMwXHViODVjIFx1YzYyY1x1YmMxNFx1Yjk3OCBcdWMyZGRcdWM3NzRcdWIyZTQuPFwvcD5cclxuPHA+XHJcblx0XHVkNTU4XHVjOWMwXHViOWNjLCAxKygyKjMsICgoMiszKSo0IFx1YzY0MCBcdWFjMTlcdWM3NDAgXHVjMmRkXHVjNzQwIFx1YzMwZFx1Yzc3NCBcdWI5ZGVcdWM5YzAgXHVjNTRhXHViMjk0IFx1YWQwNFx1ZDYzOFx1YWMwMCBcdWM3ODhcdWM3M2NcdWJiYzBcdWI4NWMgXHVjNjJjXHViYzE0XHViOTc4IFx1YzJkZFx1Yzc3NCBcdWM1NDRcdWIyYzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YWQwNFx1ZDYzOFx1Yjk3YyBcdWM4MWNcdWFjNzBcdWQ1NjAgXHViNTRjXHViMjk0LCBcdWQ1NmRcdWMwYzEgXHVjMzBkXHVjNzc0IFx1YjQxOFx1YjI5NCBcdWFkMDRcdWQ2MzhcdWIwN2NcdWI5YWMgXHVjODFjXHVhYzcwXHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjNjA4XHViOTdjXHViNGU0XHVjNWI0ICgyKygyKjIpKzIpXHVjNWQwXHVjMTFjIFx1YWQwNFx1ZDYzOFx1Yjk3YyBcdWM4MWNcdWFjNzBcdWQ1NThcdWJhNzQsICgyKzIqMisyKSwgMisoMioyKSsyLCAyKzIqMisyXHViOTdjIFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWQ1NThcdWM5YzBcdWI5Y2MsICgyKzIqMikrMlx1YzY0MCAyKygyKjIrMilcdWIyOTQgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM1YzZcdWIyZTQuIFx1YWRmOCBcdWM3NzRcdWM3MjBcdWIyOTQgXHVjMzBkXHVjNzc0IFx1YjQxOFx1YzljMCBcdWM1NGFcdWIyOTQgXHVhZDA0XHVkNjM4XHViOTdjIFx1YzgxY1x1YWM3MFx1ZDU4OFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YzViNFx1YjVhNCBcdWMyZGRcdWM3NDQgXHVjNWVjXHViN2VjIFx1YzMwZFx1Yzc1OCBcdWFkMDRcdWQ2MzhcdWFjMDAgXHVhYzEwXHVjMzAwIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbiIsImlucHV0IjoiPHA+XHJcblx0XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWM3NGNcdWM3NzQgXHVjNTQ0XHViMmNjIFx1YzgxNVx1YzIxOFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHVjMjE4XHVjMmRkXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzc0IFx1YzIxOFx1YzJkZFx1Yzc0MCBcdWFkMDRcdWQ2MzhcdWFjMDAgXHVjNjJjXHViYzE0XHViOTc0XHVhYzhjIFx1Y2NkMFx1YzgzOFx1Yzc4OFx1YjJlNC4gXHVjMjJiXHVjNzkwLCAmIzM5OysmIzM5OywgJiMzOTsqJiMzOTssICYjMzk7LSYjMzk7LCAmIzM5O1wvJiMzOTssICYjMzk7KCYjMzk7LCAmIzM5OykmIzM5O1x1Yjg1Y1x1YjljYyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWMyMThcdWMyZGRcdWM3NTggXHVhZTM4XHVjNzc0XHViMjk0IFx1Y2Q1Y1x1YjMwMCAyMDBcdWM3NzRcdWFjZTAsIFx1YWQwNFx1ZDYzOCBcdWMzMGRcdWM3NDAgXHVjODAxXHVjNWI0XHViM2M0IDFcdWFjMWMsIFx1YjljZVx1YzU0NFx1YzU3YyAxMFx1YWMxY1x1Yzc3NFx1YjJlNC4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cclxuXHRcdWM2MmNcdWJjMTRcdWI5NzggXHVhZDA0XHVkNjM4IFx1YzMwZFx1Yzc0NCBcdWM4MWNcdWFjNzBcdWQ1NzRcdWMxMWMgXHViMDk4XHVjNjJjIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3OCBcdWMyZGRcdWM3NDQgXHVjMGFjXHVjODA0IFx1YzIxY1x1YzczY1x1Yjg1YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjgwMCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlpBR1JBREUiLCJkZXNjcmlwdGlvbiI6IjxwPk1pcmtvIHdhcyBib3JlZCBhdCBoaXMgY2hlbWlzdHJ5IGNsYXNzLCBzbyBoZSBwbGF5ZWQgQm9tYiBTd2l0Y2hlciBvbiBoaXMgY2VsbCBwaG9uZS4gVW5mb3J0dW5hdGVseSwgaGUgd2FzIHNwb3R0ZWQgYW5kIHdhcyBnaXZlbiBhIHJpZGljdWxvdXNseSBoZWF2eSBhc3NpZ25tZW50IGZvciBob21ld29yay4gRm9yIGEgZ2l2ZW4gdmFsaWQgbWF0aCBleHByZXNzaW9uIHdpdGggYnJhY2tldHMsIGhlIG11c3QgZmluZCBhbGwgZGlmZmVyZW50IGV4cHJlc3Npb25zIHRoYXQgY2FuIGJlIG9idGFpbmVkIGJ5IHJlbW92aW5nIHZhbGlkIHBhaXJzIG9mIGJyYWNrZXRzIGZyb20gdGhlIG9yaWdpbmFsIGV4cHJlc3Npb24uIFR3byBleHByZXNzaW9ucyBhcmUgZGlmZmVyZW50IGlmIHRoZXJlIGlzIGEgY2hhcmFjdGVyIGF0IHdoaWNoIHRoZXkgZGlmZmVyLjxcL3A+XHJcblxyXG48cD5Gb3IgZXhhbXBsZSwgZ2l2ZW4gKDIrKDIqMikrMiksIG9uZSBjYW4gZ2V0ICgyKzIqMisyKSwgMisoMioyKSsyLCBhbmQgMisyKjIrMi4gKDIrMioyKSsyIGFuZCAyKygyKjIrMikgY2FuXHUyMDFmdCBiZSByZWFjaGVkLCBzaW5jZSB3ZSB3b3VsZCBoYXZlIHRvIHJlbW92ZSBwYWlycyBvZiBicmFja2V0cyB0aGF0IGFyZSBub3QgdmFsaWQuIE1vcmUgdGhhbiBvbmUgcGFpcnMgb2YgYnJhY2tldHMgY2FuIHN1cnJvdW5kIHRoZSBzYW1lIHBhcnQgb2YgdGhlIGV4cHJlc3Npb24uPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgYW5kIG9ubHkgbGluZSBvZiBpbnB1dCBjb250YWlucyBvbmUgdmFsaWQgbWF0aGVtYXRpY2FsIGV4cHJlc3Npb24gY29tcG9zZWQgb2Ygbm9ubmVnYXRpdmUgaW50ZWdlcnMsIGJhc2ljIGFyaXRobWV0aWMgb3BlcmF0aW9ucyBkZW5vdGVkIHdpdGggY2hhcmFjdGVycyAmcXVvdDsrJnF1b3Q7LCAmcXVvdDsqJnF1b3Q7LCAmcXVvdDstJnF1b3Q7IGFuZCAmcXVvdDtcLyZxdW90OywgYW5kIGJyYWNrZXRzICZxdW90OygmcXVvdDsgYW5kICZxdW90OykmcXVvdDsuPFwvcD5cclxuXHJcbjxwPkdpdmVuIGV4cHJlc3Npb24gd29uJnF1b3Q7dCBoYXZlIG1vcmUgdGhhbiAyMDAgY2hhcmFjdGVycywgYW5kIHdpbGwgaGF2ZSBhdCBsZWFzdCBvbmUsIGFuZCBubyBtb3JlIHRoYW4gMTAgcGFpcnMgb2YgYnJhY2tldHMuIEVhY2ggZXhwcmVzc2lvbiBpcyBndWFyYW50ZWVkIHRvIGhhdmUgYXQgbGVhc3Qgb25lIHBhaXIgb2YgYnJhY2tldHMuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IGFsbCBkaWZmZXJlbnQgZXhwcmVzc2lvbnMgdGhhdCBjYW4gYmUgb2J0YWluZWQgYnkgcmVtb3ZpbmcgdmFsaWQgcGFpcnMgb2YgYnJhY2tldHMsIHNvcnRlZCBsZXhpY29ncmFwaGljYWxseS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=