応用情報技術者試験 令和5年秋 午前問3 解説付き過去問

この問題は、逆ポーランド表記法（後置記法）で記述された式を正しく評価できるかを問うものです。逆ポーランド表記法では演算子をオペランドの後に記述し、括弧なしで計算順序が明確に示されるという特徴があります。

1. 逆ポーランド表記法の基礎
   逆ポーランド表記法では、演算子（＋、－、×、÷など）は2つの項の後に記述されます。

   たとえば、中置記法の「A ＋ B」は、逆ポーランド表記では「AB＋」と記述されます。

   このような式を評価するためには、スタックと呼ばれるデータ構造を用います。

   
   
   
2. スタックによる評価手順
   スタックを使って、左から順に処理していきます。
   1. A（16）を積む → [16]
      
      
   2. B（8）を積む → [16, 8]
      
      
   3. C（4）を積む → [16, 8, 4]
      
      
   4. D（2）を積む → [16, 8, 4, 2]
      
      
   5. 「－」を実行：4 − 2 = 2 → [16, 8, 2]
      
      
   6. 「×」を実行：8 × 2 = 16 → [16, 16]
      
      
   7. 「＋」を実行：16 ＋ 16 = 32 → [32]
      
      

   スタックの最終値 32 が演算結果となります。

   
   
   
3. 別解：中置記法に戻して計算
   逆ポーランド記法の「ABCD－×＋」を中置記法に戻すと、以下のようになります。
   1. 「CD－」→「C－D」
   2. 「B(C－D)×」→「B × (C－D)」
   3. 「A＋B × (C－D)」

   値を代入すると、

   16 ＋ 8 × (4 − 2) = 16 ＋ 8 × 2 = 16 ＋ 16 = 32

   
   
   

したがって、この式の演算結果は 32 です。