平成30年度 I-2-5

解説

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

中間記法の数式a×b+c÷dを、後置記法(逆ポーランド記法)に変換したときの表記を選ぶ問題。

解き方

① ×・÷は+より先に計算する。後置記法=左の部分→右の部分→演算子の順に並べる
② a×b+c÷d=(a×b)+(c÷d) → 左は ab×、右は cd÷、最後に +
③ ab×cd÷+(①)

正解が正しい理由

演算子の優先順位は「×、÷」が「+」より高いので、a×b+c÷dは(a×b)+(c÷d)と解釈される。2分木は、根が「+」、左の子が「×」(葉a、b)、右の子が「÷」(葉c、d)となる。後置記法は、左部分木→右部分木→根の順に並べるので、左部分木はab×、右部分木はcd÷となり、全体はab×cd÷+となる。したがって①が正しい。

各選択肢について

• ① (a×b)+(c÷d)の後置記法ab×cd÷+と一致しており、これが正答。
• ② ab×c÷d+は、((a×b)×c)÷d+…のように、演算子の優先順位を誤って解釈した場合の並びであり、式の意味が異なる。
• ③ abc×÷d+は、a÷(b×c)などを表す並びで、元の式(a×b+c÷d)とは一致しない。
• ④ abc+d÷×は、a×((b+c)÷d)を表す並びで、元の式と一致しない。
• ⑤ abcd×÷+は、a+(b÷(c×d))を表す並びで、元の式と一致しない。

覚えるべきポイント

後置記法(逆ポーランド記法)は、演算子をオペランドの後ろに置く記法で、括弧が不要になる。中間記法から変換するときは、まず演算子の優先順位を考えて2分木を作り、左部分木→右部分木→根の順にたどる。