アルゴリズムとプログラミング
平成25年度 春期 基本情報技術者試験 午前 問6
図は，逆ポーランド表記法で書かれた式 abcd+++ をスタックで処理するときのスタックの変化の一部を表している。この場合，スタックの深さは最大で 4 となる。最大のスタックの深さが最も少ない逆ポーランド表記法の式はどれか。
スタックの変化（下から上へ積む）: [a, b, c, d] → [a, b, c+d] → [a, b+c+d] → [a+b+c+d]
- ア ab+c+d+
- イ ab+cd++
- ウ abc++d+
- エ abc+d++
出典：平成25年度 春期 基本情報技術者試験 午前 問6
答えと解説を見る
正解：ア
覚える知識
逆ポーランド表記(後置表記)の式変換
逆ポーランド表記は演算子を被演算子の後ろに置く記法で、スタックで左から順に評価できる。
この問題で必要なこと
後置表記は左から読み、オペランドはpush、演算子は上2つをpopして計算し結果をpushする。演算子を早く挟む式ほどスタックが浅い。
ひっかけ
abcd+++のように全オペランドを先に積む式を選ぶと深さが最大になる。
この知識の出題：本試験系 5 回・免除試験 10 回（公開問題での観測値）