Reverse Polish Notation (RPN) is a mathematical notation where every operator follows all of its operands. For instance, to add three and four, one would write "3 4 +" rather than "3 + 4". If there are multiple operations, the operator is given immediately after its second operand; so the expression written "3 − 4 + 5" would be written "3 4 − 5 +" first subtract 4 from 3, then add 5 to that.

Transform the algebraic expression with brackets into RPN form.

You can assume that for the test cases below only single letters will be used, brackets [] will not be used and each expression has only one RPN form (no expressions like abc)

----- Sample Input 1 ------
3
(a+(bc))
((a+b)(z+x))
((a+t)*((b+(a+c))^(c+d)))

----- Sample Output 1 ------
abc+
ab+zx+
at+bac++cd+^*

见题面

见题面