【习题记录】好题要顶

题记

做题的时候做到一道很解法巧妙的题。所以写篇文章记录一下。

原题：EOlymp 3837

注：但好像在国内网络上测试不了代码？反正我是没能登录。我是从学校内部 OJ 里做的。没事，缕缕思路也很好。

题目中文翻译：

题目描述

所谓后缀表达式，是我们通常用的中缀表达式的另一种形式。中缀表达式的运算符的位置是在它所要计算的两个表达式之间的，而后缀表达式则是在其后面。比如有一个中缀表达式如下：

(<表达式1>) <运算符> (<表达式2>)

要将其转成后缀表达式，则要先递归地将<表达式1>和<表达式2>转成后缀表达式，然后将其变成：

<表达式1> <表达式2> <运算符>

我们一般不习惯这样的表示方式，但好在我们可以用栈轻松处理掉它。具体方法是：从左到右扫描整个表达式，当我们扫描到数时，将其加入栈中，当我们扫描到运算符时，取出两个栈顶元素，计算出结果后重新加入栈中。这样最终栈中只会剩下一个元素，该元素就是整个表达式的计算结果。

现在假设我们有的不是栈而是队列，我们也希望能用相同的操作方式处理一个表达式。唯一不同的是，队列每次加入元素是在队尾，而取出元素是在队头，所以就不适用在原先的后缀表达式上了。我们需要找到另一种表达式使得其适合于队列用相同的方法处理并得出相同的结果。

输入格式

输入第一行包含一个整数N，表示总共有N个后缀表达式需要处理。以下N行每行有一个后缀表达式，其中数用小写字母表示，运算符用大写字母表示。

输出格式

输出共N行，对于每个后缀表达式，输出适合于队列的另一种形式。

样例输入

1 xyPwzIM

样例输出

zwyxIPM

数据规模与约定

对于100%的数据，有1 ≤ N ≤ 20，所有后缀表达式的长度不超过10000。

好像数据比原题弱化了。但问题不大。

思路

首先，值得注意的一点是运算顺序不能变。因为不是所有运算都满足交换律。比如a b ≠ b a a^b \not= b^aab=ba。所以运算顺序一定要注意好。

我们把输入的后缀转换成树。

以样例为例：

我们发现（好惊人的注意力）：这棵树的 BFS 序：MPIxywz，恰好是答案的倒序。通过简单的模拟，我们竟然发现这是对的！因为广搜也通过队列实现，而且入队顺序恰好符合答案所需（也能正好解决运算顺序的问题）。

解决办法真是非常巧妙，但题目也十分鬼畜。思维好题。