図は，逆ポーランド表記法で書かれた式abcd+++をスタックで処理するときのスタックの変化の一部を表している。
この場合，スタックの深さは最大で4となる。
最大のスタックの深さが最も少ない逆ポーランド表記法の式はどれか。
正答1
解説
正解は1です。
逆ポーランド表記法では、オペランドはスタックに積み、演算子が来たら上の2つを取り出して計算し、結果を積みます。
図では、abcd+++を処理すると、a・b・c・dの4つが積まれた時点で深さが最大の4になり、その後c+d、b+c+d、a+b+c+dと減っていく様子が示されています。
各選択肢について、スタックの深さの変化をたどります。
【選択肢別解説】
1：○ ab+c+d+では、a、bを積んで深さ2、+で1、cを積んで2、+で1、dを積んで2、+で1です。
最大の深さは2で、最も少なくなります。
2：× ab+cd++では、ab+の後に深さ1、c、dを積んで深さ3になります。
最大の深さは3です。
3：× abc++d+では、a、b、cを積んだ時点で深さ3になります。
最大の深さは3です。
4：× abc+d++では、a、b、cで深さ3、+で2、dで再び3になります。
最大の深さは3です。
【ポイント】
オペランドを1つ積むたびにすぐ演算子で減らす形の式ほど、スタックの深さは小さくなります。
深さを数えるときは、オペランドで+1、2項演算子で−1と数えると速く解けます。