基本情報技術者試験 無料問題 10 / 10 ・ 分野4: 科目B アルゴリズムとプログラミング分野
関数 evalRpn は、逆ポーランド表記法の式を配列 t で受け取り、スタックを使って計算した値を返す。t の要素は、0 以上なら数、-1 なら減算（－）、-2 なら乗算（×）を表す。evalRpn を t = {9, 2, -1, 3, -2, 4, -1} として呼び出したときの戻り値はどれか。 注記: 配列の要素番号は1から始まる。forの終了値と増分は、繰返しの開始時に1回だけ評価する。 〔プログラム〕 ○整数型: evalRpn(整数型の配列: t) 整数型の配列: st ← {0, 0, 0, 0, 0} 整数型: sp ← 0 整数型: i, x, y for (i を 1 から t の要素数 まで 1 ずつ増やす) if (t[i] ≧ 0) sp ← sp + 1 st[sp] ← t[i] else y ← st[sp] x ← st[sp - 1] sp ← sp - 1 if (t[i] = -1) st[sp] ← x - y else st[sp] ← x × y endif endif endfor return st[1]
- 17
- 25
- -7
- -1
正解と解説を見る
正解: A
正解の理由
逆ポーランド表記法は、数をスタックに積み、演算子が来たら上の2つを取り出して計算した結果を積み直す。先に積んだ方が x（左の項）、後に積んだ方が y（右の項）になる。
| 読んだもの | スタック（下→上） |
|---|---|
| 9, 2 | 9, 2 |
| －（-1） | 7（9 - 2） |
| 3 | 7, 3 |
| ×（-2） | 21 |
| 4 | 21, 4 |
| －（-1） | 17（21 - 4） |
戻り値は 17 で、中置記法では (9 - 2) × 3 - 4 にあたる。
違う選択肢
「25」… 減算の左右を逆（y - x）にした結果で、-7 → -21 → 4 - (-21) = 25 となる。
「-1」… 並んだ順に中置記法の式 9 - 2 × 3 - 4 と読み、乗算を先にした結果である。
「-7」… (9 - 2) × (3 - 4) と、後ろの減算を先に計算した結果である。
押さえどころ
逆ポーランド表記法は括弧が要らず、左から1回読むだけで計算できる。減算や除算では、スタックから先に取り出した値が右の項になる点を間違えやすい。