F - 逆ポーランド記法
Editorial
/
「 l と r を演算子 s[i] で計算した結果を a とする」 とは, lを左の被演算子, rを右の被演算子として 演算子 s[i] によって加算・減算・乗算を行うものである. 例えば s[i] が
データ構造 X にプッシュ・ポップする値は 0 から 9 の範囲とは限らないことに注意せよ.
データ構造 X が空の状態でポップするとプログラムはエラーを出して停止し,計算の出力は得られない.
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
数式を表す記法に 逆ポーランド記法 がある.
本問題では, 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) のトークンを意味する.
「 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プログラムの入力に B を与えた時にQプログラムはエラーを出さない
- Sプログラムの入力に A を与えた時の出力とQプログラムの入力に B を与えた時の出力は等しい
入力
入力は逆ポーランド記法の式を表す文字列 A の1行からなる.A
- 1 \leq |A| \leq 100
- 文字列 A は
0123456789+-*
からなる文字列である - 文字列 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
数ひとつだけの文字列も正しい逆ポーランド記法の式である.