求一个可能包含加、减、乘、除、乘方运算的中缀表达式的值。 在计算机中，我们常用栈来解决这一问题。

首先将中缀表达式转换到后缀表达式，然后对后缀表达式求值。

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

第一行为测试数据的组数 N 。

接下来的 N 行，每行是一个中缀表达式。 每个表达式中，圆括号、运算符和运算数相互之间都用空格分隔，运算数是整数。一般运算数可正可负（负数的符号和数字之间无空格），指数一定为自然数(0 和正整数)。

不必考虑除 0 的情况。每个运算数均可由 int 放下。不必考虑溢出。中缀表达式的字符串长度不超过 600 。乘方的优先级比乘除都高，结合性是向左结合，如 2 ^ 3 ^ 4 表示 ( 2 ^ 3 ) ^ 4 = 4096。 除法的商向下取整。

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

电子学会六级

电子学会等级考试