基本情報 平成25年度 春期 問6｜テクノロジ系に関する問題

答えは a「ab+c+d+」 です。

「逆ポーランド表記法」は、計算の数字を先に書いて、最後に＋−×÷の記号を書く書き方。「＋を見たら直前の2つを足す」と覚えればOK。

スタックは「お皿を重ねる山」と思ってください。数字が来たら積み、+を見たら上2枚を取り出して計算結果を1枚積む。

aの式は早めに「＋」が出てくるので皿の山が深く積もらず、最大2段で済みます。

👉 覚え方：「＋が早く来る＝皿が少なく済む」。

ほかの選択肢：b/c/d は数字を先に積んでから後で＋＋＋とまとめて足すので、山が3段以上になります。

なぜこれが正解か

正解は a。逆ポーランド記法（後置記法・RPN）はオペランドをスタックにpushし、演算子で上位2要素をpop→演算→結果をpush。スタック深さは「未処理オペランドの最大蓄積数」で決まる。

aの式 `ab+c+d+` をトレース: push a(1)→push b(2)→`+`で1要素に集約(1)→push c(2)→`+`で集約(1)→push d(2)→`+`で集約(1)。最大深さ＝2。各選択肢中で最も浅い。

各選択肢の解説

• b `ab+cd++`：a,b積→+で1→c積(2)→d積(3)→深さ3→++で集約。最大3。
• c `abc++d+`：a,b,c積で深さ3→++で1→d積(2)→+で1。最大3。
• d `abc+d++`：a,b,c積で深さ3→+で2→d積で深さ3→++で1。最大3。

覚え方・ひっかけ注意

「演算子が早く出る式ほどスタック浅い」。コンパイラの式評価でも同じ理屈で、左結合の中置式を後置に変換するときに演算順序を工夫すると深さを抑えられる。スタック深さは関数呼出時のレジスタ退避や仮想機械の最適化指標として実務で重要。

理論的背景

逆ポーランド記法（Reverse Polish Notation, RPN）はポーランドの論理学者ヤン・ウカシェヴィチの前置記法を反転したもので、演算子をオペランドの後ろに置く。括弧不要で曖昧性なく式を表現でき、スタックマシンとの親和性が極めて高い。スタック深さは式木の右偏走査における未処理オペランド最大数で、AST（抽象構文木）の「Strahler数」とも関連する。

実務での使われ方

Java仮想マシン（JVM）・CPython・PostScript・Forth等の処理系が後置記法ベースのスタックマシンを採用。コンパイラのコード生成では、レジスタ割付前の中間表現として後置記法化し、スタック深さを抑えるために演算順序を入れ替える「Sethi-Ullman アルゴリズム」を用いる。これは「右部分木がより深い場合は右を先に評価」する古典的最適化で、必要レジスタ数（≒スタック深さ）を最小化する。

試験での位置づけ

FE/AP/高度試験のアルゴリズム・コンパイラ分野で定番。①中置→後置変換（操車場アルゴリズム）、②後置式の評価（スタック使用）、③スタック深さ計算、の3パターンで反復出題される。本問はパターン③でやや高度だが、各選択肢を機械的にトレースすれば確実に解ける。

選択肢の発展補足

操車場アルゴリズム（Shunting-yard algorithm, Dijkstra考案）は中置記法を後置記法に変換する標準手法で、演算子の優先順位・結合性を扱う。同じ計算結果になる後置式は複数存在し、結合則が成り立つ`+`,`×`なら順序入替で最適化可能だが、減算・除算は順序固定。本問の`a+b+c+d`は結合則により`((a+b)+c)+d`と`(a+b)+(c+d)`のいずれも正しいが、スタック深さは異なる。これは並列計算における式の分散表現の理論にも繋がる重要概念。