Scala二十四点游戏(7):穷举可能的表达式

详细的算法说明可以参考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"
  )