从 Java 中调用 Scala 函数

我们对前面定义的计算 24 的代码,稍作修改,可以在 Java 中调用,在通常情况下在 Java 中调用 Scala 函数非常简单,反之从 Scala 中调用 Java 代码也很简单,这是因为 Scala 代码最终也要编译成 Java class 文件。以后我们将详细介绍 Java 和 Scala 之间的互操作的用法,这里简要介绍下如何在 Java 代码中调用之前我们定义的计算 24 的算法。

在 Scala 二十四点游戏(9): 完整的代码和计算结果我们给出了完整的代码,其中的 Test 由 App 派生,如果我们希望把 Test 定义的一些方法如 cal24,cal24once 作为库函数调用,我们无需让 Test 由 App 派生,另外我们再定义 cal24once 的一个重载版本:

object Cal24 {
   ...
   def cal24once(a:Int,b:Int,c:Int,d:Int) {
   cal24once(List(a,b,c,d))
  }
  def hello {
    println("Hello from Scala")
  }
}

我们把这段代码存成 Cal24.scala. 下面我们使用 scalac 对它进行编译:

scalac Cal24.scala

然后我们列出有 scalac 编译后生成的 class 文件:

Add.class                                          Cal24.class
Add$.class                                         Cal24$.class
BinaryOp.class                                     Cal24.scala
BinaryOp$class.class                               Divide.class
Bracket$$anonfun$matchBracket$1.class              Divide$.class
Bracket$$anonfun$matchBracket$2.class              Multiply.class
Bracket.class                                      Multiply$.class
Bracket$.class                                     Rational.class
Cal24$$anonfun$cal24$1$$anonfun$apply$1.class      Rational$.class
Cal24$$anonfun$cal24$1.class                       Subtract.class
Cal24$$anonfun$cal24once$1$$anonfun$apply$2.class  Subtract$.class
Cal24$$anonfun$cal24once$1$$anonfun$apply$3.class  
Cal24$$anonfun$cal24once$1.class                   
Cal24$$anonfun$calculate$1.class

其中 Cal24 定义了我们所需的库函数,我们可以使用 javap 看看它对应的 java 类定义:

root@ubuntu:/sdb/Scala/Cal24# javap Cal24
Compiled from "Cal24.scala"
public final class Cal24 {
  public static void hello();
  public static void cal24once(int, int, int, int);
  public static void cal24once(scala.collection.immutable.List);
  public static void cal24(scala.collection.immutable.List);
  public static scala.Tuple3 calculate(java.lang.String, scala.collection.immutable.List);
  public static Rational eval(java.lang.String);
  public static scala.collection.immutable.List templates();
}

可以看到 Scala 的 object (singleton对象)对应到 Java 的 public final class, Cal24 的函数为 static

然后我们定义一个 TestCal24.java

public class TestCal24{
    public static void main(String[] args) {
        Cal24.cal24once(5,2,3,4);
    }
}

然后我们使用 javac 来编译 TestCal24.java ,此时我们需要指明 scala 库的位置

javac -cp $SCALA_HOME/lib/scala-library.jar:. TestCal24.java

-cp (class path) 指明 Scala 类定义的路径

然后运行编译后的TestCal24 代码:

root@ubuntu:/sdb/Scala/Cal24# java -cp $SCALA_HOME/lib/scala-library.jar:. TestCal24
List(5, 2, 3, 4):(N-(N-N))*N:(5-(2-3))*4

调用成功,这样你可以在 Java 应用(包括 Android 应用中使用 Scala 的函数库)

更简单的表达式算法

前面我们给出了计算 24 的算法,这并非是计算 24 的 Scala 的最短的代码,除了之前 Scala 二十四点游戏(4):算法之一,在 Scala 中我们还可以使用更简单的方法来计算表达式–从 Scala 2.10.0版本之后,新增了字符串插值的功能,比如:

scala> val name = "James"
name: String = James

scala> println(s"Hello, $name”)s
Hello, James

在字符串前使用 “s”,可以将字符串中包含的字符串变量 varname。

同样,你可以可以使用表达式,比如:

scala> println(s" ${(4.0/10+2)*10}")
 24.0

你可以在 ${} 使用任意的表示式。如果你有兴趣的话,可以自行实现更简洁的 24 点算法或者对本博客的代码进行优化。

完整的代码和计算结果

综合前面的介绍,这里我们给出最终的 24 点游戏的代码:

import scala.collection.mutable.Stack

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
  }
}

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)
}

object Bracket{
  def matchBracket(str:String):Option[(Int,Int)] ={
    val left = str.indexOf('(')
    if(left >=0) {
      val stack = Stack[Char]()
      val remaining = str substring (left+1)
      var index=0
      var right=0
      for(c <-remaining if right==0){ index=index + 1 c match{ case '(' => stack push c
          case ')'  => if (stack isEmpty)  right= left+index else stack pop
          case _ =>
        }

      }

      Some(left,right)
    }else  None
  }

  def apply(part1:String,expr:String,part2:String) =part1+ "(" + expr + ")"+ part2
  def unapply(str:String) :Option[(String,String,String)] ={
     Bracket.matchBracket(str) match{
      case Some((left:Int,right:Int)) =>{
        val part1 = if (left == 0) "" else str substring(0, left )
        val expr = str substring(left + 1, right)
        val part2 = if (right == (str length)-1) "" else str substring (right+1)
        Some(part1, expr, part2)
      }
      case _ => 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
object Rational  extends {val op="\\"} with BinaryOp

object Test extends App{

  val templates=List(
    "N*N-N+N",
    "(N-N)*N*N",
    "N*N+N*N",
    "(N+N)*N*N",
    "N*N*N*N",
    "(N+N*N)*N",
    "(N*N-N)*N",
    "N*N+N+N",
    "(N/N-N)*N",
    "(N-(N-N))*N",
    "N-(N-N-N)",
    "N+N-(N-N)",
    "N*(N/N-N)",
    "(N-N*N)*N",
    "N*(N-N)+N",
    "N+N+N/N",
    "(N-N)*(N-N)",
    "N+N*N/N",
    "N*N/(N-N)",
    "(N+N)*(N+N)",
    "(N-N)*N/N",
    "N+(N+N)/N",
    "N*N/(N+N)",
    "(N+N)*N/N",
    "(N*N+N)*N",
    "(N*N-N)/N",
    "(N/N+N)*N",
    "N*N/N/N",
    "N+N+N-N",
    "N-(N-N)+N",
    "N/(N-N/N)",
    "N+(N-N)*N",
    "(N+N+N)*N",
    "N+N*N-N",
    "N*N-N/N",
    "(N+N)*N-N",
    "(N+N)*(N-N)",
    "(N-N/N)*N",
    "N*(N+N)+N",
    "N*N+N/N",
    "N*N/N-N",
    "(N+N/N)*N",
    "N*N*N/N",
    "(N+N*N)/N",
    "N+N*N+N",
    "N-(N-N)*N",
    "(N-(N+N))*N",
    "N*N-N-N",
    "N+N/N+N",
    "(N-N)*N-N",
    "(N+N)/N+N",
    "N*N+N-N",
    "N/N+N+N",
    "N*N*N-N",
    "(N*N+N)/N",
    "N+N+N*N",
    "N*(N-N)/N",
    "N/N*N+N",
    "N+N*N*N",
    "N+N+N+N",
    "N*N/(N*N)",
    "N+(N+N)*N",
    "(N-N)*N+N",
    "(N+N+N)/N",
    "(N+N)*N+N",
    "N*N*N+N",
    "N*N-(N-N)",
    "N*N-(N+N)",
    "(N-N-N)*N",
    "N*N/N+N",
    "(N+N-N)*N",
    "N/(N/N-N)",
    "N*N-N*N"
  )

  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(0, 1)
      case Rational(expr1, expr2) =>   new Rational(expr1.trim toInt, expr2.trim toInt)
      case _ => new Rational(str.trim toInt, 1)

    }
  }

  def calculate(template:String,numbers:List[Int])={
    val values=template.split('N')
    var expression=""
    for(i <- 0 to 3)  expression=expression+values(i) + numbers(i)
    if (values.length==5) expression=expression+values(4)
    (expression,template,eval(expression))
  }

  def cal24(input:List[Int])={
    var found = false
    for (template <- templates; list <- input.permutations ) { try { val (expression, tp, result) = calculate(template, list) if (result.numer == 24 && result.denom == 1) { println(input + ":" + tp + ":" + expression) found = true } } catch { case e:Throwable=>
      }
    }
    if (!found) {
      println(input+":"+"no result")
    }
  }

  def cal24once(input:List[Int])={
    var found = false
    for (template <- templates; list <- input.permutations if(!found)) { try { val (expression, tp, result) = calculate(template, list) if (result.numer == 24 && result.denom == 1) { println(input + ":" + tp + ":" + expression) found = true } } catch { case e:Throwable=>
      }
    }
    if (!found) {
      println(input+":"+"no result")
    }
  }
  println(cal24once(List(5,5,5,1)))
}

下面给出所有从1到10的四个数字有解的结果:

输入 模板 结果
List(1,1,1,8) (N+N+N)*N (1+1+1)*8
List(1,1,2,10) (N+N)*(N+N) (1+1)*(2+10)
List(1,1,2,6) (N+N)NN (1+1)26
List(1,1,2,7) (N+N)*(N+N) (1+2)*(1+7)
List(1,1,2,8) (N+N)NN (1+2)18
List(1,1,2,9) (N+N)*(N-N) (1+2)*(9-1)
List(1,1,3,10) (N-(N+N))*N (10-(1+1))*3
List(1,1,3,4) (N+N)NN (1+1)34
List(1,1,3,5) (N+N)*(N+N) (1+3)*(1+5)
List(1,1,3,6) (N+N)NN (1+3)16
List(1,1,3,7) (N+N)NN (1+7)13
List(1,1,3,8) N*N-N+N 3*8-1+1
List(1,1,3,9) (N-N)NN (9-1)13
List(1,1,4,10) N*(N+N)+N 10*(1+1)+4
List(1,1,4,4) (N+N+N)*N (1+1+4)*4
List(1,1,4,5) (N+N)NN (1+5)14
List(1,1,4,6) N*N-N+N 4*6-1+1
List(1,1,4,7) (N-N)NN (7-1)14
List(1,1,4,8) (N-N)NN (4-1)18
List(1,1,4,9) (N-N)*(N-N) (1-4)*(1-9)
List(1,1,5,5) (NN-N)N (55-1)1
List(1,1,5,6) (N-N)NN (5-1)16
List(1,1,5,7) (N-N)*(N-N) (1-5)*(1-7)
List(1,1,5,8) (N-(N+N))*N (5-(1+1))*8
List(1,1,6,6) (N+N)*(N+N) (1+1)*(6+6)
List(1,1,6,8) N*N/(N+N) 6*8/(1+1)
List(1,1,6,9) N*(N+N)+N 9*(1+1)+6
List(1,1,7,10) N*(N+N)+N 7*(1+1)+10
List(1,1,8,8) N*(N+N)+N 8*(1+1)+8
List(1,2,2,10) (N+N)NN (2+10)12
List(1,2,2,4) (N+N)NN (1+2)24
List(1,2,2,5) (N+N)NN (1+5)22
List(1,2,2,6) (N+N)NN (2+2)16
List(1,2,2,7) (N-N)NN (7-1)22
List(1,2,2,8) (NN-N)N (22-1)8
List(1,2,2,9) (N+N+N)*N (1+2+9)*2
List(1,2,3,10) (N-N)NN (10-2)13
List(1,2,3,3) (N+N)NN (1+3)23
List(1,2,3,4) NNN*N 123*4
List(1,2,3,5) (N-N)NN (5-1)23
List(1,2,3,6) (N-N)NN (3-1)26
List(1,2,3,7) N*N+N+N 3*7+1+2
List(1,2,3,8) (N-N)NN (2-1)38
List(1,2,3,9) (N+N)NN (3+9)12
List(1,2,4,10) NN+NN 14+210
List(1,2,4,4) (N-N)NN (4-1)24
List(1,2,4,5) (N-(N-N))*N (2-(1-5))*4
List(1,2,4,6) (N-N)NN (2-1)46
List(1,2,4,7) (N-(N-N))*N (1-(2-7))*4
List(1,2,4,8) (N-N)NN (8-2)14
List(1,2,4,9) (N-(N-N))*N (4-(1-9))*2
List(1,2,5,10) N*N-N+N 2*10-1+5
List(1,2,5,5) N*N-N+N 5*5-2+1
List(1,2,5,6) (N-(N-N))*N (1-(2-5))*6
List(1,2,5,7) (N+N)NN (5+7)12
List(1,2,5,8) (N-N)NN (5-2)18
List(1,2,5,9) N*N+N+N 2*9+1+5
List(1,2,6,10) (N/N-N)*N (10/2-1)*6
List(1,2,6,6) (N-N)NN (6-2)16
List(1,2,6,7) (N-(N-N))*N (6-(1-7))*2
List(1,2,6,8) N*N/N/N 1*6/2/8
List(1,2,6,9) NN+NN 16+29
List(1,2,7,10) NN+NN 110+27
List(1,2,7,7) (N*N-N)/N (7*7-1)/2
List(1,2,7,8) N*N+N+N 2*8+1+7
List(1,2,7,9) N*N-N+N 2*9-1+7
List(1,2,8,10) N*(N-N)+N 2*(8-1)+10
List(1,2,8,8) NN+NN 18+28
List(1,2,8,9) N*N-N+N 2*8-1+9
List(1,3,10,10) N+N+N+N 1+3+10+10
List(1,3,3,10) (N-(N-N))*N (1-(3-10))*3
List(1,3,3,3) (NN-N)N (33-1)3
List(1,3,3,4) (N-N)NN (3-1)34
List(1,3,3,5) (N+N)NN (3+5)13
List(1,3,3,6) (N-(N-N))*N (3-(1-6))*3
List(1,3,3,7) NN+NN 13+37
List(1,3,3,8) N*(N-N)+N 3*(8-1)+3
List(1,3,3,9) (NN-N)N (39-3)1
List(1,3,4,10) N*(N-N)+N 10*(3-1)+4
List(1,3,4,4) (N+N)NN (4+4)13
List(1,3,4,5) N*N+N+N 4*5+1+3
List(1,3,4,6) N/(N-N/N) 6/(1-3/4)
List(1,3,4,7) N*N-N+N 3*7-1+4
List(1,3,4,8) (N-(N-N))*N (1-(3-8))*4
List(1,3,4,9) N*N-N+N 3*9-4+1
List(1,3,5,10) N*N-N+N 3*5-1+10
List(1,3,5,6) N*N+N+N 3*6+1+5
List(1,3,5,7) (N+N)*(N-N) (1+5)*(7-3)
List(1,3,5,8) N*N+N+N 3*5+1+8
List(1,3,5,9) NN+NN 19+35
List(1,3,6,10) (NN-N)N (310-6)1
List(1,3,6,6) NN+NN 16+36
List(1,3,6,7) N*N-N+N 3*6-1+7
List(1,3,6,8) (N-N)NN (6-3)18
List(1,3,6,9) N*(N-N)+N 3*(6-1)+9
List(1,3,7,10) N*N-N+N 3*10-7+1
List(1,3,7,7) (N-N)*(N-N) (1-7)*(3-7)
List(1,3,7,8) N/(N-N/N) 3/(1-7/8)
List(1,3,7,9) (N+N)*N/N (1+7)*9/3
List(1,3,8,10) (N-N)*N/N (10-1)*8/3
List(1,3,8,8) N*(N-N)+N 8*(3-1)+8
List(1,3,8,9) N*N/N/N 1*8/3/9
List(1,3,9,10) (N+N)*N-N (1+10)*3-9
List(1,3,9,9) (N-N)*N/N (9-1)*9/3
List(1,4,10,10) N*N+N+N 1*4+10+10
List(1,4,4,10) (N-N)NN (10-4)14
List(1,4,4,4) (N+N)*(N-N) (4+4)*(4-1)
List(1,4,4,5) NN+NN 14+45
List(1,4,4,6) N*(N-N)+N 4*(6-1)+4
List(1,4,4,7) (NN-N)N (47-4)1
List(1,4,4,8) NN+NN 18+44
List(1,4,4,9) N*N-N+N 4*4-1+9
List(1,4,5,10) (N-(N-N))*N (1-(5-10))*4
List(1,4,5,5) N*N-N+N 4*5-1+5
List(1,4,5,6) N/(N-N/N) 4/(1-5/6)
List(1,4,5,7) N*N-N+N 4*7-5+1
List(1,4,5,8) N*(N-N)+N 4*(5-1)+8
List(1,4,5,9) N*(N-N)+N 5*(4-1)+9
List(1,4,6,10) (N-N)*N-N (4-1)*10-6
List(1,4,6,6) N*(N-N)+N 6*(4-1)+6
List(1,4,6,7) (N-(N-N))*N (1-(4-7))*6
List(1,4,6,8) (N-N)NN (8-4)16
List(1,4,6,9) (N-(N+N))*N (9-(1+4))*6
List(1,4,7,7) (N+N)*(N-N) (1+7)*(7-4)
List(1,4,7,8) (N-N)NN (7-4)18
List(1,4,7,9) (N-N)*(N-N) (1-9)*(4-7)
List(1,4,8,8) (NN-N)N (48-8)1
List(1,4,8,9) N*N-N+N 4*8-9+1
List(1,4,9,10) N+N+N+N 1+4+9+10
List(1,5,10,10) N+N-(N-N) 5+10-(1-10)
List(1,5,5,10) (N-N)*N-N (10-5)*5-1
List(1,5,5,5) (N-N/N)*N (5-1/5)*5
List(1,5,5,6) (N+N)*N-N (1+5)*5-6
List(1,5,5,9) (N+N)*(N-N) (1+5)*(9-5)
List(1,5,6,10) (N+N)*(N-N) (1+5)*(10-6)
List(1,5,6,6) (NN-N)N (56-6)1
List(1,5,6,7) N*N-N+N 5*6-7+1
List(1,5,6,8) (N-(N-N))*N (1-(5-8))*6
List(1,5,6,9) (N-N)NN (9-5)16
List(1,5,7,10) (N/N+N)*N (7/5+1)*10
List(1,5,7,8) (N-(N-N))*N (1-(5-7))*8
List(1,5,7,9) (N-N)*(N-N) (1-7)*(5-9)
List(1,5,8,10) (N/N+N)*N (10/5+1)*8
List(1,5,8,8) (N-N)NN (8-5)18
List(1,5,8,9) (N-N)*(N-N) (1-9)*(5-8)
List(1,5,9,10) N*N+N+N 1*5+9+10
List(1,5,9,9) N+N+N+N 1+5+9+9
List(1,6,6,10) (N-N)NN (10-6)16
List(1,6,6,6) (N-N)*N-N (6-1)*6-6
List(1,6,6,8) N/(N-N/N) 6/(1-6/8)
List(1,6,6,9) (N-(N-N))*N (1-(6-9))*6
List(1,6,7,10) (N-(N-N))*N (1-(7-10))*6
List(1,6,7,9) (N+N)*(N-N) (1+7)*(9-6)
List(1,6,8,10) N*N+N+N 1*6+8+10
List(1,6,8,8) (N-(N-N))*N (1-(6-8))*8
List(1,6,8,9) (N-N)NN (9-6)18
List(1,6,9,10) N+N-(N-N) 6+9-(1-10)
List(1,6,9,9) N*N+N+N 1*6+9+9
List(1,7,7,10) N*N+N+N 1*7+7+10
List(1,7,7,9) N+N+N+N 1+7+7+9
List(1,7,8,10) (N-N)NN (10-7)18
List(1,7,8,8) N+N+N+N 1+7+8+8
List(1,7,8,9) N*N+N+N 1*7+8+9
List(1,7,9,10) (N-N)*(N-N) (1-9)*(7-10)
List(1,7,9,9) N+N-(N-N) 7+9-(1-9)
List(1,8,8,10) (N-(N-N))*N (1-(8-10))*8
List(1,8,8,8) N*N+N+N 1*8+8+8
List(1,8,8,9) N+N-(N-N) 8+8-(1-9)
List(2,2,10,10) N*N+N+N 2*2+10+10
List(2,2,2,10) NN+NN 22+210
List(2,2,2,3) (N+N)NN (2+2)23
List(2,2,2,4) (N+N)NN (2+4)22
List(2,2,2,5) (N+NN)N (2+25)2
List(2,2,2,7) (NN-N)N (27-2)2
List(2,2,2,8) (N-N)NN (8-2)22
List(2,2,2,9) N*(N+N)+N 2*(2+9)+2
List(2,2,3,10) (N+N)*N-N (3+10)*2-2
List(2,2,3,3) (N+N)NN (3+3)22
List(2,2,3,4) (N+NN)N (4+22)3
List(2,2,3,5) (NN-N)N (25-2)3
List(2,2,3,6) (N-N)NN (6-2)23
List(2,2,3,7) (N/N+N)*N (2/2+7)*3
List(2,2,3,8) N*N-N+N 3*8-2+2
List(2,2,3,9) (N-N)NN (9-3)22
List(2,2,4,10) (N-N)NN (10-4)22
List(2,2,4,4) (N+NN)N (4+24)2
List(2,2,4,5) (N-N)NN (5-2)24
List(2,2,4,6) N*N-N+N 4*6-2+2
List(2,2,4,7) (N+N)*N-N (2+2)*7-4
List(2,2,4,8) NN+NN 24+28
List(2,2,4,9) N*N+N+N 2*9+2+4
List(2,2,5,10) (N-N)*(N-N) (2-5)*(2-10)
List(2,2,5,5) (N+N+N)*N (2+5+5)*2
List(2,2,5,6) (N+N)*(N-N) (2+6)*(5-2)
List(2,2,5,7) NN+NN 25+27
List(2,2,5,8) (N+N)*N-N (5+8)*2-2
List(2,2,5,9) (N-(N-N))*N (5-(2-9))*2
List(2,2,6,10) N*N-N+N 2*10-2+6
List(2,2,6,6) NN+NN 26+26
List(2,2,6,7) (N+N)*N-N (6+7)*2-2
List(2,2,6,8) N*N+N+N 2*8+2+6
List(2,2,6,9) (NN-N)N (29-6)2
List(2,2,7,10) (N/N+N)*N (10/2+7)*2
List(2,2,7,7) (N-(N-N))*N (7-(2-7))*2
List(2,2,7,8) N*N+N+N 2*7+2+8
List(2,2,8,10) N*N-N+N 2*8-2+10
List(2,2,8,8) (N-N)*N/N (8-2)*8/2
List(2,2,8,9) N*N-N+N 2*9-2+8
List(2,2,9,10) N*(N-N)+N 2*(9-2)+10
List(2,3,10,10) N*(N-N)+N 2*(10-3)+10
List(2,3,3,10) (N/N+N)*N (10/2+3)*3
List(2,3,3,3) (N+NN)N (3+33)2
List(2,3,3,5) (NN-N)N (35-3)2
List(2,3,3,6) NN+NN 23+36
List(2,3,3,7) (N-N)NN (7-3)23
List(2,3,3,8) (N-N)NN (3-2)38
List(2,3,3,9) N*N+N+N 2*9+3+3
List(2,3,4,10) N*N+N+N 3*4+2+10
List(2,3,4,4) (N-N)NN (4-2)34
List(2,3,4,5) (N-(N-N))*N (3-(2-5))*4
List(2,3,4,6) (N-N)NN (3-2)46
List(2,3,4,7) (N-(N-N))*N (2-(3-7))*4
List(2,3,4,8) (N-N)NN (8-4)23
List(2,3,4,9) (N+N)*N/N (3+9)*4/2
List(2,3,5,10) (N-(N-N))*N (5-(3-10))*2
List(2,3,5,5) N*N-N+N 5*5-3+2
List(2,3,5,6) (N-N)NN (5-3)26
List(2,3,5,7) N*N-N+N 3*7-2+5
List(2,3,5,8) N*N+N+N 2*8+3+5
List(2,3,5,9) N*N-N+N 3*9-5+2
List(2,3,6,10) (N-N)NN (10-6)23
List(2,3,6,6) (NN-N)N (36-6)2
List(2,3,6,7) (NN-N)N (27-6)3
List(2,3,6,8) N*N-N+N 3*6-2+8
List(2,3,6,9) N*N+N+N 2*6+3+9
List(2,3,7,10) N*N-N+N 2*10-3+7
List(2,3,7,7) N*N+N+N 2*7+3+7
List(2,3,7,8) (N-(N-N))*N (7-(3-8))*2
List(2,3,7,9) (NN-N)N (37-9)2
List(2,3,8,10) N*N-N+N 3*10-8+2
List(2,3,8,8) (NN-N)N (28-8)3
List(2,3,8,9) (N-NN)N (9-23)8
List(2,3,9,10) (NN-N)N (29-10)3
List(2,3,9,9) N*N-N+N 2*9-3+9
List(2,4,10,10) (N/N+N)*N (4/10+2)*10
List(2,4,4,10) N*N-N+N 4*4-2+10
List(2,4,4,4) NN+NN 24+44
List(2,4,4,5) (NN-N)N (25-4)4
List(2,4,4,6) (NN-N)N (24-4)6
List(2,4,4,7) (N-N)NN (7-4)24
List(2,4,4,8) N*N+N+N 2*8+4+4
List(2,4,4,9) (N-N)*N-N (9-2)*4-4
List(2,4,5,10) N*N+N+N 2*5+4+10
List(2,4,5,5) N*(N+N)+N 2*(5+5)+4
List(2,4,5,6) N*N-N+N 4*5-2+6
List(2,4,5,7) (N+N)*N/N (5+7)*4/2
List(2,4,5,8) (N-N)NN (8-5)24
List(2,4,5,9) (N-(N-N))*N (2-(5-9))*4
List(2,4,6,10) N*N+N+N 2*4+6+10
List(2,4,6,6) (N-N)NN (6-4)26
List(2,4,6,7) N*N-N+N 4*7-6+2
List(2,4,6,8) N*N+N+N 2*6+4+8
List(2,4,6,9) (N-N)NN (9-6)24
List(2,4,7,10) (N-N)NN (10-7)24
List(2,4,7,7) (N+N)*N-N (7+7)*2-4
List(2,4,7,8) (NN-N)N (27-8)4
List(2,4,7,9) N*N+N+N 2*4+7+9
List(2,4,8,10) N*N-N+N 2*10-4+8
List(2,4,8,8) N*N+N+N 2*4+8+8
List(2,4,8,9) (N-(N+N))*N (9-(2+4))*8
List(2,4,9,10) N*N-N+N 2*9-4+10
List(2,4,9,9) N+N+N+N 2+4+9+9
List(2,5,10,10) (N+N)*N/N (2+10)*10/5
List(2,5,5,10) (N-N/N)*N (5-2/10)*5
List(2,5,5,7) N*N+N+N 2*7+5+5
List(2,5,5,8) (N/N+N)*N (5/5+2)*8
List(2,5,5,9) N*N+N+N 2*5+5+9
List(2,5,6,10) (N/N+N)*N (10/5+2)*6
List(2,5,6,6) (NN-N)N (25-6)6
List(2,5,6,7) (N-N)NN (7-5)26
List(2,5,6,8) N*N-N+N 5*6-8+2
List(2,5,6,9) N+N*N/N 9+5*6/2
List(2,5,7,10) (N-(N-N))*N (7-(5-10))*2
List(2,5,7,7) N*N+N+N 2*5+7+7
List(2,5,7,8) (NN-N)N (25-7)8
List(2,5,7,9) N*N-(N+N) 5*7-(2+9)
List(2,5,8,10) (N-N)*(N-N) (2-10)*(5-8)
List(2,5,8,8) (N+N*N)/N (8+5*8)/2
List(2,5,8,9) (N-(N-N))*N (8-(5-9))*2
List(2,5,9,10) N*N-N+N 2*10-5+9
List(2,6,10,10) N*N-N+N 2*10-6+10
List(2,6,6,10) N*N/N-N 6*10/2-6
List(2,6,6,6) N*N+N+N 2*6+6+6
List(2,6,6,7) (N-N/N)*N (7-6/2)*6
List(2,6,6,8) (N-N)NN (8-6)26
List(2,6,6,9) (N*N-N)/N (6*9-6)/2
List(2,6,7,10) (NN-N)N (27-10)6
List(2,6,7,8) (N-(N-N))*N (2-(6-7))*8
List(2,6,7,9) (N-N)NN (9-7)26
List(2,6,8,10) (N-N)NN (10-8)26
List(2,6,8,8) (N-N/N)*N (8-8/2)*6
List(2,6,8,9) (NN-N)N (26-9)8
List(2,6,9,10) (N-N)*(N-N) (2-10)*(6-9)
List(2,6,9,9) (N-(N-N))*N (9-(6-9))*2
List(2,7,10,10) (N-N)*(N-N) (2-10)*(7-10)
List(2,7,7,10) (N/N+N)*N (10/7+2)*7
List(2,7,7,8) (N/N+N)*N (7/7+2)*8
List(2,7,8,8) (N-(N-N))*N (2-(7-8))*8
List(2,7,8,9) (N+N)*N-N (7+9)*2-8
List(2,7,9,10) (N-(N-N))*N (9-(7-10))*2
List(2,8,10,10) (N-(N-N))*N (10-(8-10))*2
List(2,8,8,10) N+N-(N-N) 8+8-(2-10)
List(2,8,8,8) (N/N+N)*N (8/8+2)*8
List(2,8,8,9) (N-(N-N))*N (2-(8-9))*8
List(2,8,9,10) (N-(N-N))*N (2-(9-10))*8
List(2,8,9,9) N+N-(N-N) 8+9-(2-9)
List(2,9,10,10) N+N+N/N 9+10+10/2
List(3,3,3,10) N*(N-N)+N 3*(10-3)+3
List(3,3,3,3) NNN-N 333-3
List(3,3,3,4) (NN-N)N (33-3)4
List(3,3,3,5) NN+NN 33+35
List(3,3,3,6) N*N+N+N 3*6+3+3
List(3,3,3,7) (N/N+N)*N (3/3+7)*3
List(3,3,3,8) N*N-N+N 3*8-3+3
List(3,3,3,9) (N-N/N)*N (9-3/3)*3
List(3,3,4,4) NN+NN 34+34
List(3,3,4,5) (N-N)NN (5-3)34
List(3,3,4,6) N*N-N+N 4*6-3+3
List(3,3,4,7) (N-(N-N))*N (4-(3-7))*3
List(3,3,4,8) (N-N)NN (4-3)38
List(3,3,4,9) N*N+N+N 3*4+3+9
List(3,3,5,10) N*N+N+N 3*3+5+10
List(3,3,5,5) N*N-N/N 5*5-3/3
List(3,3,5,6) (NN-N)N (33-5)6
List(3,3,5,7) (NN-N)N (35-7)3
List(3,3,5,9) (N+N)*N/N (3+5)*9/3
List(3,3,6,10) (NN-N)N (36-10)3
List(3,3,6,6) (N/N+N)*N (6/3+6)*3
List(3,3,6,7) N*N-N+N 3*7-3+6
List(3,3,6,8) (NN-N)N (33-6)8
List(3,3,6,9) N*N-N+N 3*6-3+9
List(3,3,7,7) (N/N+N)*N (3/7+3)*7
List(3,3,7,8) N*N+N+N 3*3+7+8
List(3,3,7,9) (N-N)*(N-N) (3-7)*(3-9)
List(3,3,8,10) N+N+N+N 3+3+8+10
List(3,3,8,8) N/(N-N/N) 8/(3-8/3)
List(3,3,8,9) N*(N-N)+N 3*(8-3)+9
List(3,3,9,10) N*N-N+N 3*10-9+3
List(3,3,9,9) N*N-N/N 3*9-9/3
List(3,4,10,10) N*N-N+N 3*10-10+4
List(3,4,4,10) (N-N)*N-N (10-3)*4-4
List(3,4,4,4) (N+N)*N-N (3+4)*4-4
List(3,4,4,5) N*N+N+N 4*4+3+5
List(3,4,4,6) (N-N)NN (4-3)46
List(3,4,4,7) (N-(N-N))*N (3-(4-7))*4
List(3,4,4,8) N*N-N+N 3*8-4+4
List(3,4,4,9) (N+N)*N/N (4+4)*9/3
List(3,4,5,10) N*(N-N)+N 10*(5-3)+4
List(3,4,5,5) N*N-N+N 5*5-4+3
List(3,4,5,6) (N-(N-N))*N (3-(4-5))*6
List(3,4,5,7) N*N-N+N 4*5-3+7
List(3,4,5,8) (N-N)NN (5-4)38
List(3,4,5,9) (NN-N)N (35-9)4
List(3,4,6,10) N*N-N+N 3*6-4+10
List(3,4,6,6) N*N+N+N 3*4+6+6
List(3,4,6,8) (N-N)NN (8-6)34
List(3,4,6,9) (N-(N-N))*N (3-(6-9))*4
List(3,4,7,10) (N-(N-N))*N (3-(7-10))*4
List(3,4,7,7) N*N-N+N 3*7-4+7
List(3,4,7,8) N*(N-N)+N 4*(7-3)+8
List(3,4,7,9) N*N-N+N 3*9-7+4
List(3,4,8,10) (N-N)NN (10-8)34
List(3,4,8,9) (NN-N)N (34-9)8
List(3,4,9,9) N*(N-N)+N 3*(9-4)+9
List(3,5,10,10) (N-N/N)*N (10-10/5)*3
List(3,5,5,6) (N/N+N)*N (5/5+3)*6
List(3,5,5,7) (N/N+N)*N (5/5+7)*3
List(3,5,5,8) N*N-N+N 3*8-5+5
List(3,5,5,9) (N/N+N)*N (9/5+3)*5
List(3,5,6,10) (N/N+N)*N (10/5+6)*3
List(3,5,6,6) (N-(N-N))*N (3-(5-6))*6
List(3,5,6,7) (N-(N-N))*N (6-(5-7))*3
List(3,5,6,8) (N-N)NN (6-5)38
List(3,5,6,9) N*N-N+N 5*6-9+3
List(3,5,7,10) (N-(N-N))*N (5-(7-10))*3
List(3,5,7,8) N*N-N+N 3*7-5+8
List(3,5,7,9) (N+N)*(N-N) (3+9)*(7-5)
List(3,5,8,8) N*(N-N)+N 8*(5-3)+8
List(3,5,8,9) N*N-N+N 3*9-8+5
List(3,5,9,10) N*(N-N)+N 3*(10-5)+9
List(3,5,9,9) (N-N)*(N-N) (3-9)*(5-9)
List(3,6,10,10) (N/N+N)*N (10/10+3)*6
List(3,6,6,10) (N-N)*N-N (6-3)*10-6
List(3,6,6,6) N*(N-N)+N 6*(6-3)+6
List(3,6,6,7) (N-(N-N))*N (3-(6-7))*6
List(3,6,6,8) N*N-N+N 3*8-6+6
List(3,6,6,9) N+N*N/N 6+6*9/3
List(3,6,7,10) N+N*N/N 10+6*7/3
List(3,6,7,7) (N-(N-N))*N (7-(6-7))*3
List(3,6,7,8) (N-N)NN (7-6)38
List(3,6,7,9) N*N-N+N 3*7-6+9
List(3,6,8,10) (N-(N-N))*N (6-(8-10))*3
List(3,6,8,8) N+N*N/N 8+6*8/3
List(3,6,8,9) (N-(N-N))*N (3-(8-9))*6
List(3,6,9,10) (N-(N-N))*N (3-(9-10))*6
List(3,6,9,9) N*N-N+N 3*9-9+6
List(3,7,10,10) N+N-(N-N) 7+10-(3-10)
List(3,7,7,10) N*N-N+N 3*7-7+10
List(3,7,7,7) (N/N+N)*N (7/7+7)*3
List(3,7,7,8) N*N-N+N 3*8-7+7
List(3,7,7,9) (N-N/N)*N (9-7/7)*3
List(3,7,8,8) (N-N)NN (8-7)38
List(3,7,8,9) (N-(N-N))*N (7-(8-9))*3
List(3,7,9,10) N*N-N+N 3*9-10+7
List(3,7,9,9) (N/N+N)*N (9/9+7)*3
List(3,8,10,10) N*N-N+N 3*8-10+10
List(3,8,8,10) (N*N-N)/N (8*10-8)/3
List(3,8,8,8) N*N-N+N 3*8-8+8
List(3,8,8,9) (N-N)NN (9-8)38
List(3,8,9,10) (N-N)NN (10-9)38
List(3,8,9,9) N*N-N+N 3*8-9+9
List(3,9,10,10) (N-N/N)*N (9-10/10)*3
List(3,9,9,10) (N-(N-N))*N (9-(10-9))*3
List(3,9,9,9) N+N-(N-N) 9+9-(3-9)
List(4,4,10,10) (N*N-N)/N (10*10-4)/4
List(4,4,4,10) (NN-N)N (44-10)4
List(4,4,4,4) N*N+N+N 4*4+4+4
List(4,4,4,5) (N/N+N)*N (4/4+5)*4
List(4,4,4,6) N*N-N+N 4*6-4+4
List(4,4,4,7) (N+N)*(N-N) (4+4)*(7-4)
List(4,4,4,8) (N/N+N)*N (8/4+4)*4
List(4,4,4,9) N*(N-N)+N 4*(9-4)+4
List(4,4,5,10) N*(N-N)+N 4*(10-5)+4
List(4,4,5,5) (N-(N-N))*N (5-(4-5))*4
List(4,4,5,6) (N-N)NN (5-4)46
List(4,4,5,7) (N-(N-N))*N (4-(5-7))*4
List(4,4,5,8) N*N-N+N 4*5-4+8
List(4,4,6,10) N*(N-N)+N 10*(6-4)+4
List(4,4,6,8) (N-(N-N))*N (4-(6-8))*4
List(4,4,6,9) N*N/N/N 4*4/6/9
List(4,4,7,10) (N+N)*(N-N) (4+4)*(10-7)
List(4,4,7,7) (N-N/N)*N (4-4/7)*7
List(4,4,7,8) N*N-N+N 4*7-8+4
List(4,4,7,9) (N-(N-N))*N (4-(7-9))*4
List(4,4,8,10) (N-(N-N))*N (4-(8-10))*4
List(4,4,8,8) N*(N-N)+N 4*(8-4)+8
List(4,4,8,9) N*N-(N+N) 4*9-(4+8)
List(4,5,10,10) N+N*N/N 4+10*10/5
List(4,5,5,10) N+N+N+N 4+5+5+10
List(4,5,5,5) N*N-N+N 5*5-5+4
List(4,5,5,6) N*N-N+N 4*6-5+5
List(4,5,5,7) (N-N/N)*N (7-5/5)*4
List(4,5,5,8) (N-N/N)*N (4-5/5)*8
List(4,5,5,9) N*N-N+N 4*5-5+9
List(4,5,6,10) N*N-N+N 4*5-6+10
List(4,5,6,6) (N-N)NN (6-5)46
List(4,5,6,7) (N-(N-N))*N (5-(6-7))*4
List(4,5,6,8) (N-(N-N))*N (4-(6-5))*8
List(4,5,6,9) N+N+N+N 4+5+6+9
List(4,5,7,10) N*(N-N)+N 10*(7-5)+4
List(4,5,7,7) (N/N+N)*N (7/7+5)*4
List(4,5,7,8) (N-(N-N))*N (5-(7-8))*4
List(4,5,7,9) N*N-N+N 4*7-9+5
List(4,5,8,10) (N+N)*N/N (4+8)*10/5
List(4,5,8,8) (N/N+N)*N (8/8+5)*4
List(4,5,8,9) (N-(N-N))*N (5-(8-9))*4
List(4,5,9,10) (N-(N-N))*N (5-(9-10))*4
List(4,5,9,9) (N/N+N)*N (9/9+5)*4
List(4,6,10,10) N*N-N+N 4*6-10+10
List(4,6,6,10) (N+N)*N/N (6+10)*6/4
List(4,6,6,6) N*N-N+N 4*6-6+6
List(4,6,6,7) (N-N)NN (7-6)46
List(4,6,6,8) N*N/(N-N) 6*8/(6-4)
List(4,6,6,9) N*(N-N)+N 9*(6-4)+6
List(4,6,7,10) N*N-N+N 4*7-10+6
List(4,6,7,7) N*N-N+N 4*6-7+7
List(4,6,7,8) (N-N)NN (8-7)46
List(4,6,7,9) (N+N)*N/N (7+9)*6/4
List(4,6,8,10) N*(N-N)+N 4*(10-6)+8
List(4,6,8,8) N*N-N+N 4*6-8+8
List(4,6,8,9) (N-N)NN (9-8)46
List(4,6,9,10) (N-N)NN (10-9)46
List(4,6,9,9) N*N-N+N 4*6-9+9
List(4,7,10,10) (N-N/N)*N (7-10/10)*4
List(4,7,7,7) (N-N/N)*N (7-7/7)*4
List(4,7,7,8) (N-(N-N))*N (7-(8-7))*4
List(4,7,8,10) N+N*N/N 10+7*8/4
List(4,7,8,8) (N-(N-N))*N (4-(8-7))*8
List(4,7,8,9) (N-(N-N))*N (7-(9-8))*4
List(4,7,9,10) (N-(N-N))*N (7-(10-9))*4
List(4,7,9,9) (N-N/N)*N (7-9/9)*4
List(4,8,10,10) N+N-(N-N) 8+10-(4-10)
List(4,8,8,10) (N-(N-N))*N (8-(10-8))*4
List(4,8,8,8) N+N*N/N 8+8*8/4
List(4,8,8,9) (N-(N-N))*N (4-(9-8))*8
List(4,8,9,10) (N-(N-N))*N (4-(10-9))*8
List(4,8,9,9) (N-N/N)*N (4-9/9)*8
List(4,9,9,10) N+N-(N-N) 9+9-(4-10)
List(5,5,10,10) N*N-N/N 5*5-10/10
List(5,5,5,5) N*N-N/N 5*5-5/5
List(5,5,5,6) N*N-N+N 5*5-6+5
List(5,5,5,9) N+N+N+N 5+5+5+9
List(5,5,6,6) (N-(N-N))*N (5-(6-5))*6
List(5,5,6,7) N*N-N+N 5*5-7+6
List(5,5,6,8) N+N+N+N 5+5+6+8
List(5,5,7,10) (N+N)*N/N (5+7)*10/5
List(5,5,7,7) N*N-N/N 5*5-7/7
List(5,5,7,8) N*N-N+N 5*5-8+7
List(5,5,8,10) (N+N)*N/N (5+10)*8/5
List(5,5,8,8) N*N-N/N 5*5-8/8
List(5,5,8,9) N*N-N+N 5*5-9+8
List(5,5,9,10) N*N-N+N 5*5-10+9
List(5,5,9,9) N*N-N/N 5*5-9/9
List(5,6,10,10) (N+N)*N/N (10+10)*6/5
List(5,6,6,10) (N+N)*N/N (6+6)*10/5
List(5,6,6,6) (N-N/N)*N (5-6/6)*6
List(5,6,6,7) (N-(N-N))*N (5-(7-6))*6
List(5,6,6,8) N*(N-N)+N 6*(8-5)+6
List(5,6,6,9) NN-NN 69-56
List(5,6,7,7) (N-N/N)*N (5-7/7)*6
List(5,6,7,8) (N-(N-N))*N (5-(8-7))*6
List(5,6,7,9) N*(N-N)+N 9*(7-5)+6
List(5,6,8,10) N*N/N/N 5*6/10/8
List(5,6,8,8) (N-(N-N))*N (5-(8-6))*8
List(5,6,8,9) (N-(N-N))*N (5-(9-8))*6
List(5,6,9,10) (N-(N-N))*N (5-(10-9))*6
List(5,6,9,9) N*(N-N)+N 5*(9-6)+9
List(5,7,10,10) N+N*N/N 10+7*10/5
List(5,7,7,10) N*(N-N)+N 7*(7-5)+10
List(5,7,7,9) (N+N)*(N-N) (5+7)*(9-7)
List(5,7,8,10) (N+N)*(N-N) (5+7)*(10-8)
List(5,7,8,8) N*(N-N)+N 8*(7-5)+8
List(5,7,8,9) (N-(N-N))*N (5-(9-7))*8
List(5,7,9,10) N*(N-N)+N 5*(10-7)+9
List(5,8,8,10) (N-(N-N))*N (5-(10-8))*8
List(5,8,8,8) N*N-(N+N) 5*8-(8+8)
List(5,8,8,9) N*N/(N-N) 8*9/(8-5)
List(5,9,10,10) N+N-(N-N) 9+10-(5-10)
List(6,10,10,10) N+N-(N-N) 10+10-(6-10)
List(6,6,6,10) NN-NN 610-66
List(6,6,6,6) N+N+N+N 6+6+6+6
List(6,6,6,8) (N-(N-N))*N (6-(8-6))*6
List(6,6,6,9) N*(N-N)+N 6*(9-6)+6
List(6,6,7,10) N*(N-N)+N 6*(10-7)+6
List(6,6,7,9) (N-(N-N))*N (6-(9-7))*6
List(6,6,8,10) (N-(N-N))*N (6-(10-8))*6
List(6,6,8,8) N*N/(N-N) 6*8/(8-6)
List(6,6,8,9) (N-(N-N))*N (6-(9-6))*8
List(6,6,9,10) (N+N)*N/N (6+10)*9/6
List(6,7,10,10) (N-N)*N-N (10-7)*10-6
List(6,7,7,10) (N-(N-N))*N (7-(10-7))*6
List(6,7,8,10) (N-(N-N))*N (6-(10-7))*8
List(6,7,8,9) N*N/(N-N) 6*8/(9-7)
List(6,7,9,9) N*(N-N)+N 9*(9-7)+6
List(6,8,8,10) N*N/(N-N) 6*8/(10-8)
List(6,8,8,8) N*(N-N)+N 8*(8-6)+8
List(6,8,8,9) (N+N)*N/N (8+8)*9/6
List(6,8,9,10) N*(N-N)+N 9*(10-8)+6
List(6,8,9,9) N*N/(N-N) 8*9/(9-6)
List(6,9,9,10) N+N*N/N 9+9*10/6
List(7,7,9,10) N*(N-N)+N 7*(9-7)+10
List(7,8,10,10) N*(N-N)+N 7*(10-8)+10
List(7,8,8,10) NN-NN 810-78
List(7,8,8,9) N*(N-N)+N 8*(9-7)+8
List(7,8,9,10) N*N/(N-N) 8*9/(10-7)
List(8,8,8,10) N*(N-N)+N 8*(10-8)+8

计算 24 的算法

有了前面的准备工作,我们现在可以给出二十四游戏的算法,首先我们合并表示式模板和输入的四个数字,计算出结果:

def calculate(template:String,numbers:List[Int])={
    val values=template.split('N')
    var expression=""
    for(i <- 0 to 3)  expression=expression+values(i) + numbers(i)
    if (values.length==5) expression=expression+values(4)
    (expression,template,eval(expression))
  }

做些简单的测试如下:

scala> calculate("N/N*N+N",List(6,9,9,10))
res0: (String, String, Rational) = (6/9*9+10,N/N*N+N,16\1)
scala> calculate("N/N*N+N",List(9,6,10,9))
res1: (String, String, Rational) = (9/6*10+9,N/N*N+N,24\1)
scala> calculate("(N-N/N)*N",List(5,1,5,5))
res2: (String, String, Rational) = ((5-1/5)*5,(N-N/N)*N,24\1)

我们让函数 calculate 返回三个值,合成的表达式,使用的模板,计算的结果(分数形式),我们使用一个三元组作为返回结果,这里也可以看到 Scala 函数返回,无需使用 return,函数体的最后一条语句的值作为返回结果。

说到这里,在之前的 Rational 的实现和 eval 函数的实现有一个小错误(表达式出现中的歧义),之前 Rational 的字符表现形式为

override def toString = numer + "/" +denom

使用到的“/”和 我们使用的四则运算的除号一样,这样对于这样的表达式 8/1/3,就有两种解释 (8/1)/3 其中8/1 为计算的中间结果(Rational 对象,“/”为 Rational 字符串形式中的/),计算结果为8/3。

另外一种解释为 8/(1/3)其中1/3为输入时的除号。 为避免这种歧义,我们将 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
  ...
 }

object Rational  extends {val op="\\"} with BinaryOp

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(0, 1)
      case Rational(expr1, expr2) =>   new Rational(expr1.trim toInt, expr2.trim toInt)
      case _ => new Rational(str.trim toInt, 1)

    }
} 

我们有了 calculate 函数之后,就可以根据数字的全排列,和可能的表达式模板,设计出 24 游戏的穷举算法:

def cal24(input:List[Int])={
    var found = false
    for (template <- templates; list <- input.permutations ) {
      try {
        val (expression, tp, result) = calculate(template, list)
        if (result.numer == 24 && result.denom == 1) {
          println(input + ":" + tp + ":" + expression)
          found = true
        }
      } catch {
        case e:Throwable=>
      }
    }
    if (!found) {
      println(input+":"+"no result")
    }
}

这个算法列出所有可能的算法,比如:

scala> cal24(List(5,5,5,1))
List(5, 5, 5, 1):(N-N/N)*N:(5-1/5)*5

scala> cal24(List(3,3,8,8))
List(3, 3, 8, 8):N/(N-N/N):8/(3-8/3)

scala> cal24(List(5,6,7,8))
List(5, 6, 7, 8):(N-(N-N))*N:(5-(8-7))*6
List(5, 6, 7, 8):(N-(N-N))*N:(7-(8-5))*6
List(5, 6, 7, 8):N*N/(N-N):6*8/(7-5)
List(5, 6, 7, 8):N*N/(N-N):8*6/(7-5)
List(5, 6, 7, 8):(N+N)*(N-N):(5+7)*(8-6)
List(5, 6, 7, 8):(N+N)*(N-N):(7+5)*(8-6)
List(5, 6, 7, 8):(N-N-N)*N:(5-8-7)*6
List(5, 6, 7, 8):(N-N-N)*N:(7-8-5)*6
List(5, 6, 7, 8):(N+N-N)*N:(5+7-8)*6
List(5, 6, 7, 8):(N+N-N)*N:(7+5-8)*6

对于5,6,7,8 由于加法和乘法的交互律,某些算法是等价的,我们可以根据使用的模板是否相同去掉这些等价的算法。

如果只需要计算一种算法,可以为 for 表达式加上条件:

def cal24once(input:List[Int])={
    var found = false
    for (template <- templates; list <- input.permutations if(!found)) {
      try {
        val (expression, tp, result) = calculate(template, list)
        if (result.numer == 24 && result.denom == 1) {
          println(input + ":" + tp + ":" + expression)
          found = true
        }
      } catch {
        case e:Throwable=>
      }
    }
    if (!found) {
      println(input+":"+"no result")
    }
  }

测试如下:

scala> cal24once(List(5,6,7,8))
List(5, 6, 7, 8):(N-(N-N))*N:(5-(8-7))*6
scala> cal24once(List(1,2,3,4))
List(1, 2, 3, 4):N*N*N*N:1*2*3*4
scala> cal24once(List(1,1,1,1))
List(1, 1, 1, 1):no result

穷举可能的表达式

详细的算法说明可以参考 24 点算法之我见,简单的穷举可以把+,-,×,/和()和四个数进行全排列,但这样会出现很多无效的表达式,因此我们这里参考“24 点算法之我见”的算法,对表达式做些分析:

“换一种思路,介绍我的 24 点的穷举法 上面的算法是对数和运算符进行穷举和搜索

我的算法是对运算式进行穷举 无论给什么样的是 4 个数,运算式总是不变的,举例来说:

N+N+N+N=24,这是一种运算式 N*N+N*N=24,这是另一种运算式 N/(N-N/N)=24,这又是另一种运算式

下面这个例子: N+N-(N-N)=24 N+N-N+N=24

上面虽然是两种不同的运算式,但本质是同一种运算式(肯定同时成立或同时不成立),穷举的时候只要穷举其中一个就行了

再看下面这个例子 N/(N+N+N)=24 虽然是一个运算式,但是这个运算式是不可能成立的,也就是无解运算式,穷举的时候是不需要穷举该运算式的 ” 参考该文章提供的表格,我们可以定义如下两个 List 对象(去掉无解的表达式)

所有合法的表达式的模板:

 val templates=List(
    "(N-(N+N))*N",
    "(N-(N-N))*N",
    "(N*N+N)*N",
    "(N*N+N)/N",
    "(N*N-N)*N",
    "(N*N-N)/N",
    "(N/N+N)*N",
    "(N/N-N)*N",
    "(N+N)*(N+N)",
    "(N+N)*(N-N)",
    "(N+N)*N*N",
    "(N+N)*N/N",
    "(N+N)*N+N",
    "(N+N)*N-N",
    "(N+N)/(N/N)",
    "(N+N)/N*N",
    "(N+N)/N+N",
    "(N+N*N)*N",
    "(N+N*N)/N",
    "(N+N/N)*N",
    "(N+N+N)*N",
    "(N+N+N)/N",
    "(N+N-N)*N",
    "(N-N)*(N+N)",
    "(N-N)*(N-N)",
    "(N-N)*N*N",
    "(N-N)*N/N",
    "(N-N)*N+N",
    "(N-N)*N-N",
    "(N-N)/(N/N)",
    "(N-N)/N*N",
    "(N-N*N)*N",
    "(N-N/N)*N",
    "(N-N+N)*N",
    "(N-N-N)*N",
    "N-(N-N)*N",
    "N-(N-N)+N",
    "N-(N-N-N)",
    "N*(N-(N+N))",
    "N*(N-(N-N))",
    "N*(N*N+N)",
    "N*(N*N-N)",
    "N*(N/N+N)",
    "N*(N/N-N)",
    "N*(N+N)*N",
    "N*(N+N)/N",
    "N*(N+N)+N",
    "N*(N+N)-N",
    "N*(N+N*N)",
    "N*(N+N/N)",
    "N*(N+N+N)",
    "N*(N+N-N)",
    "N*(N-N)*N",
    "N*(N-N)/N",
    "N*(N-N)+N",
    "N*(N-N)-N",
    "N*(N-N*N)",
    "N*(N-N/N)",
    "N*(N-N+N)",
    "N*(N-N-N)",
    "N*N-(N+N)",
    "N*N-(N-N)",
    "N*N*(N+N)",
    "N*N*(N-N)",
    "N*N*N*N",
    "N*N*N/N",
    "N*N*N+N",
    "N*N*N-N",
    "N*N/(N*N)",
    "N*N/(N/N)",
    "N*N/(N+N)",
    "N*N/(N-N)",
    "N*N/N*N",
    "N*N/N/N",
    "N*N/N+N",
    "N*N/N-N",
    "N*N+N*N",
    "N*N+N/N",
    "N*N+N+N",
    "N*N+N-N",
    "N*N-N*N",
    "N*N-N/N",
    "N*N-N+N",
    "N*N-N-N",
    "N/((N+N)/N)",
    "N/((N-N)/N)",
    "N/(N*N)*N",
    "N/(N*N/N)",
    "N/(N/(N+N))",
    "N/(N/(N-N))",
    "N/(N/N)*N",
    "N/(N/N)/N",
    "N/(N/N*N)",
    "N/(N/N/N)",
    "N/(N/N-N)",
    "N/(N+N)*N",
    "N/(N-N)*N",
    "N/(N-N/N)",
    "N/N*(N+N)",
    "N/N*(N-N)",
    "N/N*N*N",
    "N/N*N/N",
    "N/N*N+N",
    "N/N*N-N",
    "N/N/(N/N)",
    "N/N/N*N",
    "N/N+N*N",
    "N/N+N+N",
    "N+(N+N)*N",
    "N+(N+N)/N",
    "N+(N-N)*N",
    "N+N-(N-N)",
    "N+N*(N+N)",
    "N+N*(N-N)",
    "N+N*N*N",
    "N+N*N/N",
    "N+N*N+N",
    "N+N*N-N",
    "N+N/(N/N)",
    "N+N/N*N",
    "N+N/N+N",
    "N+N+N*N",
    "N+N+N/N",
    "N+N+N+N",
    "N+N+N-N",
    "N+N-N+N",
    "N+N-N-N",
    "N-N*(N-N)",
    "N-N+N*N",
    "N-N+N+N"

  )

等价表达式的定义:

val equivalence  = List(
    "N+N-N+N,N+N+N-N",
    "N+N-(N-N),N+N-N+N,N+N+N-N",
    "N+N*(N+N),(N+N)*N+N",
    "N+N*(N-N),N+(N-N)*N",
    "N+N/N*N,N+N*N/N",
    "(N+N)/N*N,(N+N)*N/N",
    "N+N/(N/N),N+N/N*N,N+N*N/N",
    "(N+N)/(N/N),(N+N)/N*N,(N+N)*N/N",
    "N-N+N+N,N+N+N-N",
    "N-N+N*N,N+N*N-N",
    "(N-N+N)*N,(N+N-N)*N",
    "(N-(N+N))*N,(N-N-N)*N",
    "N-(N-N)+N,N-N+N+N,N+N+N-N",
    "N+N-N-N,N-N+N+N,N+N+N-N",
    "N-(N-N-N),N-N+N+N,N+N+N-N",
    "N-(N-N)*N,N+(N-N)*N",
    "(N-(N-N))*N,(N-N+N)*N,(N+N-N)*N",
    "(N-N)*N+N,N+(N-N)*N",
    "(N-N)*(N+N),(N+N)*(N-N)",
    "N-N*(N-N),N+N*(N-N),N+(N-N)*N",
    "(N-N)/N*N,(N-N)*N/N",
    "(N-N)/(N/N),(N-N)/N*N,(N-N)*N/N",
    "N*N+N+N,N+N+N*N",
    "N*(N+N)+N,N+(N+N)*N",
    "N*(N+N+N),(N+N+N)*N",
    "N*N+N-N,N-N+N*N",
    "N*(N+N)-N,(N+N)*N-N",
    "N*(N+N-N),(N+N-N)*N",
    "N*(N+N)*N,(N+N)*N*N",
    "(N*N+N)*N,(N+N*N)*N",
    "N*(N+N*N),(N+N*N)*N",
    "N*(N+N)/N,(N+N)*N/N",
    "(N*N+N)/N,(N+N*N)/N",
    "N*(N+N/N),(N+N/N)*N",
    "N*N-N+N,N-N+N*N",
    "N*(N-N)+N,N+(N-N)*N",
    "N*(N-N+N),(N+N-N)*N",
    "N*N-(N+N),N*N-N-N",
    "N*(N-(N+N)),N*(N-N-N),(N-N-N)*N",
    "N*(N-N)-N,(N-N)*N-N",
    "N*(N-N-N),(N-N-N)*N",
    "N*N-(N-N),N*N-N+N,N-N+N*N",
    "N*(N-(N-N)),N*(N-N+N),(N+N-N)*N",
    "N*(N-N)*N,(N-N)*N*N",
    "N*(N-N*N),(N-N*N)*N",
    "N*(N-N)/N,(N-M2)*N/N",
    "N*(N-N/N),(N-N/N)*N",
    "N*N*N+N,N+N*N*N",
    "N*N*(N+N),(N+N)*N*N",
    "N*(N*N+N),(N+N*N)*N",
    "N*N*(N-N),(N-N)*N*N",
    "N*(N*N-N),(N*N-N)*N",
    "N*N/N+N,N+N*N/N",
    "N*(N/N+N),(N+N/N)*N",
    "N*N/N*N,N*N*N/N",
    "N*N/(N*N),N*N/N/N",
    "N*N/(N/N),N*N/N*N,N*N*N/N",
    "N/N+N+N,N+N+N/N",
    "N/N+N*N,N*N+N/N",
    "N/(N+N)*N,N*N/(N+N)",
    "(N/N+N)*N,(N+N/N)*N",
    "N/((N+N)/N),N/(N+N)*N,N*N/(N+N)",
    "N/(N-N)*N,N*N/(N-N)",
    "N/((N-N)/N),N/(N-N)*N,N*N/(N-N)",
    "N/N*N+N,N+N*N/N",
    "N/N*(N+N),(N+N)*N/N",
    "N/N*N-N,N*N/N-N",
    "N/N*(N-N),N*(N-N)/N",
    "N/N*N*N,N*N*N/N",
    "N/(N*N)*N,N/N/N*N,N*N/N/N",
    "N/N*N/N,N*N/N/N",
    "N/(N*N/N),N/N/N*N,N*N/N/N",
    "N/(N/(N+N)),N/N*(N+N),(N+N)*N/N",
    "N/(N/(N-N)),N/N*(N-N),(N-N)*N/N",
    "N/N/N*N,N*N/N/N",
    "N/(N/N)*N,N/N*N*N,N*N*N/N",
    "N/(N/N*N),N/N*N/N,N*N/N/N",
    "N/N/(N/N),N/N/N*N,N*N/N/N",
    "N/(N/N)/N,N/N*N/N,N*N/N/N",
    "N/(N/N/N),N/N*N/N,N*N/N/N"
  ) 

通过这两个 List 对象,我们去掉等价的表达式,得出最终的合法表达式只有 73 种,大大缩小了需要穷举的表达式的数目:

val templates=List(
    "N*N-N+N",
    "(N-N)*N*N",
    "N*N+N*N",
    "(N+N)*N*N",
    "N*N*N*N",
    "(N+N*N)*N",
    "(N*N-N)*N",
    "N*N+N+N",
    "(N/N-N)*N",
    "(N-(N-N))*N",
    "N-(N-N-N)",
    "N+N-(N-N)",
    "N*(N/N-N)",
    "(N-N*N)*N",
    "N*(N-N)+N",
    "N+N+N/N",
    "(N-N)*(N-N)",
    "N+N*N/N",
    "N*N/(N-N)",
    "(N+N)*(N+N)",
    "(N-N)*N/N",
    "N+(N+N)/N",
    "N*N/(N+N)",
    "(N+N)*N/N",
    "(N*N+N)*N",
    "(N*N-N)/N",
    "(N/N+N)*N",
    "N*N/N/N",
    "N+N+N-N",
    "N-(N-N)+N",
    "N/(N-N/N)",
    "N+(N-N)*N",
    "(N+N+N)*N",
    "N+N*N-N",
    "N*N-N/N",
    "(N+N)*N-N",
    "(N+N)*(N-N)",
    "(N-N/N)*N",
    "N*(N+N)+N",
    "N*N+N/N",
    "N*N/N-N",
    "(N+N/N)*N",
    "N*N*N/N",
    "(N+N*N)/N",
    "N+N*N+N",
    "N-(N-N)*N",
    "(N-(N+N))*N",
    "N*N-N-N",
    "N+N/N+N",
    "(N-N)*N-N",
    "(N+N)/N+N",
    "N*N+N-N",
    "N/N+N+N",
    "N*N*N-N",
    "(N*N+N)/N",
    "N+N+N*N",
    "N*(N-N)/N",
    "N/N*N+N",
    "N+N*N*N",
    "N+N+N+N",
    "N*N/(N*N)",
    "N+(N+N)*N",
    "(N-N)*N+N",
    "(N+N+N)/N",
    "(N+N)*N+N",
    "N*N*N+N",
    "N*N-(N-N)",
    "N*N-(N+N)",
    "(N-N-N)*N",
    "N*N/N+N",
    "(N+N-N)*N",
    "N/(N/N-N)",
    "N*N-N*N"
  )

实现全排列

穷举法计算二十四的算法的重要一个步骤,是把数字进行全排列,比如对于一个三个数的列表 List(1,2,3),其全排列如下:

List(1, 2, 3)
List(1, 3, 2)
List(2, 1, 3)
List(2, 3, 1)
List(3, 1, 2)
List(3, 2, 1)

解决这种问题的一个策略是采用“分而治之”的方法,首先把问题分解成小的问题,比如N个数的全排列可以分解成 N-1 的全排列再加 1 个数的排列,然后对每个小的问题给出解决方案。

由此前面可以写出如下的一个递归算法:

def permutations(l:List[Int]):List[List[Int]] = {
    l match {
      case Nil => List(List())
      case (head::tail) =>
        for(p0 <- permutations(tail);i<-0 to (p0 length);(xs,ys)=p0 splitAt i)  yield xs:::List(head):::ys
    }
  }

空列表的全排列为空,N 个数的全排列为 N-1 个数的全排列和 1 个数的全排列,对于每个 N-1 的排列,依次插入剩下的一个数,就构成了一个新的全排列。 测试如下:

scala> permutations(List(1,2,3)).mkString("\n")
res3: String =
List(1, 2, 3)
List(2, 1, 3)
List(2, 3, 1)
List(1, 3, 2)
List(3, 1, 2)
List(3, 2, 1)

再看看 1,1,2 的情况:

scala> permutations(List(1,1,3)).mkString("\n")
res4: String =
List(1, 1, 3)
List(1, 1, 3)
List(1, 3, 1)
List(1, 3, 1)
List(3, 1, 1)
List(3, 1, 1)

有重复的排列,我们可以直接借助于 List 的 distinct 方法过滤掉重复的值。

scala> permutations(List(1,1,3)).distinct.mkString("\n")
res5: String =
List(1, 1, 3)
List(1, 3, 1)
List(3, 1, 1)

这样全排列的算法就成了,其实 List 自身已经提供了 permutations 方法,不需要自行实现:-)

scala> List(1,2,3,4).permutations.mkString("\n")
res6: String =
List(1, 2, 3, 4)
List(1, 2, 4, 3)
List(1, 3, 2, 4)
List(1, 3, 4, 2)
List(1, 4, 2, 3)
List(1, 4, 3, 2)
List(2, 1, 3, 4)
List(2, 1, 4, 3)
List(2, 3, 1, 4)
List(2, 3, 4, 1)
List(2, 4, 1, 3)
List(2, 4, 3, 1)
List(3, 1, 2, 4)
List(3, 1, 4, 2)
List(3, 2, 1, 4)
List(3, 2, 4, 1)
List(3, 4, 1, 2)                                                              
List(3, 4, 2, 1)
List(4, 1, 2, 3)
List(4, 1, 3, 2)
List(4, 2, 1, 3)
List(4, 2, 3, 1)
List(4, 3, 1, 2)
List(4, 3, 2, 1)

List 简介

我们在前面介绍 Scala 编程时对 Scala 库提供的函数库没有介绍,Scala 支持的集合类型比如 List,Set,Map,Array 功能非常强大,如果你之前用过 C# 的 LINQ,基本上 LINQ 支持的功能 Scala 的集合类型都支持,很多以前需要循环来实现的,在 Scala 中可能只需要一行就可以实现,有时间我们专门来介绍下 Scala 支持的集合类型。

本篇对 Scala 中最常用的 List 类型做个概要的介绍。

List 和 Array 非常相像,但有两个重要的不同点,List 是不可变的(immutable),也就是 List 创建后,不可以修改。List 具有递归的结构(也就是链接表结构)而数组不是。

和数组一样,List 中的元素必须是同类型的。下面我们来看看如何构造一个 List 对象:

scala> val fruit = List("apple","oranges","pears")
fruit: List[String] = List(apple, oranges, pears)
scala> val empty=List()
empty: List[Nothing] = List() 
scala> val fruit = "apple" :: "orange" :: "pears"  :: Nil
fruit: List[String] = List(apple, orange, pears)
scala> val empty = Nil
empty: scala.collection.immutable.Nil.type = List()
scala> val nums = 1 :: 2 :: 3 :: 4 :: Nil
nums: List[Int] = List(1, 2, 3, 4)

List 可以通过构造函数创建,也可以通过:: 连接每个元素,::是右结合的,在通过::构造列表时,需要在最右边使用 Nil,这样编译器才知道构造一个 List,因为字符串 String 本身不支持::操作。

基本操作

head 取 List 的首元素 tail 取除首元素之外的 List 的其它元素 isEmpty 判断 List 是否为空


scala> empty.isEmpty
res0: Boolean = true
scala> fruit.head
res1: String = apple
scala> fruit.tail
res2: List[String] = List(orange, pears)

列表模式匹配

可以使用模式对多个元素进行赋值

scala> val List(a,b,c)=fruit
a: String = apple
b: String = orange
c: String = pears
scala> val a::b::c = fruit
a: String = apple
b: String = orange
c: List[String] = List(pears)

合并两个 List

合并两个 List 可以使用 :::操作符,这个操作符也是右连接的:

scala> List(1,2) ::: List (3,4,5)
res3: List[Int] = List(1, 2, 3, 4, 5)
scala> List() ::: List (1,2,3)
res4: List[Int] = List(1, 2, 3)

反向 List

使用 reverse 可以逆转 List 中元素的顺序:

scala> List(1,2,3,4,5,6).reverse
res6: List[Int] = List(6, 5, 4, 3, 2, 1)

drop,take,splitAt

drop,take 操作为 head,tail (和 init)的一般形式, xs take n 返回 List 的前 n 个元素,xs drop n返回除前 n 个元素的 List 余下的元素,如果 n 比 List 全长要大,则返回空 List。 splitAt 可以把一个List在指定位置分成两个 List xs spliatAt n 和 (xs taken n, xs drop n)等价

scala> val abcde =List ('a','b','c','d','e')
abcde: List[Char] = List(a, b, c, d, e)
scala> abcde take 2
res8: List[Char] = List(a, b)
scala> abcde drop 2
res9: List[Char] = List(c, d, e)
scala> abcde splitAt 2
res10: (List[Char], List[Char]) = (List(a, b),List(c, d, e))

flatten 展开嵌套 List

flatten 可以展开嵌套的 List 为一个单个 List,比如:

scala> List(List(1,2),List(3,4),List(5,6)).flatten
res11: List[Int] = List(1, 2, 3, 4, 5, 6)

zip 和 unzipList

zip 和从两个 List 分别去对应的元素,组成二元组,构成新的 List

scala> abcde.indices zip abcde
res12: scala.collection.immutable.IndexedSeq[(Int, Char)] = Vector((0,a), (1,b), (2,c), (3,d), (4,e))
scala> abcde zip List(1,2,3)
res13: List[(Char, Int)] = List((a,1), (b,2), (c,3))

unzip 执行相反的操作。

scala> val zipped=abcde.zipWithIndex
zipped: List[(Char, Int)] = List((a,0), (b,1), (c,2), (d,3), (e,4))
scala> zipped.unzip
res14: (List[Char], List[Int]) = (List(a, b, c, d, e),List(0, 1, 2, 3, 4))

显示列表 toString 和 mkString

toString 显示 List 的正规字符表示。 mkString 可以格式化 List 显示

scala> abcde.toString
res15: String = List(a, b, c, d, e)
scala> abcde.mkString("[",",","]")
res16: String = [a,b,c,d,e]
scala> abcde mkString ""
res17: String = abcde
scala> abcde mkString("\n")
res19: String =
a
b
c
d
e

对列表使用高阶函数

map 可以对 List 的每个元素逐个应用某个函数,转换成另外一个列表

scala> List(1,2,3) map (_ + 1)
res20: List[Int] = List(2, 3, 4)
scala> val words= List("the","quick","brown","fox")
words: List[String] = List(the, quick, brown, fox)
scala> words map (_.length)
res21: List[Int] = List(3, 5, 5, 3)

flatMap 和 map 类似,但它使用的函数需要返回一个列表,然后它把这个函数用于到 List 的每个元素,然后合并列表

scala> words map (_.toList)
res22: List[List[Char]] = List(List(t, h, e), List(q, u, i, c, k), List(b, r, o, w, n), List(f, o, x))
scala> (words map (_.toList)).flatten
res23: List[Char] = List(t, h, e, q, u, i, c, k, b, r, o, w, n, f, o, x)
scala> words flatMap (_.toList)
res24: List[Char] = List(t, h, e, q, u, i, c, k, b, r, o, w, n, f, o, x)

过滤列表

filter, partition,find, takeWhile, dropWhile ,span 可以用来根据条件过滤列表的元素,构成新列表

scala> List(1,2,3,4,5) filter (_ % 2==0)
res25: List[Int] = List(2, 4)
scala>  List(1,2,3,4,5) partition (_ % 2==0)
res27: (List[Int], List[Int]) = (List(2, 4),List(1, 3, 5))

算法之一

前面我们定义了表达式的算法,通常的 24 点常用的算法,尽管都是穷举,也有几个常用的不同的算法,其中之一有人称为动态规划算法:

把多元运算转化为两元运算,先从四个数中取出两个数进行运算,然后把运算结果和第三个数进行运算, 再把结果与第四个数进行运算。在求表达式的过程中,最难处理的就是对括号的处理,而这种思路很好的避免了对括号的处理。基于这种思路的一种算法: 因为能使用的 4 种运算符 – * / 都是2元运算符,所以本文中只考虑 2 元运算符。2元运算符接收两个参数,输出计算结果,输出的结果参与后续的计算。

由上所述,构造所有可能的表达式的算法如下:

(1) 将 4 个整数放入数组中

(2) 在数组中取两个数字的排列,共有 P(4,2) 种排列。对每一个排列,

(2.1) 对 – * / 每一个运算符,

(2.1.1) 根据此排列的两个数字和运算符,计算结果

(2.1.2) 改表数组:将此排列的两个数字从数组中去除掉,将 2.1.1 计算的结果放入数组中

(2.1.3) 对新的数组,重复步骤 2

(2.1.4) 恢复数组:将此排列的两个数字加入数组中,将 2.1.1 计算的结果从数组中去除掉

可见这是一个递归过程。步骤 2 就是递归函数。当数组中只剩下一个数字的时候,这就是表达式的最终结果,此时递归结束。

在程序中,一定要注意递归的现场保护和恢复,也就是递归调用之前与之后,现场状态应该保持一致。

在上述算法中,递归现场就是指数组,2.1.2 改变数组以进行下一层递归调用,2.1.3 则恢复数组,以确保当前递归调用获得下一个正确的排列。

括号 () 的作用只是改变运算符的优先级,也就是运算符的计算顺序。所以在以上算法中,无需考虑括号。括号只是在输出时需加以考虑。

使用这个算法的一个 Scala 实现如下:

def solve(vs: List[Int],n: Int = 24){
    def isZero(d: Double) = Math.abs(d) < 0.00001 //解析为恰当的中缀表达式 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)

这个算法的来源于网上,很简短的代码就实现了算 24 的算法,Scala 还是比较强大的:-)

不过我们这里还是采用另外一种方法,来介绍Scala编程的多个方面。

这个算法就是列出 4 个数字加减乘除的各种可能性。我们可以将表达式分成以下几种:首先我们将 4 个数设为 a,b,c,d,,将其排序列出四个数的所有排序序列组合(共有 24 种组合)。再进行符号的排列表达式,其中算术符号有+,—,*,/,(,)。其中有效的表达式有 a*(b-c/b),a*b-c*d,等等。列出所有有效的表达式。其中我们用枚举类型将符号定义成数字常量。

表达式计算(三)

在上篇中我们实现了整数的四则运算的算法,这里我们回到之前提到的 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。

表达式计算(二)

在上篇 Scala 二十四点游戏(1):表达式计算(一)我们使用 Scala 实现了四则运算,但还不支持带括号的情况,本篇我们接着看看如处理带括号的情况, 比如表达式 1+2+(3*5)+3+3*(3+(3+5))

括号的情况稍微有些复杂,一层括号比较简单,对于嵌套括号的情况,需要匹配同一层次的括号,好在我们只需要匹配最外面一层括号,其它的可以通过递归函数的方法依次匹配。这里我们定义一个方法,通过栈结构来匹配最外一层括号:

import scala.collection.mutable.Stack  
def matchBracket(str:String):Option[(Int,Int)] ={
    val left = str.indexOf('(')
    if(left >=0) {
      val stack = Stack[Char]()
      val remaining = str substring (left+1)
      var index=0
      var right=0
      for(c <-remaining if right==0){ index=index + 1 c match{ case '(' => stack push c
          case ')'  => if (stack isEmpty)  right= left+index else stack pop
          case _ =>
        }
      }
      Some(left,right)
    }else  None
  }

这个方法匹配最外面一层括号,并给出他们在字符中的位置,我们做个简单的测试。

scala> val str="1+2+(3*5)+3+3*(3+(3+5))" 
str: String = 1+2+(3*5)+3+3*(3+(3+5))
scala> val Some((left,right))=matchBracket(str)
left: Int = 4
right: Int = 8
scala> str.charAt(left)
res0: Char = (

这个函数成功找到匹配的括号。

对于每个包含括号的表达式,可以有如下形式:

part1 ( expr ) part2

因此我们可以实现如下的Bracket 对象来匹配括号表达式:

object Bracket{
  def matchBracket(str:String):Option[(Int,Int)] ={
    val left = str.indexOf('(')
    if(left >=0) {
      val stack = Stack[Char]()
      val remaining = str substring (left+1)
      var index=0
      var right=0
      for(c <-remaining if right==0){ index=index + 1 c match{ case '(' => stack push c
          case ')'  => if (stack isEmpty)  right= left+index else stack pop
          case _ =>
        }
      }
      Some(left,right)
    }else  None
  }

  def apply(part1:String,expr:String,part2:String) =part1+ "(" + expr + ")"+ part2
  def unapply(str:String) :Option[(String,String,String)] ={
     Bracket.matchBracket(str) match{
      case Some((left:Int,right:Int)) =>{
        val part1 = if (left == 0) "" else str substring(0, left )
        val expr = str substring(left + 1, right)
        val part2 = if (right == (str length)-1) "" else str substring (right+1)
        Some(part1, expr, part2)
      }
      case _ => None
    }
  }
}

修改之前的eval 函数,首先匹配括号表达式:

def eval(str:String):Int = 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 _ => str toInt
 }

做些简单的测试:

scala> eval ("1+(3+(4+2)+3+(3+5)+3)+5")
res1: Int = 29
scala> eval ("1+2+(3*5)+3+3*(3+(3+5))")
res2: Int = 54

这样整数的四则运算的算法基本实现了,当然还不是很完善,比如负数,错误处理等,不过这些对我们解决 24 问题不是很重要,我们暂时忽略这些问题。