1.该OJ由于交换空间受限,暂不不支持万能头文件:bits/stdc++.h!!! 2.该OJ如果是长整型的话,C的输入输出请使用%lld!!!

Problem 1072. -- 去括号

1072: 去括号

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 1  Solved: 0
[Submit][Status][Web Board]

Description

当老师不容易,尤其是当小学的老师更难:现在的小朋友做作业喜欢滥用括号。
虽然不影响计算结果,但不够美观,容易出错,而且可读性差。但又不能一棒子打死,也许他们就是将来的“陈景润”呢!
为了减轻老师的工作,不至于他们工作到深夜,我们来写个程序把小朋友的作业做一下简单地处理,去掉那些多余的括号。
为了简化问题,所有式子里只存在小括号,运算符号包括+(加)、-(减)、*(乘)、/(除)、^(幂)。
注意:去掉多余的小括号不是指运算结果一样就可以。
比如:(1+2)^1 = 3。虽然把括号去掉1+2^1也等于3,但我们说这个括号不能去。
但如:1+(2+3) = 1+2+3只要是允许的,因为加法是满足交换律和结合律的。

Input

输入包括多组测试数据。
每组测试数据为一行算术表达式,只包括数字和运算符号,长度小于16。
输入以#行结束,该行不做处理。

Output

对应每组数据输入都有一行输出。
输出去掉多余的括号后的表达式。

Sample Input

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

Sample Output

1+1
1
1+1+1+1
(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
1*2*4*3
1*2*4*3
1*2*4*3
1*2*4*3
1*2*4*3
(1+3+2)*4
(1+3+2)*4
(1+3)*(2+4)
1*3*2*4
1*3*2*4
1*3*2*4
1*3*2*4
1*3*2*4
(1+3)*(4+2)
1*3*4*2
1*3*4*2
1*3*4*2
1*3*4*2
1*3*4*2
1*4*3*2
1*4*3*2
1*4*3*2
1*4*3*2
1*4*3*2
1*4*2*3
1*4*2*3
1*4*2*3
1*4*2*3
1*4*2*3
(2+1+3)*4
(2+1+3)*4
2*1*3*4
2*1*3*4
2*1*3*4
2*1*3*4
2*1*3*4
2/1*3*4
2/1*3*4
2/(1/3)*4
2/(1/(3*4))
2/(1/3/4)
2^1*3*4
2^1*3*4
2*1*4*3
2*1*4*3
2*1*4*3
2*1*4*3
2*1*4*3
2/1*4*3
2/1*4*3
2/(1/4)*3
2/(1/(4*3))
2/(1/4/3)
2^1*4*3
2^1*4*3
(2+3+1)*4
(2+3+1)*4
2*3*1*4
2*3*1*4
2*3*1*4
2*3*1*4
2*3*1*4
2*3/1*4
2*3/1*4
2*3/1*4
2*3/(1/4)
2*3/(1/4)
(2*3)^1*4
2*3^1*4
2*3^1*4
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/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)^1
2*3*4^1
2^3*(4-1)
(2+4)*(3+1)
2*4*3*1
2*4*3*1
2*4*3*1
2*4*3*1
2*4*3*1
2*4*3/1
2*4*3/1
2*4*3/1
2*4*3/1
2*4*3/1
(2*4*3)^1
(2*4*3)^1
2*4*3^1
2*(4*3)^1
2*4*3^1
(2+4)*(1+3)
2*4*1*3
2*4*1*3
2*4*1*3
2*4*1*3
2*4*1*3
2*4/1*3
2*4/1*3
2*4/1*3
2*4/(1/3)
2*4/(1/3)
(2*4)^1*3
2*4^1*3
2*4^1*3
2^(4-1)*3
(3+2+1)*4
(3+2+1)*4
3*2*1*4
3*2*1*4
3*2*1*4
3*2*1*4
3*2*1*4
3*2/1*4
3*2/1*4
3*2/1*4
3*2/(1/4)
3*2/(1/4)
(3*2)^1*4
3*2^1*4
3*2^1*4
3/2^(1-4)
3*2*4*1
3*2*4*1
3*2*4*1
3*2*4*1
3*2*4*1
3*2*4/1
3*2*4/1
3*2*4/1
3*2*4/1
3*2*4/1
(3*2*4)^1
(3*2*4)^1
3*2*4^1
3*(2*4)^1
3*2*4^1
3*2^(4-1)
(3+1+2)*4
(3+1+2)*4
(3+1)*(2+4)
3*1*2*4
3*1*2*4
3*1*2*4
3*1*2*4
3*1*2*4
3/1*2*4
3/1*2*4
3/(1/2)*4
3/(1/(2*4))
3/(1/2/4)
3^1*2*4
3^1*2*4
(3+1)*(4+2)
3*1*4*2
3*1*4*2
3*1*4*2
3*1*4*2
3*1*4*2
3/1*4*2
3/1*4*2
3/(1/4)*2
3/(1/(4*2))
3/(1/4/2)
3^1*4*2
3^1*4*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/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*2*1
3*4*2*1
3*4*2*1
3*4*2*1
3*4*2*1
3*4*2/1
3*4*2/1
3*4*2/1
3*4*2/1
3*4*2/1
(3*4*2)^1
(3*4*2)^1
3*4*2^1
3*(4*2)^1
3*4*2^1
(4+2)*(3+1)
4*(2+3+1)
4*(2+3+1)
4*2*3*1
4*2*3*1
4*2*3*1
4*2*3*1
4*2*3*1
4*2*3/1
4*2*3/1
4*2*3/1
4*2*3/1
4*2*3/1
(4*2*3)^1
(4*2*3)^1
4*2*3^1
4*(2*3)^1
4*2*3^1
(4+2)*(1+3)
4*(2+1+3)
4*(2+1+3)
4*2*1*3
4*2*1*3
4*2*1*3
4*2*1*3
4*2*1*3
4*2/1*3
4*2/1*3
4*2/1*3
4*2/(1/3)
4*2/(1/3)
(4*2)^1*3
4*2^1*3
4*2^1*3
4*(3+2+1)
4*(3+2+1)
4*3*2*1
4*3*2*1
4*3*2*1
4*3*2*1
4*3*2*1
4*3*2/1
4*3*2/1
4*3*2/1
4*3*2/1
4*3*2/1
(4*3*2)^1
(4*3*2)^1
4*3*2^1
4*(3*2)^1
4*3*2^1
4*(3+1+2)
4*(3+1+2)
4*3*1*2
4*3*1*2
4*3*1*2
4*3*1*2
4*3*1*2
4*3/1*2
4*3/1*2
4*3/1*2
4*3/(1/2)
4*3/(1/2)
(4*3)^1*2
4*3^1*2
4*3^1*2
4*(1+3+2)
4*(1+3+2)
4*1*3*2
4*1*3*2
4*1*3*2
4*1*3*2
4*1*3*2
4/1*3*2
4/1*3*2
4/(1/3)*2
4/(1/(3*2))
4/(1/3/2)
4^1*3*2
4^1*3*2
(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*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^1*2*3
4^1*2*3

HINT

Source

[Submit][Status][Web Board]