応用情報技術者試験 応用情報技術者試験 平成28年度秋期 午前 問3: 逆ポーランド表記法で表された式を評価する場合，途中の結果を格納するためのスタックを用意し，式の項や演算子を左から右に順に入力し処理する。スタックが図の状態のとき

問題本文

逆ポーランド表記法で表された式を評価する場合，途中の結果を格納するためのスタックを用意し，式の項や演算子を左から右に順に入力し処理する。スタックが図の状態のとき，入力が演算子となった。このときに行われる演算はどれか。ここで，演算は中置表記法で記述するものとする。

選択肢

• ア.A 演算子 B
• イ.B 演算子 A
• ウ.C 演算子 D
• エ.D 演算子 C

正解

ウ. C 演算子 D

解説

逆ポーランド表記法(後置記法)はスタックで評価し、演算子が入力されたら「直前に積まれた2つの値を取り出して計算し、結果を積み直す」のが核心。図のスタックは下からA・B・C・Dの順に積まれており、最後に積まれた(最上位の)2つは C と D で、D が一番上にある。演算子が来るとまず最上位のDを取り出し(これが第2被演算子)、次にCを取り出す(これが第1被演算子)。中置表記では先に取り出される側が右の項、後に取り出される側が左の項になるため、復元される式は「C 演算子 D」となり、正解はウである。

選択肢ごとの解説

• ア.A と B はスタックの底側にあり、まだ取り出されない2つである。最上位のC・Dより先に演算対象になることはないため誤り。
• イ.AとBはこの時点で取り出される対象ではなく、また被演算子の左右の順序も逆であるため誤り。
• ウ.最上位の2要素D・Cを取り出し、後に取り出したC(下側)を左、先に取り出したD(上側)を右に置くと「C 演算子 D」となり、後置記法の評価規則に合致するため正しい。
• エ.取り出す要素はC・Dで正しいが、被演算子の左右が逆。先に取り出される最上位のDは右側、次のCが左側になるため「D 演算子 C」ではなく「C 演算子 D」が正しく、誤り。