FUNDAMENTAL INFORMATION TECHNOLOGY ENGINEER
基本情報技術者の問題解説：次の後置記法をスタックで評価したとき、戻り値はどれか。 文字…
問題
次の後置記法をスタックで評価したとき、戻り値はどれか。
文字列型の配列: token ← {"5", "3", "+", "2", "*", "4", "-"}
整数型のスタック: st
for (tokenの各要素 t を先頭から順に取り出す)
if (tが数値である)
push(st, 数値化(t))
else
b ← pop(st)
a ← pop(st)
if (t = "+") push(st, a ＋ b) endif
if (t = "*") push(st, a × b) endif
if (t = "-") push(st, a － b) endif
endif
endfor
return pop(st)- ア 10
- イ 12（正解）
- ウ 14
- エ 16
出典：オリジナル問題｜参考範囲：試験要綱Ver.5.5 / FEシラバスVer.9.2 科目B範囲
正解と解説
正解：12
数値はpushし、演算子が出たら右オペランドbを先にpopし、左オペランドaを次にpopします。減算ではa-bの順序が重要です。
| token | 処理後スタック |
|---|---|
| 5 | {5} |
| 3 | {5,3} |
| + | {8} |
| 2 | {8,2} |
| * | {16} |
| 4 | {16,4} |
| - | {12} |
最終的に(5+3)×2-4=12となります。popの順序を逆にすると減算の結果が変わってしまいます。
選択肢の見分け方：10や14は最後の減算順序を誤った場合、16は4を引く前の途中値です。演算子では右辺bを先にpopする点を押さえておきましょう。
このアルゴリズムの正体：これは後置記法（逆ポーランド記法）を1回の走査で評価する定石で、各トークンを1度ずつ処理するためトークン数n に対して計算量はO(n)です。括弧や演算子の優先順位を見ずに済むのが利点で、この式でもスタックに同時に載る要素は最大2個に収まります。
この問題について
公開問題・サンプル問題の形式、擬似言語記法、アルゴリズム読解・トレース・空欄補充・セキュリティ事例判断の傾向を参考にした独自問題です。本文・数値・選択肢は新規作成しています。
公式試験問題、公開問題、市販教材、外部問題サイトの問題文を転載・改題したものではありません。