情報に関する理論(全53問中39問目)
No.39解説へ
逆ポーランド表記法で表された式を評価する場合，途中の結果を格納するためのスタックを用意し，式の項や演算子を左から右に順に入力し処理する。スタックが図の状態のとき，入力が演算子となった。このときに行われる演算はどれか。ここで，演算は中置表記法で記述するものとする。
出典：平成20年秋期 問 8
- A 演算子 B
- B 演算子 A
- C 演算子 D
- D 演算子 C
広告
解説
逆ポーランド表記法は、演算子を被演算子の右側に記述する表記法です。例えば、A＝4×5－6＋3×2という式を逆ポーランド表記法で記述すると、A45×6－32×＋＝となります。
上記の逆ポーランド表記法の式を左から順にスタックに積んでいくことを考えると、
というようにスタックに積まれていきます。次に"×"が現れたときには元の式の4×5を行いたいので、スタックの上の二つを取り出して演算子が示す演算4×5＝20を行い、その結果をスタックに積みます。
次に"6"を積むと、"－"の演算子が現れます。今度はスタックから"20"と"6"を取り出して20－6を行い、その結果をスタックに積みます。
このように演算子が現れたときには、スタックの上から2つ目の値を前の項、スタックの1番上の値を後ろの項として、演算を行っていくことになります。設問のスタックでいえば、Cが前の項、Dが後ろの項となります。したがって行われる演算は「C 演算子 D」です。
上記の逆ポーランド表記法の式を左から順にスタックに積んでいくことを考えると、
広告