応用情報技術者令和5年秋期 午前問3

問3

逆ポーランド表記法(後置記法)で表現されている式ABCD−×+において,A=16,B=8,C=4,D=2のときの演算結果はどれか。逆ポーランド表記法による式AB+は,中置記法による式A+Bと同一である。
  • 32
  • 46
  • 48
  • 94

分類

テクノロジ系 » 基礎理論 » 情報に関する理論

正解

解説

逆ポーランド表記法は、通常の中置記法とは異なり、演算子(+、−、×、÷)を2つの項の後ろに記述する数式の表現方法です。たとえば、中置記法の「1+2」は、逆ポーランド表記法で「12+」と記述されます。

逆ポーランド表記法による数式は、コンピュータがそのように処理するように、スタック(後入れ先出しのデータ構造)を使って以下の手順で答えを求めることができます。
  1. 数式の左側から値を1つずつスタックに積んでいく
  2. 演算子が現れたら、スタックから上2つの値を取り出して演算し、その結果をスタックに積む
  3. 式を最後まで評価し、スタックに残っている値が答えとなる
この問題の式も、次のようにスタックを使って答えを求めることができます。
  1. Aを積む [16]
  2. Bを積む [16, 8]
  3. Cを積む [16, 8, 4]
  4. Dを積む [16, 8, 4, 2]
  5. −なので、4、2を取り出し、4−2の結果である2を積む [16, 8, 2]
  6. ×なので、8、2を取り出し、8×2の結果である16を積む [16, 16]
  7. +なので、16、16を取り出し、16+16の結果である32を積む [32]
式の評価が終わった時点でスタックに残っている32が演算結果となります。したがって「ア」が正解です。

【別解】
式中で最も左にある演算子を起点にして、中置記法の式に戻し、値を代入して演算します。
  1. "CD−"を"C−D"にする
  2. "B(C−D)×"を"B×(C−D)"にする
  3. "AB×(C−D)+"を"A+B×(C−D)"にする
値を当てはめると、

 16+8×(4−2)
=16+8×2
=16+16=32
© 2010-2024 応用情報技術者試験ドットコム All Rights Reserved.

Pagetop