平成25年度 春期 基本情報技術者試験 午前 問6
テクノロジ／アルゴリズム図は，逆ポーランド表記法で書かれた式 abcd＋＋＋ をスタックで処理するときのスタックの変化の一部を表している。この場合，スタックの深さは最大で4となる。最大のスタックの深さが最も少ない逆ポーランド表記法の式はどれか。
出典：平成25年度 春期 基本情報技術者試験 午前 問6
- アab＋c＋d＋
- イab＋cd＋＋
- ウabc＋＋d＋
- エabc＋d＋＋
正解：ア
解説
逆ポーランド表記式を1文字ずつスタックで処理し，オペランドをプッシュ，演算子が来たら上位2つをポップして計算結果をプッシュする，としてそれぞれの式の最大スタック長をシミュレートします。「ab＋c＋d＋」は演算子の直後にすぐ加算してスタックを1要素に戻すため最大深さ2で済みますが，他の三つはオペランドを続けて積んでから演算するため最大深さ3になります。
選択肢ごとの解説
- ア正しい。a，bを積んで即座に加算して1要素に戻す，という操作をc，dについても繰り返すため，スタックは常に2要素以下で済み，最大深さは2です。
- イ誤り。c，dを続けて積んでから加算するため，その時点でスタックに3要素（ab和，c，d）が並び，最大深さは3になります。
- ウ誤り。a，b，cを続けて積んでから演算を始めるため，その時点でスタックに3要素が並び，最大深さは3になります。
- エ誤り。a，b，cを続けて積んでから加算するため，その時点でスタックに3要素が並び，最大深さは3になります。