応用情報技術者 2016年 秋期 午前2 問03
問題文
逆ポーランド表記法で表された式を評価する場合、途中の結果を格納するためのスタックを用意し、式の項や演算子を左から右に順に入力し処理する。スタックが図の状態のとき、入力が演算子となった。このときに行われる演算はどれか。ここで、演算は中置表記法で記述するものとする。
選択肢
ア：A 演算子 B
イ：B 演算子 A
ウ：C 演算子 D（正解）
エ：D 演算子 C
逆ポーランド表記法の演算処理【午前2 解説】
要点まとめ
- 結論：逆ポーランド表記法では、演算子が来たらスタックの上から2つの値を取り出し、左側が先に取り出した値、右側が後に取り出した値となる。
- 根拠：スタックは後入れ先出し（LIFO）構造であり、演算子適用時は直前の2つのオペランドを取り出すため、順序が重要。
- 差がつくポイント：オペランドの取り出し順序を誤ると計算結果が変わるため、左オペランドが先に取り出した値、右オペランドが後に取り出した値であることを正確に理解すること。
正解の理由
逆ポーランド表記法（後置記法）では、演算子が現れた時点でスタックの上から2つの値を取り出します。
このとき、最初に取り出す値が右オペランド、次に取り出す値が左オペランドとなります。
問題の図でスタックの上から順にD、C、B、Aと積まれている場合、演算子が来たらDとCを取り出し、演算は「C 演算子 D」となります。
したがって、正解はウ: C 演算子 Dです。
このとき、最初に取り出す値が右オペランド、次に取り出す値が左オペランドとなります。
問題の図でスタックの上から順にD、C、B、Aと積まれている場合、演算子が来たらDとCを取り出し、演算は「C 演算子 D」となります。
したがって、正解はウ: C 演算子 Dです。
よくある誤解
スタックから取り出す順序を逆に考え、先に取り出した値を左オペランドと誤認することが多いです。
また、スタックの上から順に左から右に演算するイメージを持つと混乱します。
また、スタックの上から順に左から右に演算するイメージを持つと混乱します。
解法ステップ
- 逆ポーランド表記法の演算処理では、演算子が来たらスタックから2つの値を取り出す。
- 取り出す順序は「右オペランドが先、左オペランドが後」であることを確認する。
- 問題の図でスタックの上から順にD、C、B、Aと積まれていることを把握する。
- 演算子適用時に取り出す2つの値はD（先に取り出す）とC（次に取り出す）。
- よって演算は「C 演算子 D」となる。
選択肢別の誤答解説
- ア: A 演算子 B
スタックの下の方の値であり、演算子適用時に取り出す値ではないため誤り。 - イ: B 演算子 A
同様にスタックの下位の値で、演算子適用時の対象外。 - ウ: C 演算子 D
スタックの上位2つの値を正しい順序で取り出しているため正解。 - エ: D 演算子 C
取り出し順序が逆で、右オペランドと左オペランドが入れ替わっているため誤り。
補足コラム
逆ポーランド表記法は中置記法の括弧の必要性を排除し、計算機での式評価を効率化します。
スタックを用いることで演算子の優先順位や括弧の処理を気にせずに計算が可能です。
また、演算子適用時のオペランドの取り出し順序は計算結果に直結するため、正確な理解が重要です。
スタックを用いることで演算子の優先順位や括弧の処理を気にせずに計算が可能です。
また、演算子適用時のオペランドの取り出し順序は計算結果に直結するため、正確な理解が重要です。
FAQ
Q: 逆ポーランド表記法で演算子が来た時、なぜ2つの値を取り出すのですか？
A: 演算子は2つのオペランドに対して演算を行うため、直前に積まれた2つの値を取り出して計算します。
A: 演算子は2つのオペランドに対して演算を行うため、直前に積まれた2つの値を取り出して計算します。
Q: スタックから取り出す順序はなぜ右オペランドが先なのですか？
A: スタックは後入れ先出しのため、最後に積まれた値が先に取り出され、これが右オペランドに対応します。
A: スタックは後入れ先出しのため、最後に積まれた値が先に取り出され、これが右オペランドに対応します。
関連キーワード: 逆ポーランド記法、スタック、式評価、後置記法、演算子の順序
\ せっかくなら /
応用情報技術者を
クイズ形式で学習しませんか？
クイズ画面へ遷移する→
すぐに利用可能！