ｃ言語での分配法則のプログラム

Question

前提・実現したいこと

入力された算術式を二分木と捉えて、右回転・左回転を使って分配法則を行って展開する関数を作成しています。((x+9)(y+8))であれば((((xy)+(9y))+(x8))+(98))に、(7((p+(q+r))(x+y)))は(((((((7p)x)+((7q)x))+((7r)x))+((7p)y))+((7q)y))+((7r)y))という形になればいいです。
((x+9)(y+8))は正しく表示されるのですが、(7*((p+(q+r))(x+y)))は正しく表示されず、計算結果も(((((((((77)*p)*x)y)+((((77)*q)*x)y))+((((77)*r)*x)y))+((((77)*p)*x)y))+((((77)*q)*x)y))+((((77)*r)*x)*y))となり、計算結果も294と正解の42と全く違う値になってしまいます。

発生している問題・エラーメッセージ

(7*((p+(q+r))*(x+y)))
show:  (7*((p+(q+r))*(x+y)))
eval:  42
dist:  (((7*(7*((p*x)*y)))+((7*(7*((q*x)*y)))+(7*(7*((r*x)*y)))))+((7*(7*((p*x)*y)))+((7*(7*((q*x)*y)))+(7*(7*((r*x)*y))))))
assoc: (((((((((7*7)*p)*x)*y)+((((7*7)*q)*x)*y))+((((7*7)*r)*x)*y))+((((7*7)*p)*x)*y))+((((7*7)*q)*x)*y))+((((7*7)*r)*x)*y))
eval:  294

*** Error in `./ex3': double free or corruption (fasttop): 0x0000000001c31290 ***
======= Backtrace: =========
/lib64/libc.so.6(+0x7c619)[0x7f9273d1f619]
./ex3[0x400a84]
./ex3[0x400a68]
./ex3[0x400a78]
./ex3[0x400a68]
./ex3[0x400a68]
./ex3[0x400b74]
./ex3[0x4012c8]
/lib64/libc.so.6(__libc_start_main+0xf5)[0x7f9273cc4c05]
./ex3[0x4006c9]
======= Memory map: ========
00400000-00402000 r-xp 00000000 00:28 9045122                            /exports/home/j418828/centos7/AdvProg/T6/week02/ex3
00601000-00602000 r--p 00001000 00:28 9045122                            /exports/home/j418828/centos7/AdvProg/T6/week02/ex3
00602000-00603000 rw-p 00002000 00:28 9045122                            /exports/home/j418828/centos7/AdvProg/T6/week02/ex3
01c31000-01c52000 rw-p 00000000 00:00 0                                  [heap]
7f926c000000-7f926c021000 rw-p 00000000 00:00 0
7f926c021000-7f9270000000 ---p 00000000 00:00 0
7f9273a8d000-7f9273aa2000 r-xp 00000000 08:01 2365672                    /usr/lib64/libgcc_s-4.8.5-20150702.so.1
7f9273aa2000-7f9273ca1000 ---p 00015000 08:01 2365672                    /usr/lib64/libgcc_s-4.8.5-20150702.so.1
7f9273ca1000-7f9273ca2000 r--p 00014000 08:01 2365672                    /usr/lib64/libgcc_s-4.8.5-20150702.so.1
7f9273ca2000-7f9273ca3000 rw-p 00015000 08:01 2365672                    /usr/lib64/libgcc_s-4.8.5-20150702.so.1
7f9273ca3000-7f9273e5b000 r-xp 00000000 08:01 2361504                    /usr/lib64/libc-2.17.so
7f9273e5b000-7f927405b000 ---p 001b8000 08:01 2361504                    /usr/lib64/libc-2.17.so
7f927405b000-7f927405f000 r--p 001b8000 08:01 2361504                    /usr/lib64/libc-2.17.so
7f927405f000-7f9274061000 rw-p 001bc000 08:01 2361504                    /usr/lib64/libc-2.17.so
7f9274061000-7f9274066000 rw-p 00000000 00:00 0
7f9274066000-7f9274087000 r-xp 00000000 08:01 2361497                    /usr/lib64/ld-2.17.so
7f9274269000-7f927426c000 rw-p 00000000 00:00 0
7f9274283000-7f9274287000 rw-p 00000000 00:00 0
7f9274287000-7f9274288000 r--p 00021000 08:01 2361497                    /usr/lib64/ld-2.17.so
7f9274288000-7f9274289000 rw-p 00022000 08:01 2361497                    /usr/lib64/ld-2.17.so
7f9274289000-7f927428a000 rw-p 00000000 00:00 0
7ffdda0c5000-7ffdda0e6000 rw-p 00000000 00:00 0                          [stack]
7ffdda11b000-7ffdda11d000 r-xp 00000000 00:00 0                          [vdso]
ffffffffff600000-ffffffffff601000 r-xp 00000000 00:00 0                  [vsyscall]
Abort (core dumped)

該当のソースコード

void dist_prod_exp_sub(Exp *ep) {
  if((*ep)->node == '*' && (*ep)->left->node != '+' && (*ep)->right->node == '+'){
	rotate_left_exp(ep);
	(*ep)->right = make2_exp('*', ((*ep)->left)->left, (*ep)->right);
	dist_prod_exp(&(*ep));
  }
  else if((*ep)->node == '*' && (*ep)->left->node == '+' && (*ep)->right->node != '+') {
	rotate_right_exp(ep);
	(*ep)->left = make2_exp('*', (*ep)->left, ((*ep)->right)->right);
	dist_prod_exp(&(*ep));
  }
  else if((*ep)->node == '*' && (*ep)->left->node == '+' && (*ep)->right->node == '+') {
	rotate_left_exp(ep);
	(*ep)->right = make2_exp('*',((*ep)->left)->left, (*ep)->right);
	rotate_right_exp(&((*ep)->left));
	((*ep)->left)->left = make2_exp('*', ((*ep)->left)->left, (((*ep)->left)->right)->right);
	rotate_right_exp(&((*ep)->right));
	((*ep)->right)->left = make2_exp('*', ((*ep)->right)->left, ((*ep)->right)->right->right);
	dist_prod_exp(&(*ep));
  }
  if((*ep)->left != NULL)
	dist_prod_exp(&((*ep)->left));
  if((*ep)->right != NULL)
	dist_prod_exp(&((*ep)->right));
}

void dist_prod_exp(Exp *ep) {
  dist_prod_exp_sub(ep);
  dist_prod_exp_sub(ep);
}

試したこと

((x+9)*(y+8))などを入力すると、正しく展開はされていますが、二回目を入力すると上と同じようなエラー文が表示されます。

補足情報

このプログラムの演算子は、和と積のみです。

出力には、showは入力された算術式をそのまま表示、evalは計算結果を表示（アルファベットは１として計算）、distは分配法則を使って展開した式を表示、assocはdistで表示された式の括弧をすべて左にくくりなした式を表示しています。
Exp型は、２分木の節を格納するためのデータ構造で、下の構造体と同じ形です。

typedef struct _tree {
　char  node;		/* 節のデータ (1文字) */
  struct _tree  *left;		/* 左の子へのポインタ */
  struct _tree  *right;		/* 右の子へのポインタ */
} Tree;

rotate_left_exp、rotate_right_expはそれぞれ二分木を左回転・右回転する関数です。
make2_expは、括弧の中の引数で二分木を生成する関数で、左から根となる演算子、左の子の値、右の子の値です。

周りの人に聞いてもあまり分かってないため、ここで初めて質問させていただきます。長々とすみません、よろしくお願いします。

Comments

[y_waiwai]

違う、というのはなにがどういうふうに違うんでしょうか。
実際の計算結果と、こうなるはず、の値を提示しましょう

[退会済みユーザー]

すみません、説明不足でした。内容を付け加えさせていただきました。ありがとうございます。

Answer 1

Expや記載されていない各種関数が正しく、初期の木が正常である前提ですが、回転と木の生成までは正常であるように思いました。
（回りくどいこと再帰呼び出しになっており複雑なので自信はあまりありませんが）

気になったのはdist_prod_exp(Exp *ep)の方で、subを2回呼んでいる理由です。
これがちょっとよく分かりません。

あと最初のif～elseとその後のifでepが変わっているのと最初のif～elseで再帰呼び出しが行われた後のその後のifでまた再帰呼び出ししているののコンボで処理の流れが無駄に難解になってしまっています。

条件を整理してみましょう。

Comments

[退会済みユーザー]

回答の方ありがとうございます。すこし整理してまたやってみます。ありがとうございました。

[退会済みユーザー]

とりあえず回転＆make処理をした後の部分木のrootは必ず+になっているので、rootはもう触れる必要が無く左右のnodeについてのみ再帰呼び出しするように設計すると良いと思います。
左右両方+の場合も実は片側だけ処理して、左右のNodeについて再帰呼び出しすれば場合分けが減るはずです。

後は木を式として出力する関数があるなら呼び出しごとにどういう木になっているか出力してみればバグの原因が追求しやすいと思います。

再帰のコツは相似な構造を見つけることです。
明確な答えになってなくてすいませんが、是非頑張って下さい。

Answer 2

以下3点になんとなく違和感を感じます。

(*ep)->node

引数epはダブルポインタでないのにこの書き方は正しいですか？
ep->nodeでいいような気がします。

rotate_right_exp(&((*ep)->left));

leftにはアドレスが入っているのだから、rotate_right_exp(ep->left)でいいような気がします。
rightも同様です。
もっともrotate_right_expの引数の型がダブルポインタなら問題ありません。

dist_prod_exp(&(*ep));

引数epはアドレスなのだからdist_prod_exp(ep)でいいような気がします。
ただし結果は変わらないかもしれません。

なんとなく違和感を感じただけで正解かわかりませんので参考程度にお願いします。

Comments

[退会済みユーザー]

ご回答ありがとうございます。一度それで書いてます、ありがとうございました。

[退会済みユーザー]

dist_prod_exp(ep)はエラーにならなかったのですが、それ以外の二つは訂正したところエラーになってしまいました。私の説明不足でした、答えていただいたのにすみません。少し自分でも考えてみます。

[ttyp03]

いえ、的外れな回答失礼しました。
また何か気づいたらコメントします。

[退会済みユーザー]

ありがとうございます、本当にすみません。

[ttyp03]

2関数の引数はダブルポインタじゃないですかね？
そうするとしっくりくるんですが。
void dist_prod_exp_sub(Exp **ep)
void dist_prod_exp(Exp **ep)

そもそも今のコードってコンパイルエラー出ません？

[退会済みユーザー]

コンパイル時点でエラーは出てないです。ダブルポインタの方で一度やってみます。何度もありがとうございます。