四則演算 解説byWさん
四則演算の式の書き方には，演算子をオペランドの前に書く方法（前置記法），オペランドの間に書く方法（中置記法），オペランドの後に書く方法（後置記法）の３通りがある。図は，２分木で表現された式のたどり方と，各記法によって表される式を例示したものである。
各記法で式を書く手順の説明として，適切なものはどれか。 [平成18年 秋期 基本情報技術者]
ア 前置記法：節から上に戻るときにそこの記号を書く。
イ 中置記法：節に下りたときにそこの記号を書く。
ウ 後置記法：節から上に戻るときにそこの記号を書く。
エ 後置記法：葉ならばそこの記号を書いて戻る。演算子ならば下りるときに左括弧を書き，左の枝から右の枝に移るときに記号を書き，上に戻るときに右括弧を書く。
まず、図の矢印の向きが着目する節の順番になります。
つまり
- a + * - b - c - * d +
という順番で着目していきます。
これを踏まえて選択肢について考えます。
【ア】「節から上に戻るときにそこの記号を書く」
上に戻る、とはつまり a→+ や b→- のように上の節に移動するということです。
上の節に移動するときに記号を書いていくと、
a b c - d * +
となり、これは前置記法ではないので ×
【イ】「節に下りたときにそこの記号を書く」
節に降りる、とはアとは逆で +→a や +→* のように下の節に移動するということです。
下の説に移動したときにそこの記号を書いていくと
- a * - b c d
となり、これは中置記法ではないので ×
【ウ】これは記号の記述はアと同様
a b c - d * +
となり、これは後置記号と一致するので ○
【エ】「葉ならばそこの記号を書いて戻る」
末端の節に到達すれば無条件に記述するということです。
「演算子ならば下りるときに左括弧を書き，左の枝から右の枝に移るときに記号を書き，上に戻るときに右括弧を書く」
例えば - b - c - と着目する部分を見てみると、
下りるとき、とは -→b との部分。このとき"("を記述。
上に戻るとき、とは c→- の部分。このとき")"を記述。
左の枝から右の枝に移るとき、とは b→-→cの部分。このとき"-"を記述。
よって、この部分の記述は
( b - c )
となります。
この手順で全体の記号を書いていくと
( a + ( ( b - c ) * d )
となり、これは後置記号ではないので ×
以上です。
