基本情報技術者　逆ポーランド記法について

お世話になります。
基本情報技術者の学習をしています。

基本情報技術者の過去問

において、

Y＝AB＋CDE÷－×

がこのように変更されます。

YAB＋CDE÷－×＝

この部分がいまいち理解できないのですが、どのように考ええるべきなのでしょうか？

よろしくお願いいたします。

行動規範の内容に同意します

回答2件

過去問の問題Y＝(A＋B)×(C－(D÷E))をもう少し丁寧に書いてみましょう。
((Y) = (((A) + (B)) × ((C) - ((D) ÷ (E)))))
これを外側のカッコに対応する演算子から順にツリー状にしていくと

1
1      =
2(Y)     (((A) + (B)) × ((C) - ((D) ÷ (E))))

2
1      =
2(Y)         × 
3((A) + (B))   ((C) - ((D) ÷ (E))))

3
1      =
2(Y)         × 
3      +          - 
4  (A) (B)    (C)   ((D) ÷ (E))

4
1      =
2(Y)         × 
3      +          - 
4  (A) (B)    (C)       ÷
5                   (D)   (E)

と、最終的に4のような形になります
この木を後置記法(後順走査)で走査していきます。
後置記法は

1.もし左部分木があれば後順走査する
2.もし右部分木があれば後順走査する
3.根ノードを調査する

という再帰的な処理のことです。
調査するタイミングで、その値を取り出す(逆ポーランド記法の解となる文字列に追加していく)と考えると

1. = には左部分木(Y)があるのでそちらを後順走査
2. (Y)には左部分木が無い。その次に右部分木も無い。よって現時点でルートである(Y)を調査
3. = からみて左部分木を走査し終えた。右部分木があるのでそちらを後順走査
4. × には左部分木があるのでそちらを後順走査
5. + には左部分木(A)があるのでそちらを後順走査
6. (A)には左部分木が無い。その次に右部分木も無い。よって現時点でルートである(A)を調査
7. + からみて左部分木を走査し終えた。右部分木(B)があるのでそちらを後順走査
8. (B)には左部分木が無い。その次に右部分木も無い。よって現時点でルートである(B)を調査
9. + からみて右部分木を走査し終えた。よって現時点でルートである(+)を調査

この時点の結果YAB+となっています。そのまま続けていくと

10. × からみて左部分木を走査し終えた。右部分木があるのでそちらを後順走査
11. - には左部分木(C)があるのでそちらを後順走査
12. (C)には左部分木が無い。その次に右部分木も無い。よって現時点でルートである(C)を調査
13. - からみて左部分木を走査し終えた。右部分木があるのでそちらを後順走査
14. ÷ には左部分木(D)があるのでそちらを後順走査
15. (D)には左部分木が無い。その次に右部分木も無い。よって現時点でルートである(D)を調査
16. ÷ からみて左部分木を走査し終えた。右部分木(E)があるのでそちらを後順走査
17. (E)には左部分木が無い。その次に右部分木も無い。よって現時点でルートである(E)を調査
18. ÷ からみて右部分木を走査し終えた。よって現時点でルートである(÷)を調査
19. - からみて右部分木を走査し終えた。よって現時点でルートである(-)を調査
20. × からみて右部分木を走査し終えた。よって現時点でルートである(×)を調査
21. = からみて右部分木を走査し終えた。よって現時点でルートである(=)を調査

そうすると逆ポーランド記法はYAB+CDE÷-×=になります

ちなみにY＝AB＋CDE÷－×からYAB＋CDE÷－×＝になるのは、上記20番目の走査を終えた直後から21番目の走査をすると変換されます。
上記サイト解説の言葉を借りて説明すると、

次に右辺でまだ演算をしていない、"×"の左側と右側で演算します。先程と同様に「AB＋」×「CDE÷－」⇒AB＋CDE÷－×と考えます。
　{{Y} ＝ {AB＋CDE÷－×}}
最後に 左辺と右辺を"＝"で演算して逆ポーランド表記法への変換が完了します。
　{YAB＋CDE÷－×＝}

となります。説明と違う点は、{ }で括られた所は一つの文字に置き換えてみるとわかりやすいでしょう。{ }を一つの文字に置き換えて、最初から説明すると

{Y}＝({A}＋{B})×({C}－({D}÷{E}))を、一つずつ順番に逆ポーランド表記法に変換していきましょう。
まず括弧内のA＋B と D÷Eを変換します。 
　{Y}＝{AB＋}×({C}－{DE÷})
次にもう一つの括弧内の(C－DE÷)を変換します。
　{Y}＝{AB＋}×{CDE÷－}
この時「DE÷」を一つの項として考えると、「C」－「DE÷」⇒CDE÷－となることを理解しやすいかと思います。
次に右辺でまだ演算をしていない、"×"の左側と右側で演算します。先程と同様に「AB＋」×「CDE÷－」⇒AB＋CDE÷－×と考えます。
　{Y}＝{AB＋CDE÷－×}
最後に 左辺と右辺を"＝"で演算して逆ポーランド表記法への変換が完了します。
　{YAB＋CDE÷－×＝}

になります。以上で説明を終わります。

投稿2018/12/16 07:44