表達式計算(三)

在上篇中我們實現(xiàn)了整數(shù)的四則運算的算法，這里我們回到之前提到的 5 5 5 1 的例子，我們看看 eval ( ” 5 * ( 5 – 1/5) ” )的結果是多少？

scala> eval ("5*(5-1/5)")
res15: Int = 25

結果為 25，我們知道這個結果應該是 24，這是因為前面我們的算法都是針對整數(shù)的, 1/5 =0 ，當然我們可以把整數(shù)改成浮點數(shù)，比如，修改 eval 如下：

def eval(str:String):Double = str match {
    ...
    case _ => str toDouble
}

重新計算 eval (“5*(5-1/5)”) 結果為 24.0， 但是浮點數(shù)帶來了誤差，不是特別理想，我們前面在介紹類和對象時，使用的 Rational 例子，任何有理數(shù)都可以表示成分數(shù)，因此可以利用這個 Rational 來得到表達式計算的精確結果。

class Rational (n:Int, d:Int) {
  require(d!=0)
  private val g =gcd (n.abs,d.abs)
  val numer =n/g
  val denom =d/g
  override def toString = numer + "/" +denom
  def +(that:Rational)  =
    new Rational(
      numer * that.denom + that.numer* denom,
      denom * that.denom
    )

  def -(that:Rational)  =
    new Rational(
      numer * that.denom - that.numer* denom,
      denom * that.denom
    )

  def * (that:Rational) =
    new Rational( numer * that.numer, denom * that.denom)

  def / (that:Rational) =
    new Rational( numer * that.denom, denom * that.numer)

  def this(n:Int) = this(n,1)
  private def gcd(a:Int,b:Int):Int =
    if(b==0) a else gcd(b, a % b)
}

利用 Rational 類，我們修改 eval 定義如下：

def eval(str:String):Rational = str match {
    case Bracket(part1,expr,part2) => eval(part1 +  eval(expr) + part2)
    case Add(expr1,expr2) => eval(expr1)  +  eval(expr2)
    case Subtract(expr1,expr2) => eval(expr1)  -  eval(expr2)
    case Multiply(expr1,expr2) => eval(expr1)  * eval(expr2)
    case Divide(expr1,expr2) => eval(expr1)  /  eval(expr2)
    case _ => new Rational (str.trim toInt,1)

  }

再看看 eval (“5*(5-1/5)”)的計算結果：

scala> eval ("5*(5-1/5)")
res16: Rational = 24/1

我們得出來表達式的精確結果，為分數(shù)表示，比如：

scala> eval ("4*6")
res17: Rational = 24/1

scala> eval ("4*6+3*3+5/7")
res18: Rational = 236/7

到目前為止我們有了計算四則運算的算法，下面24的算法就比較簡單了，窮舉法。

注：Scala 中表達式計算的算法還有不少其它方法，比如對表達式的分析可以利用 scala.util.parsing.combinator 提供的 API。