我們首先通過我們小時(shí)候經(jīng)常玩的算 24 ，通過 Scala 實(shí)現(xiàn)算二十四，編程計(jì)算二十點(diǎn)的算法大多為窮舉法，我們先從最簡單的算法開始，計(jì)算表達(dá)式，還記得以前學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)使用C語言實(shí)現(xiàn)算二十四，需要把表達(dá)式首先轉(zhuǎn)成逆波蘭形式，然后通過棧來計(jì)算表達(dá)式的值，我們看看如果通過Scala的函數(shù)化編程來實(shí)現(xiàn)表達(dá)式的計(jì)算。

算二十四使用基本的四則運(yùn)算，加減乘除，外加括號(hào)。為簡單起見，我們先不考慮帶括號(hào)的四則運(yùn)算，后面再逐步擴(kuò)展，算 24 ，比較有名的一個(gè)例子是 5 5 5 1 ，我們最終的結(jié)果是需要使用 Scala 實(shí)現(xiàn)二十四算法，給出 5 5 5 1 的算法，并可以計(jì)算任意四個(gè)數(shù)，如果有解，給出解，如果窮舉后無解，給出無解的結(jié)果。

四則運(yùn)算具有以下二元計(jì)算基本表現(xiàn)形式：（表達(dá)式） op (表達(dá)式）

其中表達(dá)式可以是個(gè)數(shù)字，或是另外一個(gè)表達(dá)式， op 可以為 + – * /。

比如 3 + 2 ; 3 + 4*3 等等。

對于此類二元運(yùn)算，我們可以設(shè)計(jì)一個(gè) Extractor ，分解出二元表達(dá)式的左右操作數(shù)，還記的我們之前介紹的 Email 的 Extractor 的例子嗎？Scala 專題教程-Extractors(1):分解Email地址的例子

我們模仿分解 Email 的例子，寫出一個(gè)分解加法的 Extractor ，如下：

object Add {
    def apply(expr1:String,expr2:String) = expr1 + "+" + expr2
    def unapply(str:String) :Option[(String,String)] ={
        val parts = str split "\\+"
        if(parts.length==2) Some(parts(0),parts(1)) else None
    }
}

測試一下看看

scala> Add.unapply("3+2")
res1: Option[(String, String)] = Some((3,2))

可以看到 Add 對象成功分解了表達(dá)式 3+2 的兩個(gè)操作數(shù) 3 和 2。

設(shè)計(jì)一個(gè) eval 函數(shù)，來計(jì)算加法的結(jié)果，為簡單起見，我們先只考慮整數(shù)的情況

def eval(str:String):Int = str match{
    case Add(expr1,expr2) => eval(expr1) + eval(expr2)
    case _ => str toInt
}

這個(gè) eval 函數(shù)計(jì)算一個(gè)表達(dá)式的值（目前只支持加法），如果輸入的是一個(gè)加法表達(dá)式，分解后計(jì)算每個(gè)操作時(shí)的值，如果不能分解，那么這是個(gè)整數(shù)，輸出該整數(shù)：

scala> eval("3+5")
res0: Int = 8

scala> eval("4+8")
res1: Int = 12

計(jì)算結(jié)果成功，不過這個(gè)實(shí)現(xiàn)有些局限，我們看看 3+5+3，什么情況：

scala> eval("3+5+3")
java.lang.NumberFormatException: For input string: "3+5+3"
  at java.lang.NumberFormatException.forInputString(NumberFormatException.java:65)
  at java.lang.Integer.parseInt(Integer.java:492)
  at java.lang.Integer.parseInt(Integer.java:527)
  at scala.collection.immutable.StringLike$class.toInt(StringLike.scala:241)
  at scala.collection.immutable.StringOps.toInt(StringOps.scala:30)
  at .eval(<console>:10)
  ... 32 elided

出錯(cuò)了，這是因?yàn)?Extractor 對象 Add 的實(shí)現(xiàn)，只考慮了表達(dá)式只包含一個(gè)“+”的情況，我們修改下 Add 的實(shí)現(xiàn)，不使用 split（使用split,如果有有兩個(gè)+以上，parts.length 就>2)，而是使用 indexOf 來查找”+”號(hào)：

object Add{
  val op:String="+"
  def apply(expr1:String,expr2:String) = expr1 + op + expr2
  def unapply(str:String) :Option[(String,String)] ={
    val index=str indexOf(op)
    if(index>0)
      Some(str substring(0,index),str substring(index+1))
    else None
  }
}

再來計(jì)算”3+5+3″等表達(dá)式的值：

scala> eval("3+5+3")
res0: Int = 11

scala> eval("1+2+3+4+5+6+7+8+9+10")
res1: Int = 55

同樣，我們可以復(fù)制Add，修改op的值，實(shí)現(xiàn) Subtract，Divide，Multiply，為避免重復(fù)代碼，我們可以設(shè)計(jì)一個(gè)抽象 Trait：

trait BinaryOp{
  val op:String
  def apply(expr1:String,expr2:String) = expr1 + op + expr2
  def unapply(str:String) :Option[(String,String)] ={
    val index=str indexOf(op)
    if(index>0)
      Some(str substring(0,index),str substring(index+1))
    else None
  }
}

object Multiply  extends {val op="*"} with BinaryOp
object Divide  extends {val op="/"} with BinaryOp
object Add  extends {val op="+"} with BinaryOp
object Subtract  extends {val op="-"} with BinaryOp

同樣修改 eval 的實(shí)現(xiàn)如下：

def eval(str:String):Int = str match {

    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 _ => str toInt

  }

測試如下：

scala> eval("4*5-2/2")
res3: Int = 19

scala> eval("4*5-5*4")
res4: Int = 0

scala> eval("4*5-5*4-2/2")
res5: Int = 1

scala> eval("4*5-5*4+2/2")
res6: Int = 1

這個(gè)簡單的計(jì)算表達(dá)式的函數(shù) eval 就這么簡單的實(shí)現(xiàn)了，而且代碼也很直觀（盡管還有不少局限性），我們下篇再看看帶括號(hào)的情況。

上一篇：表達(dá)式計(jì)算(三)下一篇：更簡單的表達(dá)式算法