1508_表达式

算术表达式通常是把运算符写在两个运算数的中间（称为“中缀表达式”）。例如(x+y)*(z-w)是一个中缀表达式。然而，如果把表达式写为"后缀表达式"（也称为"逆波兰式"），则更容易用程序计算出结果。在后缀表达式中，运算符写在它的两个运算数的后面。如 x y + z w - * 就是上述算术表达式的后缀表达式形式。注意到，在这种形式下，就不需要使用括号了。

计算后缀表达式，可以使用一个栈来协助。栈是一种数据结构，支持以下两个操作：

1. push ：把一个数放在栈的顶部

2. pop ：取出栈顶部的那个数

计算时，从左到右处理表达式。如果碰到一个数，就把它压进栈。如果碰到一个运算符，就从栈中弹出两个数，执行这个运算，然后把运算结果再压进栈。下面的伪代码更详细地描述了碰到运算符时是如何处理的。

a := pop();
b := pop();
push(b O a);

最后栈中唯一剩下的数，就是表达式的运算结果。

现在我们要用队列来代替栈。队列也有push和pop操作。但它们的意义却有所不同：

1. push ：把一个数插入到队列的尾部

2. pop ：把队列最前面的数取出来。

请你重写前面所给的表达式，它采用队列来协助进行计算，所得的结果必须与采用栈来协助计算后缀表达式所得的结果相一致。

输入第一行是一个整数T ( T ≤ 200 )。接下来的T行，每行有一条后缀表达式。算术运算符用大写字母表示，运算数用小写字母表示。每条表达式的长度少于10000个字符。

为每一条所给的后缀表达式，输出使用队列来计算的表达式，保证其结果与使用栈来计算后缀表达式所得结果相一致。为了确保答案的唯一性，假设所有运算符都不满足结合律，也不满足交换律。

2
xyPzwIM
abcABdefgCDEF

wzyxIPM
gfCecbDdAaEBF