京都大学プログラミングコンテスト2015

F - 逆ポーランド記法


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

問題文

数式を表す記法に 逆ポーランド記法 がある. 本問題では, 1桁の整数 ( 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) のトークンを意味する.
lr を演算子 s[i] で計算した結果を a とする」 とは, lを左の被演算子, rを右の被演算子として 演算子 s[i] によって加算・減算・乗算を行うものである. 例えば s[i]- ならば a に中置記法で言うところの l - r を代入すると言う意味である.
データ構造 X にプッシュ・ポップする値は 0 から 9 の範囲とは限らないことに注意せよ.
データ構造 X が空の状態でポップするとプログラムはエラーを出して停止し,計算の出力は得られない.

コード中のデータ構造 X がスタックならばこの関数は逆ポーランド記法の式を正しく計算するが,誤ってキューで作ってしまい正しい計算をすることができない. そこであなたは,入力する式を並び替えてキューで作ったプログラムに正しい答えを出力させることにした.

X をスタックで作ったコードをSプログラム, X をキューで作ったコードをQプログラムと呼ぶことにする.
逆ポーランド記法の式 A が与えられるので,次の条件を満たすような B を求めて出力せよ.


入力

入力は逆ポーランド記法の式を表す文字列 A の1行からなる.
A
  • 1 \leq |A| \leq 100
  • 文字列 A0123456789+-* からなる文字列である
  • 文字列 A は,正しい逆ポーランド記法の式である

出力

問題の条件を満たす文字列 Bを1行で出力せよ. そのような Bが複数ある場合はどれか一つ出力せよ.
B

入力例1

54-

出力例1

45-

入力 54- に対する正しい出力は 45- のただ一つだけである.

入力例2

321+-

出力例2

12+3-

入力 321+- をSプログラムに与えた時の計算を中置記法で書くと 3-(2+1) であり,Sプログラムの出力は 0 である.

入力例3

2

出力例3

2

数ひとつだけの文字列も正しい逆ポーランド記法の式である.


Source name

京都大学プログラミングコンテスト2015

Submit提出する