数式をa+bのように，オペランド（演算の対象となるもの，ここでは1文字のアルファベットで表される文字のみを考える。）の間に演算子（ここでは+，-，×，÷の4つの2項演算子のみを考える。）を書く書き方を中間記法と呼ぶ。これをab+のように，オペランドの後に演算子を置く書き方を後置記法若しくは逆ポーランド記法と呼ぶ。中間記法で，( a + b ) × ( c + d ) と書かれる式を下記の図のように数式を表す2分木で表現し，木の根（root）からその周囲を反時計回りに回る順路（下図では▲の方向）を考え，順路が節点の右側を上昇（下図では↑で表現）して通過するときの節点の並び ab + cd + ×はこの式の後置記法となっている。後置記法で書かれた式は，先の式のように「aとbを足し，cとdを足し，それらを掛ける」というように式の先頭から読むことによって意味が通じることが多いことや、かっこが不要なため，コンピュータの世界ではよく使われる。中間記法で a × b + c ÷ d と書かれた式を後置記法に変換したとき，最も適切なものはどれか。
図 式 ( a + b ) × ( c + d ) の2分木と後置記法への変換
① ab × cd ÷ +
② ab × c ÷ d +
③ abc × ÷ d +
④ abc + d ÷ ×
⑤ abcd × ÷ +
解答
①
解説
a × b + c ÷ d について，図のに当てはめると，左側の+を×に，右側の+を÷に，上部の×を+に置き換えた構成になります。
したがって，後置記法で表記すると，
ab × cd ÷ +
となります。
参考情報
過去の出題
なし
