問題プレビューID: fb64ddcb

問 6

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

解説

各逆ポーランド表記法の式をスタックで処理したときの最大のスタックの深さを調べる。

ア ab+c+d+：a，b を積み（深さ 2），＋で 1 に減り，c で 2，＋で 1，d で 2，＋で 1。最大は 2。
イ ab+cd++：a，b を積み（2），＋で 1，c，d を積み（3），＋で 2，＋で 1。最大は 3。
ウ abc++d+：a，b，c を積み（3），＋で 2，＋で 1，d で 2，＋で 1。最大は 3。
エ abc+d++：a，b，c を積み（3），＋で 2，d で 3，＋で 2，＋で 1。最大は 3。

最大のスタックの深さが最も少ないのはアである。よって正解は「ア」である。