━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
課題3 (数式の変形)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

●準備

次のファイルを，ディレクトリ ~/AdvProg/T6/ に保存しておく．

        ex3.c
                        課題3の動作確認用
        Makefile
                        自動コンパイル用

これらを課題1や課題2のファイルと併用し，Makefile は上書きする．

予習時に上記のソースファイルと以下の課題を熟読し，疑問点を明らかにしておく．

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

●課題一覧

基本課題
        3a      数式変形の理解
        3b      数式変形の実現

発展課題
        3c      進んだ数式変形
        3d      記憶領域の管理
        3e      構文の制限の緩和

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

●基本課題 3a (数式変形の理解)

規則に従って数式を変形するプログラムを作る．

算術式の括弧を全て左にくくり直す式変形を考える．例えば，算術式

        (i+(j+(k+l)))
        ((2*(a*b))+((3*(b*c))+(4*(c*a))))

の演算子 + や * を左結合にすると，それぞれ，次の式になる．

        (((i+j)+k)+l)
        ((((2*a)*b)+((3*b)*c))+((4*c)*a))

これを実現するには，前回作った関数 rotate_left_exp() による回転を繰り返す．
式全体にわたり，変形できる部分式がなくなるまで，再帰的に回転すればよい (下図)．

        　→　
        
次のプログラムをよく読み，ファイル exp.c の適切な位置に転記せよ．

        assocleft.c     + と * を左結合にする関数 assoc_left_exp()

式変形のアルゴリズムや実行時の動作を理解し，式変形の過程と再帰関数の呼び出し
との関係を，例を使ってわかりやすく説明せよ．

補足

●基本課題 3b (数式変形の実現)

括弧をすべて左にくくり直す式変形に加えて，分配法則を使って + を * の
外側へとくくり出す式変形をするプログラムを作れ．

ファイル exp.c に，+ を * の外側にくくり出す式変形をする
関数 dist_prod_exp() を作ること．

例えば，算術式 ((x+1)*(y+a)) の＋を外にくくり出し，括弧を左にくくり直すことで，
次の式が順に得られればよい．

        ((x+1)*(y+a))
        (((x*y)+(1*y))+((x*a)+(1*a)))
        ((((x*y)+(1*y))+(x*a))+(1*a))
        　→　　→　

分配法則を使う順序によっては，結果の式の形が変わる．((Ａ+Ｂ)*(Ｃ+Ｄ))
の形の式は，* の左の式 (Ａ+Ｂ) を先に分配すると (((Ａ+Ｂ)*Ｃ)+((Ａ+Ｂ)*Ｄ))
になり，右の式 (Ｃ+Ｄ) を先に分配すると ((Ａ*(Ｃ+Ｄ))+(Ｂ*(Ｃ+Ｄ))) になる．
同じ位置で２通りに分配できる場合，この課題では，左の式の分配を優先する．

補足

──────────────────────────────────────

●発展課題 3c (進んだ数式変形)

これまでに実現した式変形に加えて，単項演算の - を最内に移動する
式変形ができるようにせよ．

例えば -(-a+(b*-(c+d))) を ((a+(-b*-c))+(-b*-d)) と変形できればよい．

負号を移動する関数 push_neg_exp() を，ファイル exp.c に作ること．

補足

●発展課題 3d (記憶領域の管理)

プログラム実行中に動的に確保された記憶領域が，プログラム終了直前に
全て解放されることを，malloc() と free() の回数を調べる機能を追加して確かめよ．

●発展課題 3e (構文の制限の緩和)

より自然な表記の数式を受け付けるように，入力の構文の制限を緩めよ．

例えば，years * 365 + days や sqrt( (square - sum*mean) / (n - 1) )
といった式を書けるようにするとよい．

補足

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
演習のホームページ

山田 俊行
https://www.cs.info.mie-u.ac.jp/~toshi/