问题描述

求一个可能包含加、减、乘、除、乘方运算的中亲表达式的值。

在计算机中，我们常用栈来解决这一问题。首先将中缀表达式转换到后缀表达式，然后对后缀表达式求值。

加、减、乘、除、乘方分别用 +,-,*,/,^ 来表示。表达式可以有圆括号()

输人描述

第一行为测试数据的组数 N。 接下来的N行，每行是一个中缀表达式。每个表达式中，圆括号、运算符和运算数相互之间都用空格分隔，运算数是整数。

一般运算数可正可负(负数的符号和数字之间无空格)，指数一定为自然数(0和正整数)。 不必考虑除0的情况。 每个运算数均可由 int 放下。 不必考虑溢出。

中缀表达式的字符串长度不超过 600，乘方的优先级比乘除都高，结合性是向左结台，如2^3^4表示(2^3)^4=4096，除法的商向下取整。

输出描述

对每一组测试数据输出一行，为表达式的值

样例

2
31 * ( 5 - ( -3 + 25 ) ) + 70 ^ 2
2 * 5 + 6 * ( 7 - 8 ) + 6

4373
10