SP1683 EXPRESS - Expressions

在通常的算术表达式中，运算符位于两个操作数之间，这种书写方式被称为中缀表示法。例如，表达式 $(x+y)\*(z-w)$ 就是中缀表示法。然而，若将表达式用后缀表示法（逆波兰表示法）书写，则编程求值会更简单。在后缀表示法中，运算符跟在两个操作数之后，操作数本身也可能是表达式。举例来说，$x\ y\ +\ z\ w\ -\ *$ 是上面所述算术表达式的后缀形式。这样书写时，无需使用括号。 计算后缀表达式时，可以使用栈这种数据结构。栈支持两种操作： 1. **push**：将一个数字压入栈顶。 2. **pop**：从栈顶弹出一个数字。 在求值过程中，我们从左到右遍历表达式。当遇到一个数字时，将其压入栈中；当遇到一个运算符时，从栈中弹出两个数字，使用该运算符进行计算，并将结果重新压入栈。以下是处理运算符 O 的伪代码示例： ``` a := pop(); b := pop(); push(b O a); ``` 计算完成后，栈中剩余的那个数字就是表达式的结果。 假设我们用队列来代替栈，队列也有 push 和 pop 操作，但含义有所不同： 1. **push**：将一个数字加入队列末尾。 2. **pop**：从队列前端取出一个数字。 你能否修改给定的后缀表达式，使得使用队列求值时，结果与使用栈求值时相同？

第一行输入一个整数 **T** ($T \leq 200$)，表示测试用例的数量。接下来的 **T** 行中，每行是一个后缀表达式。算术运算符用大写字母表示，数字用小写字母表示。可以假设每个表达式长度小于 10000 个字符。

对于每个输入的表达式，输出一个等价的新的后缀表达式，使得用队列计算时结果与用栈计算时相同。注意，不能假设运算符具有结合性或交换性，这样才能保证输出唯一。 ## 样例输入 ``` 2 xyPzwIM abcABdefgCDEF ``` ## 样例输出 ``` wzyxIPM gfCecbDdAaEBF ``` **本翻译由 AI 自动生成**