━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
課題2 (数式データの操作)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

●準備

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

        exp.h
                        算術式の処理のためのヘッダ
        exp.c
                        算術式の操作
        ex2.c
                        課題２の動作確認用
        Makefile
                        自動コンパイル用

これらを課題１のファイル (tree.h, tree.c) と併用し，Makefile は上書きする．

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

文字の種類による判定に，isalnum() などの ctype.h で宣言された標準ライブラリの
関数群を使うので，あらかじめ使いこなせるようにしておく．

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

●課題一覧

基本課題
        2a      数式の読み込みと表示
        2b      数式の値の計算
        2c      数式データの基本操作

発展課題
        2d      進んだ数式操作
        2e      値の割り当ての変更

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

●基本課題 2a (数式の読み込みと表示)

課題 2a と 2b では，算術式を読み，表示し，値を求めるプログラムを作る．

限られた時間内で数式処理の本質部分を効率よく学ぶために，
入力できる算術式の構文を，次の BNF で定めるものに限る．

        定数   ::= 0 | 1 | … | 9
        変数   ::= a | b | … | z | A | B | … | Z
        算術式 ::= 定数
                 | 変数
                 | (算術式+算術式)
                 | (算術式*算術式)

つまり，1桁の定数や1文字の変数の和や積からなる式が入力である．

入力された算術式を読み込み，2分木データとして格納し，そのデータをもとに
入力と同じ算術式を表示する，という処理 (下図) を繰り返すプログラムを作れ．

        (a+1)　→　　→　(a+1)
        
次の要求を満たすものを作り，仕様の不明確な部分は各自で詳細化すること．

・算術式は標準入力から読む
・二つの算術式の区切りは一つの空白 (間隔文字や改行文字など) とする
・結果は標準出力に書く
・構文に合わない算術式を読んだらプログラムを終了する
・入力の終わりに達したらプログラムを終了する

算術式操作用のプログラムファイル exp.c の次の二つの関数を完成させること．

・算術式を読み込んで2分木に変換する関数 read_exp()
・算術式の2分木の表示関数 show_exp()

補足

●基本課題 2b (数式の値の計算)

課題 2a のプログラムに，算術式の値を計算して表示する機能を追加せよ．
ただし，変数の値は全て1であるとして，式の値を求めること．

例えば，入力が (2*3) と (x+(y+z)) の場合，次のような出力をすればよい．
show: に続いて入力された算術式を，eval: に続いて算術式の値を表示している．

        (2*3)                   ←入力
        show:  (2*3)
        eval:  6

        (x+(y+z))               ←入力
        show:  (x+(y+z))
        eval:  3

まず，算術式の値を求める関数 eval_exp() (exp.c にある) を完成させる．
十分な数の検査データを使って動作の正しさを確かめよ．

補足

●基本課題 2c (数式データの基本操作)

算術式の値を変えずに括弧をくくり直す簡単な式変形を考える．例えば，式

        (1+(2+3))
        (a*(b*c))
        ((i*x)+((j*y)+(k*z)))

の括弧を (結合法則を使って) 左にくくり直すと，それぞれ，次の式になる．

        ((1+2)+3)
        ((a*b)*c)
        (((i*x)+(j*y))+(k*z))

括弧を左にくくり直せる (Ａ+(Ｂ+Ｃ)) や (Ａ*(Ｂ*Ｃ)) の形の算術式を
((Ａ+Ｂ)+Ｃ) や ((Ａ*Ｂ)*Ｃ) の形にする式変形は，式に対応する木を
「左に回転」する変形と捉えられる (下図)．

        　→　
        
この操作を実行する関数 rotate_left_exp() (exp.c にある) を完成させよ．
この関数を使い，可能な場合にだけ算術式の括弧を左にくくり直す関数
assoc_left() を ex2.c に作って動作確認せよ．

補足

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

●発展課題 2d (進んだ数式操作)

入力の算術式に単項演算の - を使えるようにし，これまでに実現した
式変形に加えて，最外の - を消したり内側に移動したりする式変形を実現せよ．
関数 push_neg() を ex2.c に作ること．

例えば，式 --(a*-b) の - を消して (a*-b) にしたり，
-((2*i)+(2*j)) の - を内側に分配して (-(2*i)+-(2*j)) にしたり，
-((w+x)*(y+z)) の - を内側に移動して (-(w+x)*(y+z)) にする．
課題 2c と同様，外側に - があるときに1回だけ変形できればよい．

補足

●発展課題 2e (値の割り当ての変更)

プログラム実行開始時の各変数の値を1とし，
(x=0) や (x=(x+(i*y))) といった式を入力することで
変数の値の割り当てが変えられるようにせよ．

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

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