基本情報技術者 2013年春期午前（科目A）問06

問題文

図は、逆ポーランド表記法で書かれた式abcd+++をスタックで処理するときのスタックの変化の一部を表している。この場合、スタックの深さは最大で4となる。最大のスタックの深さが最も少ない逆ポーランド表記法の式はどれか。

🖊️ 解答を隠して解いてみる

選択肢

ア：ab+c+d+（正解）

イ：ab+cd++

ウ：abc++d+

エ：abc+d++

🔒 解説は解答すると表示されます

逆ポーランド記法のスタック深さ【午前解説】

逆ポーランド表記式abcd+++ の例が示す通り、スタック深さを最小にする式はどれか

正解の理由

正解: ア

逆ポーランド記法（後置記法）での評価ルールに従うと、オペランドを読むとスタックに値を積み（深さ +1）、二項演算子を読むとスタックから2つ取り出して結果を1つ戻す（深さ -1）ので、各トークンでの深さ推移を追えば最大深さが求まります。選択肢アの列は「a b + c + d +」という順になり、演算子が早めに適用されるため同時に積まれるオペランド数が最小で、最大深さが2で最小になります。

解法ステップ

式を左からトークン（オペランド／演算子）に分ける。
初期depth = 0、max_depth = 0とする。
各トークンを順に処理：オペランドならdepth += 1、二項演算子ならdepth -= 1（2つ引いて1つ戻すため差分は -1）。
各ステップでmax_depth = max(max_depth, depth) を更新する。
最終的なmax_depthがその式の最大スタック深さ。最小のものが正解。

（注意：実装上は演算子でpopする際にdepthが負にならないことを確認する）

選択肢別の誤答解説

ア: ab+c+d+
トークン順と深さ: a(1) → b(2) → +(1) → c(2) → +(1) → d(2) → +(1)。
最大深さ = 2。これが最小で正解。
イ: ab+cd++
トークン順と深さ: a(1) → b(2) → +(1) → c(2) → d(3) → +(2) → +(1)。
最大深さ = 3。c,dを積んでから演算する箇所で深さが増えるため不利。
ウ: abc++d+
トークン順と深さ: a(1) → b(2) → c(3) → +(2) → +(1) → d(2) → +(1)。
最大深さ = 3。連続してオペランドを積み上げるため深さが3になる。
エ: abc+d++
トークン順と深さ: a(1) → b(2) → c(3) → +(2) → d(3) → +(2) → +(1)。
最大深さ = 3。c演算後にdを積むフェーズで深さが3になる。

以上より、アのみ最大深さが2で他は3なのでアが最小となる。

よくある誤解

「演算子が多ければ深くなる」と考える誤解：演算子は値を減らすので、演算子が早く来るほど深さは下がります。
「RPNと中置の結合規則を混同する」：RPNはトークン順で評価され、中置の括弧や優先度の直感は適用されません。
スタック変化を一括で考えず、局所的な増減を見落とすことで誤判定しやすい点に注意してください。

補足コラム

二項演算のみのRPNにおいて、演算子を「早く」出す（オペランドをためすぎない）配置がスタック深さを抑えます。
木構造に対応づけると、RPNの最大スタック深さは評価スタック上で同時に必要な部分木の葉の数に対応します。式をできるだけ左で縮約する（部分式を早く評価する）ほど深さは小さくなります。
実務的には式の実行メモリやレジスタ使用量の目安になるため、コンパイラ最適化や組込み機器のコード生成で重要です。

FAQ

Q1: 二項演算子以外（単項・可変長）の場合はどうする？
A1: 単項演算子はpop1 push1なので深さ変化は0、可変長ならarityに応じてdepth += (1 - arity) のように扱います。

Q2: 中置表記に戻して考えた方が早い？
A2: 中置に戻す必要はなく、RPNは直接スキャンで深さが計算できるため逆変換は不要です。

Q3: 最大深さが同じならどれを選ぶ？
A3: 出題は最小深さを問うので同値なら他条件（例えば文字列の形）で決まるが、今回の選択肢では唯一アが最小です。

関連キーワード: 逆ポーランド記法、RPN、スタック深さ、式評価、後置記法、演算子結合、スタックマシン

← 前の問題へこの年度をクイズで解く次の問題へ →

\ せっかくなら /

基本情報技術者を
クイズ形式で学習しませんか？

クイズ画面へ遷移する→

すぐに利用可能！