レコード・オブジェクト・クラス(2) 演習

式の木構造

式の木構造のスライドで使ったクラスExprの定義をまとめたものを以下に示す(expr.rb)．

class Expr
  def initialize(left, op, right)
    @left = left
    @op = op
    @right = right
  end
  def to_s
    s = "("
    s += @left.to_s
    s += @op
    s += @right.to_s
    s + ")"
  end
  def to_f
    left = @left.to_f
    right = @right.to_f
    if @op == "+" then
      left + right
    elsif @op == "-" then
      left - right
    elsif @op == "*" then
      left * right
    elsif @op == "/" then
      left / right
    else
      0
    end
  end
end

変数を含む式

上の定義を使って，x, y などの変数を含む式も

Expr.new("x","+",Expr.new("y","-",Expr.new("x","*",Expr.new("x","*","x"))))

のように表すことができる．これは，x+(y-x*x*x)という式を表している．変数に具体的な値を代入して値を計算するメソッドevaluateを定義してみることにする．このメソッドevaluate は式を表す引数 exp と，変数と具体的な値との対応を示す引数 env の二つを取るものとする．実行例は，以下のようになる．

>> e1=Expr.new("x","+",Expr.new("y","-",Expr.new("x","*",Expr.new("x","*","x"))))
=> #, @op="*", @left="x">, @op="-", @left="y">, @op="+", @left="x">
>> evaluate(e1,{"x"=>3,"y"=>4})
evaluate(e1,{"x"=>3,"y"=>4})
=> -20   ### 3+4-3*3*3
>> evaluate(e1,{"x"=>1,"y"=>10})
=> 10    ### 1+10-1*1*1
>> evaluate("x",{"x"=>3})
=> 3
>> evaluate(30,{"x"=>3})
=> 30

このメソッドの設計方針としては，数値(Numeric)と文字列(String)はメソッド内で処理して，式(Expr)の場合はExprクラスのインスタンスメソッドevalで扱うことにする． Exprクラスに定義するメソッドevalの穴を埋めてプログラム(expr1.rb)を完成させなさい．

# 式expを環境(変数をキーとしてその変数の値を得るハッシュ)envのもとで
# 評価した値を得る
def evaluate(exp,env)
# 数値の時は，値を浮動小数点数に変換する
  if exp.kind_of?(Numeric)
    exp.to_f
# 変数の時は，ハッシュenvの中から変数の値を得て浮動小数点数に変換する
  elsif exp.kind_of?(String)
    env[exp].to_f
# クラスExprのインスタンスの時は，クラスExprのインスタンスメソッド evalを呼ぶ
  elsif exp.kind_of?(Expr)
    exp.eval(env)
  end
end

class Expr
  def eval(env)
# 式 @left を環境 envの元で評価した値をローカル変数leftに代入する
    left = ### (1) ###
# 式 @right を環境 envの元で評価した値をローカル変数rightに代入する
    right = ### (2) ###
    if @op == "+" then
      left + right
    elsif @op == "-" then
      left - right
    elsif @op == "*" then
      left * right
    elsif @op == "/" then
      left / right
    else
      0
    end
  end
end

これが完成すれば，

>> load "./expr.rb"
=> true
>> load "./expr1.rb"
=> true
>> e1=Expr.new("x","+",Expr.new("y","-",Expr.new("x","*",Expr.new("x","*","x"))))
=> #, @op="*", @left="x">, @op="-", @left="y">, @op="+", @left="x">
>> evaluate(e1,{"x"=>3,"y"=>4})
evaluate(e1,{"x"=>3,"y"=>4})
=> -20
>> evaluate(e1,{"x"=>1,"y"=>10})
=> 10
>> evaluate("x",{"x"=>3})
=> 3
>> evaluate(30,{"x"=>3})
=> 30

のような実行例になるはずである．上のプログラムはエラー処理をきちんと行っていないので，すべての変数の値が定まっていない場合などは問題が出ることがある．

式の微分

式を変形させて別の式を作る上で木構造が役に立つということを確かめるために，式の微分を考えてみる．変数xだけを含む(四則演算だけからなる)式をxに関して微分した結果を得るには，微分の公式を組み合わせるだけで良い．

# 式exp を 変数varで微分した結果の式を返す
# 結果の式はどんなにひどい形でも構わない
def d(exp,var)
# dx/dxは1
  if exp == var
    1.0
# クラスExprのインスタンスの場合はインスタンスメソッドexp_dを呼ぶ
  elsif exp.kind_of?(Expr)
    exp.exp_d(var)
  else
# 定数を微分すると0.0, エラーになる場合も無視して0とする
    0.0
  end
end

class Expr
  def exp_d(var)
    ######
  end
end

上のプログラムの穴を埋めて，

evaluate(d(Expr.new("x","/",Expr.new("x","+",3.0)),"x"),{"x"=>3.0})
=> 0.0833333333333333 # d(x/(x+3))/dx= 3/(x+3)**2, 3/6**2
evaluate(d(Expr.new("x","/",Expr.new("x","+",3.0)),"x"),{"x"=>5.0})
=> 0.046875    ## 3/8**2
evaluate(d(Expr.new("x","-",Expr.new(Expr.new("x","*","x"),"*","x")),"x"),{"x"=>2.0})
=> -11.0       # d(x-x**3)/dx = 1-3*x**2, 1-3*2**2=-11
evaluate(d(Expr.new("x","-",Expr.new(Expr.new("x","*","x"),"*","x")),"x"),{"x"=>0.0})
=> 1.0         # 1-3*0**2=1

となるようにプログラムを完成させなさい．上のプログラムはエラー処理をきちんと行っていないので，すべての変数の値が定まっていない場合などは問題が出ることがある．

発展

時間の余った人は以下の課題のどれかを選んで取り組んでみると良いだろう(本物の数式処理プログラムであるMathematicaも使ってみると感じがつかめるかもしれない)．

演算子の拡張

"**", exp, log, sin, cos などの算術関数も扱えるように Exprクラスの定義を拡張する(exp, log, sin, cosなどの1引数関数は@leftにはnilを入れて@rightのみを使う)．

## 実行例
e1=Expr.new("x","+",Expr.new(nil,"log","x"))
=> #, @op="+", @left="x">
evaluate(e1,{"x"=>1})
=> 1.0

パーサー

文字列からクラスExprのオブジェクトに変換する

## 実行例
e1=parse("3*x+y-z")
=> #>>

simplifier

変数，演算子を含む式をなるべく簡潔な形に変換する．

## 実行例
simplify(parse("(1+(0-((1*(x*x))+(x*((1*x)+(x*1))))))"))
=> #, @op="+", @left=1>

式のクラス階層化

今のプログラムでは，演算子を増やすたびに，クラス Expr の関連するメソッドをすべて書き換える必要がある．これはオブジェクト指向としては美しくないので，以下のように演算子ごとのクラスにしてみるとすっきりするはずである．

class Expr  ----- class NumberExpr  # 数(整数，実数)
              |
              +-- class VarExpr     # 変数
              |
              +-- class AddExpr     # ??? + ???
              |
              +-- class SubExpr     # ??? - ???
              |
              +-- class MulExpr     # ??? * ???
              |
              +-- class DivExpr     # ??? / ???
              |
              +-- class LogExpr     # log(???)
              |
                .....

このようにクラス階層を変更するようにプログラムを書き換えて動くことを確かめなさい．

課題の提出方法

学生証番号，氏名，説明を含んだファイル(テキストファイルが望ましいが，図等を入れたい場合はPDFファイル，WORDファイル(教育用計算機システムのOfficeで読める)も可) を作成して，cfiveの課題提出機能の12月19日分を選択して提出すること．

講義の感想も100字以上1000字以下で加えること．

期限内なら何度でも再提出が可能である．1/9の夜23:55までに提出したものは8割以上を満点(8割以上は同じ)，それ以降講義期間内(試験前)に提出したものは，10割を満点として採点する．もっとも点数の高いものを評価に用いる．