解説

式： a op (b op c) op d の演算を考えると、まずbとcに対して演算opを施し、その結果とaに対して演算opを施し、さらにその結果とdに対して演算opを施すという順序になります。

各選択肢の2分木を例と同じ方法で探索し、式が正しく解釈される木構造がどれかを確認していくことで正解がどれかを突き止めます。

木構造のデータを読み出す方法には三種類ありますが、例と同じ帰りがけ順／後行順序訪問で探索していきます。

帰りがけ順の探索では、

1. ある節にたどり着いたら、その節の左の節のデータを読む。
   もし、その節が部分木を持つのであれば1.を繰り返す
2. その節の右の節のデータを読む。
   もし、その節が部分木を持つのであれば1を繰り返す
3. その節のデータを読む
4. 親の節へ戻る

というルールに従って探索を繰り返します。

各木構造を帰りがけ順で探索・解釈していくと以下のようになります。

• 
  cとdに演算opを施し、その結果とbに演算opを施す。さらにその結果とaに演算opを施すと解釈されます。
  式で表すと、a op { b op (c op d)}となるので誤りです。
• 
  aとbに演算opを施したものと、ｃとdに演算opを施したもの二つに対して演算opを施すと解釈されます。
  式で表すと、a op b op (c op d)となるので誤りです。
• 
  aとdに演算opを施したものと、bとcに演算opを施したもの二つに対して演算opを施すと解釈されます。
  式で表すと、a op d op (b op c)となるので誤りです。<
• 
  bとcに演算opを施し、その結果とdに演算opを施す。さらにその結果とaに演算opを施すと解釈されます。
  式で表すと、a op {(b op c) op d}となるので誤りです。
• 
  bとcに演算opを施し、その結果とaに演算opを施す。さらにその結果とdに演算opを施すと解釈されます。
  式で表すと、a op (b op c) op dとなるのでこれが正解となります。

解説

構文規則を規定する方法として疑似BNF記法が用いられており、この構文規則から正しい構文木が作成できるかが要点となります。

〔式の構文規則〕に従いすべての要素を"名前"と"演算子"に分解していきます。この構文規則から構築された構文木は以下のようになります。これを2分木で表現したものが「イ」の構文木です。

構文木作成のポイントは、b op2 c op2(d op1 e)の部分で、これを項を再帰的に解釈し(項 op2 因子) op2 因子と分解できるかどうかが、正しい2分木を描けるかの分かれ目になるのではないかと思います。

この木構造を見ると演算の優先度は、括弧つき"()"が最も高く、次いでop2、最後にop1が評価され最終的な式が構成されることがわかります。

解説

通常の式を後置表記法(＝逆ポーランド表記法)逆ポーランド表記法に直すだけの単純な問題です。

設問2にて演算の優先順位が把握できていれば、午前の小問を解いたことのある人ならいとも簡単に答えることができると思います。

演算の優先度は、括弧つき＞op2(×)＞op1(＋)です。これを頭に入れて a×b＋c×d＋e を逆ポーランド表記法に変換してみましょう。

通常の式を、逆ポーランド表記法で表現するための基本は、A＋BをAB＋で表すことです。これと一回使った演算子は2度使わないことに注意して、普通に計算式を解くのと同じ要領で行っていくことで逆ポーランド表記法の式になります。

a×b＋c×d＋eを、1つずつ変換していきます。

1. まず式の中で演算優先順位が高い a×b と c×d を変換します。a×bは"ab×"に、c×dは"cd×"になります。
   　a×b＋c×d＋e→ab×＋cd×＋e
2. 次にa×bの結果であるab×と、c×dの結果であるcd×を加算します。この時"ab×"や"cb×"を一つの項として考えると、現在どこを変換しているのかが理解しやすいかと思います。
   　ab×＋cd×＋e　→　ab×cd×＋＋e
3. 最後にこれまでの演算結果であるab×cd×＋に、eを加算します。
   　ab×cd×＋＋e　→　ab×cd×＋e＋　
   

ここまでですべての演算子についての演算を1回ずつ行ったので変換は終了します。

a×b＋c×d＋eを逆ポーランド表記法で表現すると、ab×cd×＋e＋となるため答えは「ウ」が適切です。

解説

まず式 a＋b＋c×d を後置表記法に変換します。

設問3と同様の手順で変換を施すと、

　a＋b＋c×d→a＋b＋cd×→ab＋＋cd× → ab＋cd×＋

となり、ab＋cd×＋として表記されます。

式a＋b＋c×dを言葉にすると「aとbを加算したものと、cとdを乗算したものを足し合わせる」というように解釈ができると思います。
選択肢の中でこれを満たす操作順序を考えると、

• 通常の式そのままをスタック命令にしただけの順序です。スタックに一つしかオペランドが入っていない状態でadd命令をしていることなど誤りだらけであることがわかります。
• この順序だとaとbを加算したものとcを乗算し、その結果にdを足し合わせることになるため誤りです。
  この順序が示す式は、(a＋b)×c＋dになります。
• 正しい。
• この順序だとbとcとdを加算した結果と、aを乗算することになるので誤りです。
  この順序が示す式は、a×(b＋c＋d)になります。

正解である「ウ」の順序をよく見てみると、後置表記法で表現したab＋cd×＋を先頭から評価した時と全く同じになっている事がわかります。