令和3年度 I-2-5

解説

この問題で問われていること

中置記法「(A+B÷C)×(D-F)」を表す構文木を、深さ優先順(左部分木、右部分木、節の順)で走査し、逆ポーランド表記法(後置記法)に変換する問題。

解き方

① 逆ポーランド=左部分木→右部分木→演算子の順。÷は+より先に計算するので B÷C がひとまとまり
② 左: A (B C ÷) + → A B C ÷ +、右: D F −、最後に×
③ A B C ÷ + D F − ×(①)

正解が正しい理由

構文木は根が×、左の子が+(その子はAと、B÷Cを表すサブツリー)、右の子が-(その子はDとF)という構造になる。左部分木・右部分木・節の順に走査すると、まず左部分木(+側)を処理し、その中でもさらに左(A)→右(B÷Cのサブツリー:B→C→÷)→節(+)の順でAとB, C, ÷, +が出力され「A B C ÷ +」となる。次に右部分木(-側)をD→F→-の順で処理し「D F -」となる。最後に根の×を出力する。全体をつなげると「A B C ÷ + D F - ×」となり、①が正しい。

各選択肢について

• ① 左部分木(A B C ÷ +)、右部分木(D F -)、根(×)の順に出力した「A B C ÷ + D F - ×」が、深さ優先順(左・右・節)での走査結果と一致しており、これが正答。
• ② 「A B + C ÷ D F - ×」は、+とB÷Cの構造(Aと÷の間に+を挟む位置)が構文木の構造と一致しておらず誤り。
• ③ 「A B C ÷ + D × F -」は、×とFの順序が構文木の根(×)を最後に出力するという走査順と一致しておらず誤り。
• ④ 「× + A ÷ B C - D F」は、根の記号(×)を先頭に出力しており、後置記法(節を最後に出力する)の原則と一致していないため誤り。
• ⑤ 「A B + C ÷ D × F -」も、+とC÷の位置関係、および×とFの順序が構文木の構造と一致しておらず誤り。

覚えるべきポイント

構文木を深さ優先順(左部分木→右部分木→節)で走査すると、その式の逆ポーランド表記法(後置記法)が得られる。この問題のように演算子の優先順位(÷が先に計算される部分木になっている)を反映した構文木の形を正しく捉えることが、変換の正確さの鍵となる。