dag(directed acyclic graph)であらわした算術式の計算

質問

以下の問題が解けません。

１．演算子として＋と＊をもつ算術式の木から、共通の部分式をまとめてdagに変えるアルゴリズムを作れ。（Cでプログラムを作れ）

２．dagで表した算術式の値を求めるアルゴリズムを作れ。（Cでプログラムを作れ）

です。
＜dagの説明は、閉路の無い有向グラフということと、共通の部分式をもつ算術式の文法的な構造を表すのに便利だという性質が書いてありました。＞

分からない点は、どうやって共通の部分式を認識するのか、またどういうデータ構造（リスト？配列？）で処理したらよいかです。
例：((a+b)*c+((a+b)+e)*((a+b)*c)で、a+bや(a+b)*cは共有されている部分式であり、これを表す頂点には入ってくる弧が２本以上ある。

アドバイスで構わないので、よろしくお願いします。

回答No.1

rinkun

データ構造は基本的に算術式の木と同じで良いでしょう。

１．
まず部分式に対して一致を判定する関数を作ります。
この関数は部分式について再帰的に判定を行うように作ると良いでしょう。
例えばX1＋Y1とX2＋Y2の比較ならば、((X1とX2が一致)かつ(Y1とY2が一致))あるいは((X1とY2が一致)かつ(Y1とX2が一致))で(X1＋Y1とX2＋Y2が一致)となるわけです。

あとは算術式の木の部分式について一致する場合にどちらか一方を残して他方を置き換え(要するに部分式XとYが一致するならYをXで置き換える)、これ以上の置き換えができなくなる(XとYが一致する場合はXとYは同じ(ポインタ値を持つ))まで繰り返します。

２．
計算式の木を辿って末端から順に計算します。
ただし部分式に計算値を保持する変数と計算済みを判定する変数を用意し、一度計算した値は再度計算しないようにします。