逆ポーランド記法とスタック
出典: 平成28年度 秋期 応用情報技術者試験 午前 問3 (IPA)
逆ポーランド表記法で表された式を評価する場合，途中の結果を格納するためのスタックを用意し，式の項や演算子を左から右に順に入力し処理する。スタックが図の状態のとき，入力が演算子となった。このときに行われる演算はどれか。ここで，演算は中置表記法で記述するものとする。
- ア A 演算子 B
- イ B 演算子 A
- ウ C 演算子 D
- エ D 演算子 C
正解と解説を見る
正解: ウ
- ア: A と B はスタックの下の方にあり、この演算では使いません。
- イ: A と B はスタックの下の方にあり、この演算では使いません。
- ウ: スタックの上の 2 つ (C と D) を取り出し、先に積まれた C を左にして C 演算子 D を計算するので正しい答えです。
- エ: C と D の順番が逆です。先に積まれた C が左側になります (例: C D − は C − D)。
ポイント
- 逆ポーランド記法の式は、項が来たらスタックに積み、演算子が来たら上から 2 つを取り出して計算 し、結果を積みます。
- 先に積まれた方 (下にある C) が演算子の左、後から積まれた方 (一番上の D) が右になるので、C 演算子 D を計算します。