← 返回题目列表

AtCoder · kupc2015_f

F. 逆波兰表示法

中文机器翻译题面 查看原题

問題文

表达数学表达式的符号 逆波兰表示法 有 。 在这个问题中,我们将使用一位整数( 0 从 9 )和 二元运算符(加法 + , 減算 - , 乗算 * )称为标记,由连接的标记组成的字符串表示逆波兰表示法的表达式。
例如,逆波兰表示法的表达式为 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] 表示 i+1 番目 (0 \leq i \leq |s|-1) 。
「 l 和 我讨厌 r 至操作员 用 s[i] 计算的结果是 “ a ”的意思 l是左操作数, r作为右操作数运算符 使用 s[i] 执行加法、减法和乘法。 例如 s[i] 是 - 如果 a 中缀表示法 意思是替换 l - r 。
数据结构 压入和弹出到 X 的值是 请注意,这不一定是 0 从 9 的范围。 如果
数据结构 压入和弹出到 X 为空时弹出,程序将因错误而停止,并且不会获得任何输出。

代码中的数据结构 如果 X 是一个堆栈,这个函数将正确计算逆波兰表示法的表达式,但它会错误地创建一个队列,并且无法正确计算。 因此,您决定重新排列输入表达式,并让队列中创建的程序输出正确的答案。 堆栈中使用

X 创建的代码是S程序, 使用 X 作为队列创建的代码称为Q程序。
逆波兰表示法表达式 给出 A ,因此满足以下条件。 查找并打印 B 。 这是一种

  • B 表示 A 是一个重新排列
  • Q程序输入 Q 程序在给出 B 时不会给出错误
  • S程序输入 给出 A 时的输出和 Q 程序的输入为 给出 B 时的输出是相同的


入力

输入是表示逆波兰表示法表达式的字符串 由一行组成: A 。 是由
A
  • 1 \leq |A| \leq 100
  • 文字列 A 表示 0123456789+-* 组成的字符串
  • 文字列 A 是逆波兰表示法的有效表达式

出力

满足问题条件的字符串 在一行中输出 B。 如果有多个 B,则输出一个。
B

入力例1

54-

出力例1

45-

入力 54- 的正确输出是 只有一个 45- 。 如果我们使用中缀表示法将

入力例2

321+-

出力例2

12+3-

入力 321+- 赋予 S 程序时编写计算, 3-(2+1) 并且S程序的输出是 0 。

入力例3

2

出力例3

2

仅包含一个数字的字符串也是逆波兰表示法的有效表达式。