木構造の前置形と行きがけ順について

質問

はじめまして。今データ構造とアルゴリズムを勉強しているのですが、前置形でつまずいてしまいました。以下の問題を解くのですが、いまいち自分で出した答えに自身がないのです。
問題　式((a+b)+c*(d+e)+f)*(g+h)を前置形に変換せよ。
自分は、与えられた式を元に木を再現して、それから行きがけ順に並べたのですが。自信がないところは、ずばり、最初の項で和が３つあるところなんです。考え方の一つとして、枝分かれを３つという考え（すなわち、*++ab*c+def+gh）と、３つを一つの和ともう２つの和と分けて考える（すなわち*++ab+*c+def+gh）のと、どちらが正解なのでしょうか？といいますのも、defのところで、今度は逆に前置形からもとの式を作り直すときに違う式ができるのでは、と思うからです。

よろしくお願いします。

回答No.5

JaritenCat · ベストアンサー

2番の補足です。

　　　　　　　　　　＊
　　　　　　　　／　　　＼
　　　　　　　＋　　　　　＋
　　　　　　／　＼　　　／　＼
　　　　　＋　　　ｆ　　ｇ　　　　　ｈ
　　　／　　　＼
　　＋　　　　　＊
　／　＼　　　／　＼
ａ　　　　ｂ　ｃ　　　　　＋
　　　　　　　　　　　／　＼
　　　　　　　　　　ｄ　　　　ｅ

ですよね？

お礼

はいありがとうございます。図まで載せてもらいありがとうございます。感謝です☆

回答No.4

ymmasayan

式((a+b)+c*(d+e)+f)*(g+h)を前置形に変換せよ。
これを前置系に変換すると
*+++ab*c+def+gh
これを元に戻すと
((a+b)+c*(d+e)+f)*(g+h)
となってきちんと戻り何の問題もありません。

回答No.3

BLUEPIXY

＃１は、勘違いしていました
Ａ＋Ｂ＋Ｃを
＋ＡＢＣとするか
＋＋ＡＢＣまたは＋Ａ＋ＢＣとするかって話ですね。
（私は後者の話だと思っていました。）

＋は普通に考えたら２項演算子ですので、
＋ＡＢＣとは出来ません
＋（ＡＢＣ）と表記するとか拡張が必要だと思います。
でないと質問者も言っている通り元には戻りません。

回答No.2

JaritenCat

普通は２分木で考えるので　*++ab*c+def+gh　はありえないと思います。(+が１個少ないですよね？)

お礼

ありがとうございます。普通は２分木を考えるのですか？

回答No.1

BLUEPIXY

どっちでも数式としての評価は同じだと思いますが、
要は
A+B+C
を
(A+B)+Cとするか
A+(B+C)とするか
って意味の様に思えます。
数学的には、
(A+B)+C=A+(B+C)だと思いますので、どちらでもいいのでしょうが
プログラム的には
＋の優先順位は同等なのでどちらでもいいですけど
基本的には、左から評価するという規則が使われることが多いと思います。
その場合は、
(A+B)+C
ってことになりますね。
元の式が作り出せるかどうかというのは、
要は（）のくくりが戻せるかということでもあると思いますが
（Ａ＋Ｂ＋Ｃ）の部分は、（）が使われていないので、厳密には同じ式に戻らない（どこに（）が使われてあるいは使われていないかという情報が失われている）と思います。
いずれにしても、式全体としては、正しいものに戻せるとは思いますが。