把多元運(yùn)算轉(zhuǎn)化為兩元運(yùn)算，先從四個(gè)數(shù)中取出兩個(gè)數(shù)進(jìn)行運(yùn)算，然后把運(yùn)算結(jié)果和第三個(gè)數(shù)進(jìn)行運(yùn)算，再把結(jié)果與第四個(gè)數(shù)進(jìn)行運(yùn)算。在求表達(dá)式的過程中，最難處理的就是對(duì)括號(hào)的處理，而這種思路很好的避免了對(duì)括號(hào)的處理?；谶@種思路的一種算法：因?yàn)槟苁褂玫?4 種運(yùn)算符 – * / 都是2元運(yùn)算符，所以本文中只考慮 2 元運(yùn)算符。2元運(yùn)算符接收兩個(gè)參數(shù)，輸出計(jì)算結(jié)果，輸出的結(jié)果參與后續(xù)的計(jì)算。

由上所述，構(gòu)造所有可能的表達(dá)式的算法如下：

(1) 將 4 個(gè)整數(shù)放入數(shù)組中

(2) 在數(shù)組中取兩個(gè)數(shù)字的排列，共有 P(4,2) 種排列。對(duì)每一個(gè)排列，

(2.1) 對(duì) – * / 每一個(gè)運(yùn)算符，

(2.1.1) 根據(jù)此排列的兩個(gè)數(shù)字和運(yùn)算符，計(jì)算結(jié)果

(2.1.2) 改表數(shù)組：將此排列的兩個(gè)數(shù)字從數(shù)組中去除掉，將 2.1.1 計(jì)算的結(jié)果放入數(shù)組中

(2.1.3) 對(duì)新的數(shù)組，重復(fù)步驟 2

(2.1.4) 恢復(fù)數(shù)組：將此排列的兩個(gè)數(shù)字加入數(shù)組中，將 2.1.1 計(jì)算的結(jié)果從數(shù)組中去除掉

可見這是一個(gè)遞歸過程。步驟 2 就是遞歸函數(shù)。當(dāng)數(shù)組中只剩下一個(gè)數(shù)字的時(shí)候，這就是表達(dá)式的最終結(jié)果，此時(shí)遞歸結(jié)束。

在程序中，一定要注意遞歸的現(xiàn)場保護(hù)和恢復(fù)，也就是遞歸調(diào)用之前與之后，現(xiàn)場狀態(tài)應(yīng)該保持一致。

在上述算法中，遞歸現(xiàn)場就是指數(shù)組，2.1.2 改變數(shù)組以進(jìn)行下一層遞歸調(diào)用，2.1.3 則恢復(fù)數(shù)組，以確保當(dāng)前遞歸調(diào)用獲得下一個(gè)正確的排列。

括號(hào) () 的作用只是改變運(yùn)算符的優(yōu)先級(jí)，也就是運(yùn)算符的計(jì)算順序。所以在以上算法中，無需考慮括號(hào)。括號(hào)只是在輸出時(shí)需加以考慮。

使用這個(gè)算法的一個(gè) Scala 實(shí)現(xiàn)如下：

def solve(vs: List[Int],n: Int = 24){
    def isZero(d: Double) = Math.abs(d) < 0.00001

    //解析為恰當(dāng)?shù)闹芯Y表達(dá)式
    def toStr(any: Any): String = any match {
        case (v: Double,null,null,null) => v.toInt.toString
        case (_,v1: (Double,Any,Any,Any),v2: (Double,Any,Any,Any),op) => 
               if(op=='-'&&(v2._4=='+'||v2._4=='-'))
                   "%s%c(%s)".format(toStr(v1),op,toStr(v2))
               else if(op=='/'){
                   val s1 = if(v1._4=='+'||v1._4=='-') "("+toStr(v1)+")" else toStr(v1)
                   val s2 = if(v2._4==null) toStr(v2) else "("+toStr(v2)+")"
                   s1 + op + s2
               }
               else if(op=='*'){
                   val s1 = if(v1._4=='+'||v1._4=='-') "("+toStr(v1)+")" else toStr(v1)
                   val s2 = if(v2._4=='+'||v2._4=='-') "("+toStr(v2)+")" else toStr(v2)
                   s1 + op + s2
               }
               else toStr(v1) + op + toStr(v2)
    }

    //遞歸求解
    val buf = collection.mutable.ListBuffer[String]()
    def solve0(xs: List[(Double,Any,Any,Any)]): Unit = xs match {
        case x::Nil => if(isZero(x._1-n) && !buf.contains(toStr(x))){ buf += toStr(x); println(buf.last)}
        case _      => for{ x @ (v1,_,_,_) <- xs;val ys = xs diff List(x)
                              y @ (v2,_,_,_) <- ys;val rs = ys diff List(y)
                         }{   solve0((v1+v2,x,y,'+')::rs)
                              solve0((v1-v2,x,y,'-')::rs)
                              solve0((v1*v2,x,y,'*')::rs)
                              if(!isZero(v2)) solve0((v1/v2,x,y,'/')::rs)
                         }
    }
    solve0(vs map {v => (v.toDouble,null,null,null)})
}

測試如下：

scala> solve(List(5,5,5,1))
(5-1/5)*5
5*(5-1/5)

scala> solve(List(3,3,8,8))
8/(3-8/3)

這個(gè)算法的來源于網(wǎng)上，很簡短的代碼就實(shí)現(xiàn)了算 24 的算法，Scala 還是比較強(qiáng)大的:-)

不過我們這里還是采用另外一種方法，來介紹Scala編程的多個(gè)方面。

這個(gè)算法就是列出 4 個(gè)數(shù)字加減乘除的各種可能性。我們可以將表達(dá)式分成以下幾種：首先我們將 4 個(gè)數(shù)設(shè)為 a,b,c,d,，將其排序列出四個(gè)數(shù)的所有排序序列組合（共有 24 種組合）。再進(jìn)行符號(hào)的排列表達(dá)式，其中算術(shù)符號(hào)有+，—，*，/，（，）。其中有效的表達(dá)式有 a*(b-c/b)，a*b-c*d,等等。列出所有有效的表達(dá)式。其中我們用枚舉類型將符號(hào)定義成數(shù)字常量。

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