1384 : 波兰式，逆波兰式

Description

表达式有三种表示方法，分别为：

• 前缀表示（波兰式）：运算符+操作数1+操作数2
• 中缀表示：操作数1+运算符+操作数2
• 后缀表示(逆波兰式)：操作数1+操作数2+运算符

例如：a +b * (c -d ) - e/f

• 波兰式：-+a*b-cd/ef （运算符在操作数的前面，用递归计算波兰式）
• 中缀式：a+b*c-d-e/f
  
• 逆波兰式：abcd-*+ef/- （运算符在操作数的后面，用栈计算逆波兰式）

中缀表示就是原表达式去掉括号。

根据表达式求波兰式、逆波兰式都是教材第三章表达式求值的思想。

求波兰式，需要操作数栈(注意不是计算结果入栈，计算式入栈)，运算符栈。区别在于从后往前扫描表达式，( 换成 )。栈顶运算符优先级>新读入运算符优先级出栈，教材第三章表3.1中的相同运算符优先级>（从左往右计算）改为<，例如栈顶为+，新读入的为+，则栈顶优先级<新读入的优先级。

求逆波兰式，只需要运算符栈。操作数直接输出，操作符按表3.1优先级顺序出栈，输出。

输入表达式，求其波兰式和逆波兰式。

Input

测试次数

每组测试数据一行，一个100字符以内的合法表达式。

Output

对每组测试数据，输出两行

第一行，表达式的波兰表示

第二行，表达式的逆波兰表示

不同组测试数据间以空行分隔。

Sample

2
4+2*3-10/5
12+3*5+(2+10)*5 

- + 4 * 2 3 / 10 5
4 2 3 * + 10 5 / -

+ + 12 * 3 5 * + 2 10 5
12 3 5 * + 2 10 + 5 * +

Hint

Source

Author

CSGrandeur