Scala二十四点游戏(3):表达式计算(三)

在上篇中我们实现了整数的四则运算的算法，这里我们回到之前提到的 5 5 5 1 的例子，我们看看eval ( ? 5 * ( 5 ? 1/5) ? )的结果是多少？

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

结果为25，我们知道这个结果应该是24，这是因为前面我们的算法都是针对整数的, 1/5 =0 ，当然我们可以把整数改成浮点数，比如，修改eval如下：

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

重新计算eval (?5*(5-1/5)?)
结果为 24.0，
但是浮点数带来了误差，不是特别理想，我们前面在介绍类和对象时，使用的Rational例子，任何有理数都可以表示成分数，因此可以利用这个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

我们得出来表达式的精确结果，为分数表示，比如：

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。