#2047 다른 수식 찾기

10  2 s   128 MB  

Description

 

경수는 화학실험 과목을 듣고 있었다. 세명의 팀원 중 경수를 제외한 나머지 팀원들이 너무 열심히 실험을 하고 있었기 때문에 경수는 딱히 할일이 없었다. 그러던 차에 최근에 나온 수학 숙제를 하기위해 숙제 유인물을 보게 되었다. 유인물에는 다음과 같은 문제가 적혀있었다.

 

수식이 주어졌을 때, 짝 지어진 괄호 쌍들을 임의로 제거했을 때 원 수식과 다른 형태의 수식들을 모두 적으시오. 수식이 다른 형태라는 것은 두 개의 수식을 문자열로 간주했을 때 차이가 있을 경우를 뜻한다. 예를 들어 (2+(2*2)+2)라는 수식이 주어질 경우, (2+2*2+2), 2+(2*2)+2, 그리고 2+2*2+2는 올바르게 괄호 쌍들이 제거 되었고, 원 수식과 다른 수식이라고 할 수 있다. 하지만 (2+2*2)+2, 2+(2*2+2)와 같이 짝 지어지지 않은 괄호 쌍을 지우는 경우는 올바르지 않은 경우로 간주한다.

 

경수는 문제를 보고 이것은 아무래도 손으로 하면 결과가 제대로 나오지 않으리라 판단하여, 최근 컴퓨터 프로그래밍 과목 과제가 너무 쉬워 하루하루가 여유롭다 자랑하고 다니는 당신에게 문자를 보내어 해당 문제를 풀어 달라고 요청했다(물론 경수는 정말 프로그래밍을 잘하는 친구이지만, 실험 시간에 랩탑을 꺼내어 딴짓을 하면 조교에게 혼나는 것은 자명한 사실이다. 그렇다고 정말로 경수가 이 문제를 못 푸는 것은 아니다. 충분히 풀 수 있을 것이다.). 가뜩이나 통장 잔액이 486원을 향해 달리고 있는 당신, 이 문제를 풀어서 경수에게 맛있는 것을 얻어먹자.

Input

 

입력은 여럿의 테스트 케이스로 이뤄지며, 입력의 맨 첫 줄에는 테스트 케이스의 개수 T가 입력된다.

테스트 케이스는 한 줄로 이뤄지며, 길이 200이하의 수식이 입력된다. 수식에 사용되는 연산자는 ‘+’, ‘-’, ‘*’, ‘/’ 그리고 ‘(‘, ‘)’다.  수식이 올바르게 입력되지 않는 경우는 존재하지 않으며, 적어도 한 개의 괄호 쌍이 입력 된다고 가정하며, 괄호 쌍은 최대 10개 쌍이 주어질 수 있다.

Output

 

각 테스트 케이스에 주어진 수식에 대해 올바르게 짝 지어진 괄호 쌍들을 제거하여 만들어지는 다른 수식들을 한 줄에 하나씩 사전 순으로 출력한다., 또한 i번째 테스트 케이스의 경우 점수들을 출력하기에 앞서 “Case #i:”를 출력한다. 맨 처음 들어오는 테스트 케이스의 번호는 1이며, 마지막에 들어오는 테스트 케이스의 번호는 T이다.

 

Sample Input

Sample Output

3
(0/(0))
(2+(2*2)+2)
(1+(2*(3+4)))
Case #1:
(0/0)
0/(0)
0/0
Case #2:
(2+2*2+2)
2+(2*2)+2
2+2*2+2
Case #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