ACM队的mdd想做一个计算器，但是，他要做的不仅仅是一计算一个A+B的计算器，他想实现随便输入一个表达式都能求出它的值的计算器，现在请你帮助他来实现这个计算器吧。

比如输入：“1+2/4=”，程序就输出1.50（结果保留两位小数）

第一行输入一个整数n，共有n组测试数据（n<10)。

每组测试数据只有一行，是一个长度不超过1000的字符串，表示这个运算式，每个运算式都是以“=”结束。这个表达式里只包含+-*/与小括号这几种符号。其中小括号可以嵌套使用。数据保证输入的操作数中不会出现负数。

每组都输出该组运算式的运算结果，输出结果保留两位小数。

此题为中缀表达式，也可以先转化成后缀表达式（逆波兰表达式）或前缀表达式（波兰表达式）求值；下面的例子会讲到

n扫描三遍：第一遍去括号；第二遍算乘除；第三遍算加减。

n用数组模拟栈；需要两个栈，一个是char 型用来存储符号，另一个是double型用来存储数值。

 
 case '+' : //此处由于加减几乎优先级一样，故放在一起
 case '*' : //此处由于乘除优先级一样，故放在一起
 
 

 

人们的日常习惯是把算术表达式写成中缀式，但对于机器来说更“习惯于”后缀式，关于算术表达式的中缀式和后缀式的论述一般的数据结构书都有相关内容可供参看，这里不再赘述，现在你的任务是将中缀式变为后缀式。

第一行输入一个整数n，共有n组测试数据（n<10)。
每组测试数据只有一行，是一个长度不超过1000的字符串，表示这个运算式的中缀式，每个运算式都是以“=”结束。这个表达式里只包含+-*/与小括号这几种符号。其中小括号可以嵌套使用。数据保证输入的操作数中不会出现负数。

每组都输出该组中缀式相应的后缀式，要求相邻的操作数操作符用空格隔开。

转换过程需要用到栈，具体过程如下：

1）如果遇到操作数，我们就直接将其输出。

2）如果遇到操作符，则我们将其放入到栈中，遇到左括号时我们也将其放入栈中。

3）如果遇到一个右括号，则将栈元素弹出，将弹出的操作符输出直到遇到左括号为止。注意，左括号只弹出并不输出。

4）如果遇到任何其他的操作符，如（“+”， “*”，“（”）等，从栈中弹出元素直到遇到发现更低优先级的元素(或者栈为空)为止。弹出完这些元素后，才将遇到的操作符压入到栈中。有一点需要注意，只有在遇到" ) "的情况下我们才弹出" ( "，其他情况我们都不会弹出" ( "。也就是说这种操作，" + "的优先级最低，"

5）如果我们读到了输入的末尾，则将栈中所有元素依次弹出。

规则很多，还是用实例比较容易说清楚整个过程。以上面的转换为例，输入为a + b * c + (d * e + f)*g，处理过程如下：

1）首先读到a，直接输出。

2）读到“+”，将其放入到栈中。

3）读到b，直接输出。

此时栈和输出的情况如下：

4）读到“*”，因为栈顶元素"+"优先级比" * " 低，所以将" * "直接压入栈中。

5）读到c，直接输出。

此时栈和输出情况如下：

6）读到" + "，因为栈顶元素" * "的优先级比它高，所以弹出" * "并输出， 同理，栈中下一个元素" + "优先级与读到的操作符" + "一样，所以也要弹出并输出。然后再将读到的" + "压入栈中。

此时栈和输出情况如下：

7）下一个读到的为"("，它优先级最高，所以直接放入到栈中。

8）读到d，将其直接输出。

此时栈和输出情况如下：

9）读到" * "，由于只有遇到" ) "的时候左括号"("才会弹出，所以" * "直接压入栈中。

10）读到e，直接输出。

此时栈和输出情况如下：

11）读到" + "，弹出" * "并输出，然后将"+"压入栈中。

12）读到f，直接输出。

13）接下来读到“）”，则直接将栈中元素弹出并输出直到遇到"("为止。这里右括号前只有一个操作符"+"被弹出并输出。

14）读到" * "，压入栈中。读到g，直接输出。

15）此时输入数据已经读到末尾，栈中还有两个操作符“*”和" + "，直接弹出并输出。

至此整个转换过程完成。程序实现代码后续再补充了。

 3）转换的另一种方法

计算就好说了，根据后缀表达式，遇到运算符则弹出两个操作数，计算后压栈，最后栈顶元素为计算结果

 
 } //将栈顶元素弹出并放到p 

聪明的你帮助C小加解决了中缀表达式到后缀表达式的转换（详情请参考“郁闷的C小加（一）”），C小加很高兴。但C小加是个爱思考的人，他又想通过这种方法计算一个表达式的值。即先把表达式转换为后缀表达式，再求值。这时又要考虑操作数是小数和多位数的情况。

第一行输入一个整数T，共有T组测试数据（T<10)。
每组测试数据只有一行，是一个长度不超过1000的字符串，表示这个运算式，每个运算式都是以“=”结束。这个表达式里只包含+-*/与小括号这几种符号。其中小括号可以嵌套使用。数据保证输入的操作数中不会出现负数并且小于1000000。
数据保证除数不会为0。

对于每组测试数据输出结果包括两行，先输出转换后的后缀表达式，再输出计算结果，结果保留两位小数。两组测试数据之间用一个空行隔开。

2694:逆波兰表达式