AT_kupc2015_f 逆ポーランド記法

## 问题描述 有一种算式的表达方法被称作[逆波兰表达式](//baike.baidu.com/item/%E9%80%86%E6%B3%A2%E5%85%B0%E8%A1%A8%E8%BE%BE%E5%BC%8F/9841727)。在这个问题中，单个数字（$0-9$）和加减乘三个双目运算符（`+-*`）被称作“令牌”（`token`）。我们以一串“令牌”组成字符串来表达一个逆波兰式。 举个例子。如果有一个逆波兰记法的表达式 $32-1+$，这个表达式的中缀表达式为 $(3-2)+1$，计算的结果为 $2$。逆波兰表达式的计算方法的伪代码如下给出： ```cpp calc(s) { 初始化一个空的X for (i in [0 .. |s|-1]) { if (s[i]是数字) { X.push(s[i]) } else { r = X.pop() l = X.pop() 求出l和r按照运算符s[i]计算的结果记作a X.push(a) } } ans = X.pop() return ans } ``` 该程序的输入 $s$ 是一个逆波兰式的字符串。$s[i]\quad(0\leq i\leq |s|-1)$ 指 $s$ 的第 $i+1$ “令牌”。 “求出 $l$ 和 $r$ 按照运算符 $s[i]$ 计算的结果记作a”的意思是：$l$ 为左运算数，$r$ 为右运算数，运算符为 $s[i]$，进行加 / 减 / 乘的运算。比如当 $s[i]$ 为 `-` 时，要进行的运算（用中缀表达式表达）为 $l-r$。 应该注意的是：构造后 $X$ 的 `push` / `pop` 操作的有关值均在 $0$ 到 $9$ 的范围的限制之内。当 $X$ 为空时对其进行 `pop` 操作将会导致程序产生错误而停止，不会得到计算的输出。 如果上述代码中构造的 $X$ 是一个栈，那么就应该能正确的计算一个逆波兰表达式；如果错误地使用队列则不能正确的计算。如果将输入的式子进行重新的排列，用队列的程序就应该能够输出正确答案。 我们将 $X$ 为栈的程序称为“$S$ 程序”， $X$ 为队列的程序为“$Q$ 程序”。 给定一个逆波兰式 $A$，要求求出符合以下条件的 $B$： - $B$ 是 $A$ 的一个排列 - 以 $B$ 为输入的 “$Q$ 程序”不会产生错误 - 以 $B$ 为输入的 “$Q$ 程序”的输出与以 $A$ 为输入的“$S$ 程序”的输出相等。

一行逆波兰式的字符串 $A$： ``` A ```

一行满足题目要求的字符串 $B$（如有多个符合条件的 $B$，任意输出一个）： ``` B ``` ## 样例输入输出 ### 样例一 #### 输入 ``` 54- ``` #### 输出 ``` 45- ``` ### 样例二 #### 输入 ``` 321+- ``` #### 输出 ``` 12+3- ``` ### 样例三 #### 输入 ``` 2 ``` #### 输出 ``` 2 ```

- 样例一：对于输入的 $A$ `54-`，仅有一个符合条件的 $B$ 为 `45-` - 样例二：输入 `321+-` 时，“$S$ 程序”得到的中缀表达式为 `3-(2+1)`，最终的输出为 $0$。 - 样例三：单个数字的字符串也是一个正确的逆波兰式。 - $1\leq A\leq100$ - $A$ 是仅含有 `0123456789+-*` 的字符串 - 保证 $A$ 是合法的逆波兰式。 - 题目来源：[京都大学2015程序大赛](//www.kupc.jp/)