【习题记录】好题要顶

题记做题的时候做到一道很解法巧妙的题。所以写篇文章记录一下。原题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恰好是答案的倒序。通过简单的模拟我们竟然发现这是对的因为广搜也通过队列实现而且入队顺序恰好符合答案所需也能正好解决运算顺序的问题。解决办法真是非常巧妙但题目也十分鬼畜。思维好题。