表達(dá)式計(jì)算(三)

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

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

結(jié)果為 25，我們知道這個(gè)結(jié)果應(yīng)該是 24，這是因?yàn)榍懊嫖覀兊乃惴ǘ际轻槍?duì)整數(shù)的, 1/5 =0 ，當(dāng)然我們可以把整數(shù)改成浮點(diǎn)數(shù)，比如，修改 eval 如下：

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

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

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)”)的計(jì)算結(jié)果：

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

我們得出來表達(dá)式的精確結(jié)果，為分?jǐn)?shù)表示，比如：

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

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

到目前為止我們有了計(jì)算四則運(yùn)算的算法，下面24的算法就比較簡(jiǎn)單了，窮舉法。

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

上一篇：算法之一下一篇：表達(dá)式計(jì)算(一)