平成25年度 春期 午前 問6

✓ これが正解アab＋c＋d＋

解説

英字を2つ積むごとにたたむ式が深さ2で最小です。

逆ポーランド表記法の式は、左から1文字ずつ読んで処理します。英字が現れたらスタックに1つ載せるので深さが1つ増え、演算子が現れたら上の2つを下ろして結果を1つ載せ直すので深さが1つ減ります。この数え方は設問が示した例で確かめられます。abcd＋＋＋ を読むと英字が4つ続いたところでいちばん深くなり、設問が言う最大4と一致します。ですから深さを浅く保つ鍵は、英字を続けて載せないことです。2つ載せた時点で演算子を挟んでたためば、深さは2を超えません。判定の軸は二つで、最初の演算子が来るまでに英字が何個続くかと、そのあと積み直して同じ高さに戻っていないかを見ます。

ほかの選択肢はなぜ違うのか

• イab＋cd＋＋：前半で一度たたんだあと、後半でまた英字を2つ続けて載せています。読み進める途中で3つ載る場面ができるため、いちばん深いところは3になります。
• ウabc＋＋d＋：始めに英字が3つ続くので、その時点で3つ載ります。あとから演算子を2つ並べてたたんでも、いったん増えた高さはさかのぼって減りません。
• エabc＋d＋＋：始めに英字が3つ続いて3つ載り、1つたたんだあとにまた英字を載せるので、途中でもう一度3つに戻ります。いちばん深いところは3のままです。