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

문제

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

이 수식은 괄호가 올바르게 쳐져 있다. 예를 들면, 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

예제 입력 2

(2+(2*2)+2)

예제 출력 2

(2+2*2+2)
2+(2*2)+2
2+2*2+2

예제 입력 3

(1+(2*(3+4)))

예제 출력 3

(1+(2*3+4))
(1+2*(3+4))
(1+2*3+4)
1+(2*(3+4))
1+(2*3+4)
1+2*(3+4)
1+2*3+4
W3sicHJvYmxlbV9pZCI6IjI4MDAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFkMDRcdWQ2MzggXHVjODFjXHVhYzcwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM1YjRcdWI1YTQgXHVjMjE4XHVjMmRkXHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YWQwNFx1ZDYzOFx1Yjk3YyBcdWM4MWNcdWFjNzBcdWQ1NzRcdWMxMWMgXHViMDk4XHVjNjJjIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3OCBcdWMyZGRcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1YWNjNFx1YzBiMFx1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcblxyXG48cD5cdWM3NzQgXHVjMjE4XHVjMmRkXHVjNzQwIFx1YWQwNFx1ZDYzOFx1YWMwMCBcdWM2MmNcdWJjMTRcdWI5NzRcdWFjOGMgXHVjY2QwXHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YmE3NCwgMSsyLCAoMys0KSwgKDMrNCooNSs2KSlcdWM2NDAgXHVhYzE5XHVjNzQwIFx1YzJkZFx1Yzc0MCBcdWFkMDRcdWQ2MzhcdWFjMDAgXHVjMTFjXHViODVjIFx1YzMwZFx1Yzc3NCBcdWI5ZGVcdWM3M2NcdWJiYzBcdWI4NWMgXHVjNjJjXHViYzE0XHViOTc4IFx1YzJkZFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkNTU4XHVjOWMwXHViOWNjLCAxKygyKjMsICgoMiszKSo0IFx1YzY0MCBcdWFjMTlcdWM3NDAgXHVjMmRkXHVjNzQwIFx1YzMwZFx1Yzc3NCBcdWI5ZGVcdWM5YzAgXHVjNTRhXHViMjk0IFx1YWQwNFx1ZDYzOFx1YWMwMCBcdWM3ODhcdWM3M2NcdWJiYzBcdWI4NWMgXHVjNjJjXHViYzE0XHViOTc4IFx1YzJkZFx1Yzc3NCBcdWM1NDRcdWIyYzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWQwNFx1ZDYzOFx1Yjk3YyBcdWM4MWNcdWFjNzBcdWQ1NjAgXHViNTRjXHViMjk0LCBcdWQ1NmRcdWMwYzEgXHVjMzBkXHVjNzc0IFx1YjQxOFx1YjI5NCBcdWFkMDRcdWQ2MzhcdWIwN2NcdWI5YWMgXHVjODFjXHVhYzcwXHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNjA4XHViOTdjXHViNGU0XHVjNWI0ICgyKygyKjIpKzIpXHVjNWQwXHVjMTFjIFx1YWQwNFx1ZDYzOFx1Yjk3YyBcdWM4MWNcdWFjNzBcdWQ1NThcdWJhNzQsICgyKzIqMisyKSwgMisoMioyKSsyLCAyKzIqMisyXHViOTdjIFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWQ1NThcdWM5YzBcdWI5Y2MsICgyKzIqMikrMlx1YzY0MCAyKygyKjIrMilcdWIyOTQgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM1YzZcdWIyZTQuIFx1YWRmOCBcdWM3NzRcdWM3MjBcdWIyOTQgXHVjMzBkXHVjNzc0IFx1YjQxOFx1YzljMCBcdWM1NGFcdWIyOTQgXHVhZDA0XHVkNjM4XHViOTdjIFx1YzgxY1x1YWM3MFx1ZDU4OFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzViNFx1YjVhNCBcdWMyZGRcdWM3NDQgXHVjNWVjXHViN2VjIFx1YzMwZFx1Yzc1OCBcdWFkMDRcdWQ2MzhcdWFjMDAgXHVhYzEwXHVjMzAwIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1Yzc0Y1x1Yzc3NCBcdWM1NDRcdWIyY2MgXHVjODE1XHVjMjE4XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWMyMThcdWMyZGRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzQgXHVjMjE4XHVjMmRkXHVjNzQwIFx1YWQwNFx1ZDYzOFx1YWMwMCBcdWM2MmNcdWJjMTRcdWI5NzRcdWFjOGMgXHVjY2QwXHVjODM4XHVjNzg4XHViMmU0LiBcdWMyMmJcdWM3OTAsICYjMzk7KyYjMzk7LCAmIzM5OyomIzM5OywgJiMzOTstJiMzOTssICYjMzk7XC8mIzM5OywgJiMzOTsoJiMzOTssICYjMzk7KSYjMzk7XHViODVjXHViOWNjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YzIxOFx1YzJkZFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWIyOTQgXHVjZDVjXHViMzAwIDIwMFx1Yzc3NFx1YWNlMCwgXHVhZDA0XHVkNjM4IFx1YzMwZFx1Yzc0MCBcdWM4MDFcdWM1YjRcdWIzYzQgMVx1YWMxYywgXHViOWNlXHVjNTQ0XHVjNTdjIDEwXHVhYzFjXHVjNzc0XHViMmU0LiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YzYyY1x1YmMxNFx1Yjk3OCBcdWFkMDRcdWQ2MzggXHVjMzBkXHVjNzQ0IFx1YzgxY1x1YWM3MFx1ZDU3NFx1YzExYyBcdWIwOThcdWM2MmMgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc4IFx1YzJkZFx1Yzc0NCBcdWMwYWNcdWM4MDQgXHVjMjFjXHVjNzNjXHViODVjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIyODAwIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiWkFHUkFERSIsImRlc2NyaXB0aW9uIjoiPHA+TWlya28gd2FzIGJvcmVkIGF0IGhpcyBjaGVtaXN0cnkgY2xhc3MsIHNvIGhlIHBsYXllZCBCb21iIFN3aXRjaGVyIG9uIGhpcyBjZWxsIHBob25lLiBVbmZvcnR1bmF0ZWx5LCBoZSB3YXMgc3BvdHRlZCBhbmQgd2FzIGdpdmVuIGEgcmlkaWN1bG91c2x5IGhlYXZ5IGFzc2lnbm1lbnQgZm9yIGhvbWV3b3JrLiBGb3IgYSBnaXZlbiB2YWxpZCBtYXRoIGV4cHJlc3Npb24gd2l0aCBicmFja2V0cywgaGUgbXVzdCBmaW5kIGFsbCBkaWZmZXJlbnQgZXhwcmVzc2lvbnMgdGhhdCBjYW4gYmUgb2J0YWluZWQgYnkgcmVtb3ZpbmcgdmFsaWQgcGFpcnMgb2YgYnJhY2tldHMgZnJvbSB0aGUgb3JpZ2luYWwgZXhwcmVzc2lvbi4gVHdvIGV4cHJlc3Npb25zIGFyZSBkaWZmZXJlbnQgaWYgdGhlcmUgaXMgYSBjaGFyYWN0ZXIgYXQgd2hpY2ggdGhleSBkaWZmZXIuPFwvcD5cclxuXHJcbjxwPkZvciBleGFtcGxlLCBnaXZlbiAoMisoMioyKSsyKSwgb25lIGNhbiBnZXQgKDIrMioyKzIpLCAyKygyKjIpKzIsIGFuZCAyKzIqMisyLiAoMisyKjIpKzIgYW5kIDIrKDIqMisyKSBjYW5cdTIwMWZ0IGJlIHJlYWNoZWQsIHNpbmNlIHdlIHdvdWxkIGhhdmUgdG8gcmVtb3ZlIHBhaXJzIG9mIGJyYWNrZXRzIHRoYXQgYXJlIG5vdCB2YWxpZC4gTW9yZSB0aGFuIG9uZSBwYWlycyBvZiBicmFja2V0cyBjYW4gc3Vycm91bmQgdGhlIHNhbWUgcGFydCBvZiB0aGUgZXhwcmVzc2lvbi48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBhbmQgb25seSBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIG9uZSB2YWxpZCBtYXRoZW1hdGljYWwgZXhwcmVzc2lvbiBjb21wb3NlZCBvZiBub25uZWdhdGl2ZSBpbnRlZ2VycywgYmFzaWMgYXJpdGhtZXRpYyBvcGVyYXRpb25zIGRlbm90ZWQgd2l0aCBjaGFyYWN0ZXJzICZxdW90OysmcXVvdDssICZxdW90OyomcXVvdDssICZxdW90Oy0mcXVvdDsgYW5kICZxdW90O1wvJnF1b3Q7LCBhbmQgYnJhY2tldHMgJnF1b3Q7KCZxdW90OyBhbmQgJnF1b3Q7KSZxdW90Oy48XC9wPlxyXG5cclxuPHA+R2l2ZW4gZXhwcmVzc2lvbiB3b24mcXVvdDt0IGhhdmUgbW9yZSB0aGFuIDIwMCBjaGFyYWN0ZXJzLCBhbmQgd2lsbCBoYXZlIGF0IGxlYXN0IG9uZSwgYW5kIG5vIG1vcmUgdGhhbiAxMCBwYWlycyBvZiBicmFja2V0cy4gRWFjaCBleHByZXNzaW9uIGlzIGd1YXJhbnRlZWQgdG8gaGF2ZSBhdCBsZWFzdCBvbmUgcGFpciBvZiBicmFja2V0cy48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgYWxsIGRpZmZlcmVudCBleHByZXNzaW9ucyB0aGF0IGNhbiBiZSBvYnRhaW5lZCBieSByZW1vdmluZyB2YWxpZCBwYWlycyBvZiBicmFja2V0cywgc29ydGVkIGxleGljb2dyYXBoaWNhbGx5LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

Contest > Croatian Open Competition in Informatics > COCI 2011/2012 > Contest #6 3번