AT_kupc2015_f.逆ポーランド記法

问题描述

有一种算式的表达方法被称作逆波兰表达式。在这个问题中，单个数字（$0-9$）和加减乘三个双目运算符（+-*）被称作“令牌”（token）。我们以一串“令牌”组成字符串来表达一个逆波兰式。

举个例子。如果有一个逆波兰记法的表达式 $32-1+$，这个表达式的中缀表达式为 $(3-2)+1$，计算的结果为 $2$。逆波兰表达式的计算方法的伪代码如下给出：

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程序大赛