逆ポーランド記法の変換法

以前逆ポーランド記法の優先順位について質問したのですが、いまいち変換法が分かりません。
例１ A+B*(C+D)+E →ABCD+*+E+
ABとCDがなぜ一緒になるのか。
例２ (A+B)*(C-D)→AB+CD-*
なぜ例1のABとCDは、ABCDになって、こっちはAB+CDなのか。なぜ*が一番後ろなのか。参考書は2冊ありますが、見ても？です。手順を詳しく説明して頂ける方、よろしくお願いします。

No.5 ベストアンサー 回答者： ham_kamo 回答日時： 2006/12/06 12:26

No.3です。

私のやり方も実は左からやっているのと同じなのです。かっこの中を先に変換しているだけで、計算自体は左から行っています。

逆ポーランド記法は X op Y （opは算術記号）が XYop と変換される、というのが基本になります。XとYはそれぞれ式であっても同じです。元の式は３項以上あると、どこかで区切って２項演算にしてやる必要があります。左から、というのはそれを左から計算されるように処理する、という意味でしょう。

たとえばA+B+Cという式があったとします。式は左から処理するのでA+Bを先に処理します。それを明示的に書くと(A+B)+Cという書き方ができます。これを変換すると、A+BはAB+なので、
(A+B)+C→(AB+)+C→(AB+)(C)+→AB+C+
となります。

しかし、最初の式をA+(B+C)と区切ってしまうと、
A+(B+C)→A+(BC+)→(A)(BC+)+→ABC++
と違う結果になります。これは、A+(B+C)では「かっこの中を先に計算する」という計算規則からすると「右側を先に計算している」ということになり、計算としての結果は同じでも左から計算しているわけではなく、逆ポーランド記法の変換結果も異なってしまいます。

例１の場合を改めて参考書と同じ過程を通るようにして変換してみましょう。X+Y → XY+、X*Y → XY* となることを頭においておき、
A+B*(C+D)+E を、(A+B*(C+D)) + E　と解釈し、上の式のXに(A+B*(C+D))、YにEを当てはめたとすると、X+YはXY+ですから
X+Y → (A+B*(C+D)) + E → (A+B*(C+D))E+　…(1)
同じように処理していって、A+B*(C+D)の部分をX=A,Y=B*(C+D)とあてはめると、
X+Y　→　A + B*(C+D) → A(B*(C+D))+
となり、これを(1)の式に代入すると
(A(B*(C+D))+)E+ …(2)
さらにかっこの中を見ていくと、
B*(C+D) →　B(C+D)*と変換できるので、これを(2)にあてはめると、
(A(B(C+D)*)+)E+
となり、最後にC+DはCD+と置きかえられるので、
(A(B(CD+)*)+)E+ → ABCD+*+E+
となります。

実は私の変換方法も同じことをやっているのです。最後のC+D→CD+などを先に変換しておいただけで、中から計算しているように見えているだけです。

最初に A+B*(C+D)+E を A+(B*(C+D)+E)としてしまうと、最初の方でA+B+CをA+(B+C)とした場合と同じく、結果が異なってしまいます。

例２の場合も同じように、XとYに一度置きかえてみましょう。
X*YはXY*と変換されます。
Xを(A+B)、Yを(C-D)とすると、
X*Y → XY* は、
(A+B)*(C-D) → (A+B)(C-D)*
という意味になります。
そしてA+BはAB+、C-DはCD-になるので、上の式は
(A+B)(C-D)* → (AB+)(CD-)*　→ AB+CD-*
となります。

>私の頭の中は(A+B)*(C-D)→(AB+)*(CD-)？→AB+*CD-？→*だけ右に来て+がそのまま？
(AB+)*(CD-)がまだ変換に最中なのにかっこを消してしまっています。ここから、（AB+)(CD-)*とさらに変換して逆ポーランド記法への変換は完了します。

この回答への補足

度々本当にすみません。XYopが、XとYはそれぞれ式であっても同じということから、例2は分かりました。ありがとうございます。こんなに丁寧に説明して頂いてまた質問で申し訳ないのですが、例1は「元の式は３項以上あると、どこかで区切って２項演算にしてやる必要がある」ことから、
(1)A+B*(C+D)+Eを(A+B*(C+D)) + EでXに(A+B*(C+D))、YにEを当てはめて
(2)A+B*(C+D)の部分をX=A,Y=B*(C+D)とあてはめる
となっていますが、区切る場所はどうやって決めていくのですか。
どうして最初のA+B+Cは（A+B)+Cで左からなのに、例1だと区切る場所が変わるのでしょうか。
気が向いたらで構いません。よろしくお願いします。

補足日時：2006/12/06 13:53

No.7 回答者： kohji_5959 回答日時： 2006/12/08 09:19

もう少しやわらかく考えてみたらどうでしょう？

例1 A+B*(C+D)+E

これを実際に頭の中で計算するときを考えます

おそらく
CとDを足したもの(+)にBをかけて(*)それにAを足して(+)Eを足す(+)
のような感じになると思います

この出来上がった文字列を左から順番に記号に変換すると
A+B*(C+D)+E　→　CD+B*A+E+　となります

これが逆ポーランド記法の基本的な考え方です

しかし実際には
A、B、C…と順番にデータが処理されることが前提のため
Aから順番に表記したものが一般的？になっている

このためAから順番に表記する方法を考える必要がある
問題をわかりやすくするため
解答から元の数式を求める方法を考えてみる

基本は3点
　・左から順番
　・数値は2つ一組
　・計算は演算子

＜逆ポーランド記法　→　数式への変換＞
ABCD+*+E+

A
計算なし

AB
計算なし

ABC
計算なし

ABCD
計算なし

ABCD+
計算あり
対象は直前のCD　→　C+D

ABCD+*
計算あり
対象は直前のB　→　B*(C+D)

ABCD+*+
計算あり
対象は直前のA　→　A+B*(C+D)

ABCD+*+E
計算なし

ABCD+*+E+
計算あり
対象は直前のE　→　A+B*(C+D)+E

この逆を考えればよい

＜数式　→　逆ポーランド記法への変換＞
A+B*(C+D)+E

A
最初の数値

AB
次の数値　ここまでは必須

ABC
次の数値
AとBの演算はまだ行わないので演算子はなし

ABCD
次の数値
BとCの演算はまだ行わないので演算子はなし

ABCD+
演算子(+)　1番目の演算
C+Dの演算を行う

ABCD+*
演算子(*)　2番目の演算
B*(C+D)の演算を行う

ABCD+*+
演算子(+)　3番目の演算
A+B*(C+D)の演算を行う

ABCD+*+E
次の数値

ABCD+*+E+
演算子(+)　4番目の演算
A+B*(C+D)+Eの演算を行う

初めの内は
逆ポーランド記法 → 数式に変換するほうが理解しやすいと思います

情報処理試験対策だけを考えるのであれば
答え（4択）から数式を求めて解答を導く
というのもひとつの手ではあります

この回答へのお礼

何人もの方が丁寧に回答を下さって本当にありがたく思います。
やっぱり頭の中で数式を1回整理する必要ってあるんですね。他の人は必要ないのかもしれないけど。もっと事務的にこうなったらこうみたいにぽんぽんできるのかと思って。
ここに回答をもらってから、数式が短めの逆・・の問題なら正解できるようになりました。kohji_5959さんの逆・・⇒数式も理解できるので困ったとき用に覚えておこうと思います。ありがとうございます。

お礼日時：2006/12/08 10:54

No.6 回答者： asfd 回答日時： 2006/12/06 16:00

＃1です。

木が違います。正しくは以下のとおりです。
　　　　　＼
　　　　　　＋
　　　　　／　＼
　　　　＋　　　　E
　　　／＼
　　A　　　＊
　　　　　／＼
　　　　　B　＋
　　　　　　／＼
　　　　　　C　D

一番優先順位が低いものが順番に節になります。

　　　　　＼
　　　　　　＋
　　　　　／　＼
　　A+B*(C+D)　　E

この段階で次に節になるのはA+B*...の＋です。一番優先順位が低くて
一番最後に計算されます。で、以下のとおりになります。

　　　　　＼
　　　　　　＋
　　　　　／　＼
　　　　＋　　　E
　　　／　＼
　　　A　　B*(C+D)

次は*が節に、最後にC+Dの＋が節になり完成です。

この回答へのお礼

度々ありがとうございます。
やはり優先順位的なところが難しく感じます。きっと数学が苦手だったこともあるのだと思います。少し理解が深まりました。基本情報の問題を解くことだけを考えれば対応できそうです。ありがとうございました。

お礼日時：2006/12/08 10:46

No.4 回答者： asfd 回答日時： 2006/12/05 19:31

＃１です。

＞木構造を使う方法ですとABCD+*+E+はAB+CD+*E+になります。

これ大嘘でした。ごめんなさい。今やってみたら違ってました。
木構造を使ってもABCD+*+E+ですね。。。

混乱したらごめんなさいm(_ _)m

この回答へのお礼

素早い回答ありがとうございます。
スタックのURLは英語みたいでしたが、木のほうは参考にさせてもらいました。木を使って例2は解けるようになりました。これだけでも大変ありがちのですが、例1はasfdさんの最初の回答と同じAB+CD+*E+になります。
　　　　　＼
　　　　　　＋
　　　　　／　＼
　　　　*　　　　E
　　　／＼
　　+　　　+
　／＼　　／＼
A　　B　C　　D
の後順です。違いますか。時間がある時で構いませんので、例2がABCD+*+E+になる理由を教えていただけたらと思います。よろしくお願いします。　

お礼日時：2006/12/06 11:00

No.3 回答者： ham_kamo 回答日時： 2006/12/05 17:13

A+BがAB+、A*BはAB*となることはわかりますよね。

そうすると、順番に処理していけば、以下のようになります。
変換の過程を書いてみますが、途中で（）を挟むとわかりやすいです。

例１
C+D → CD+
B*(C+D) → B(CD+)* →　BCD+*
A+B*(C+D) → A(BCD+*)+　→　ABCD+*+
A+B*(C+D)+E → (ABCD+*+)E+ → ABCD+*+E+

例２
A+B → AB+
C-D → CD-
(A+B)*(C-D) → (AB+)(CD-)* → AB+CD-*

この回答への補足

素早い回答ありがとうございます。ごめんなさい。まだちょっとよく分からないのですが、
質問(1)最初に優先順位についてこちらで質問したときに、
左からと回答して頂いて、参考書も優先順位順に（）をつけるという事で(A+(B*(C+D)))E+→(A(B*(C+D))+E+→(A(B(C+D)*+)E+つづく
といった感じで左から行っているようですが、ham_kamoさんの回答を見た感じでは普通の数式のように（）が先で*が次でみたいに行っても構わないということですか。（ちなみに私はこの参考書の「優先順位順に（）をつける」の意味も分かりません。）
質問(2)(A+B)*(C-D) → (AB+)(CD-)* は、なんで*だけ後ろに来るんでしょうか。私の頭の中は(A+B)*(C-D)→(AB+)*(CD-)？→AB+*CD-？→*だけ右に来て+がそのまま？となります。度々すみません。お手すきのときで構いませんので、よろしくお願いします。

補足日時：2006/12/06 08:49

No.2 回答者： motochan7185 回答日時： 2006/12/05 17:12

左から見て行って、３つの並びが「数　数　演算子」の形になったら計算する、

というのを繰り返してみてください。
ABCD+*+E+
を左から見て、最初に「数　数　演算子」の形になるのは
CD+
なので、C+Dを計算。C+D=Fだとして話を続けると、
ABF*+E+
また左から見て、最初に「数　数　演算子」の形になるのは
BF*
なので、B*Fを計算。B*F=Gだとすると、
AG+E+
同様に、A+G=Hとすると、
HE+
最後にHとEを足して終了です。

なお、アルファベットの部分に実際に数字を入れる場合、
数字と数字を区切るための「デリミタ」が必要になります。

参考URL：http://ja.wikipedia.org/wiki/%E9%80%86%E3%83%9D% …

No.1 回答者： asfd 回答日時： 2006/12/05 16:53

段階を追って書こうと思ったんですが、途中まで書いたらすごく

長かったので辞めます。これは2種類のアルゴリズムがあります。
二分木を作る方法と、スタックを使う方法です。
スタックを使う方法だと、上記の回答になります、
木構造を使う方法ですとABCD+*+E+はAB+CD+*E+になります。
どちらも正解なので、あまり違いを気にする必要は無いと思います。

スタックを使う方法は
http://en.wikipedia.org/wiki/Shunting_yard_algor …
木構造を使う方法は
http://santamartadotnet.hp.infoseek.co.jp/docume …
です。

参考URL：http://en.wikipedia.org/wiki/Shunting_yard_algor …