窮舉可能的表達(dá)式

詳細(xì)的算法說(shuō)明可以參考 24 點(diǎn)算法之我見(jiàn)，簡(jiǎn)單的窮舉可以把+，-，×，/和()和四個(gè)數(shù)進(jìn)行全排列，但這樣會(huì)出現(xiàn)很多無(wú)效的表達(dá)式，因此我們這里參考“24 點(diǎn)算法之我見(jiàn)”的算法，對(duì)表達(dá)式做些分析：

“換一種思路，介紹我的 24 點(diǎn)的窮舉法 上面的算法是對(duì)數(shù)和運(yùn)算符進(jìn)行窮舉和搜索

我的算法是對(duì)運(yùn)算式進(jìn)行窮舉 無(wú)論給什么樣的是 4 個(gè)數(shù)，運(yùn)算式總是不變的，舉例來(lái)說(shuō)：

N+N+N+N=24，這是一種運(yùn)算式 N*N+N*N=24，這是另一種運(yùn)算式 N/（N-N/N）=24，這又是另一種運(yùn)算式

下面這個(gè)例子： N+N-（N-N）=24 N+N-N+N=24

上面雖然是兩種不同的運(yùn)算式，但本質(zhì)是同一種運(yùn)算式（肯定同時(shí)成立或同時(shí)不成立），窮舉的時(shí)候只要窮舉其中一個(gè)就行了

再看下面這個(gè)例子 N/(N+N+N)=24 雖然是一個(gè)運(yùn)算式，但是這個(gè)運(yùn)算式是不可能成立的，也就是無(wú)解運(yùn)算式，窮舉的時(shí)候是不需要窮舉該運(yùn)算式的 ” 參考該文章提供的表格，我們可以定義如下兩個(gè) List 對(duì)象（去掉無(wú)解的表達(dá)式）

所有合法的表達(dá)式的模板：

 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"

  )

等價(jià)表達(dá)式的定義：

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

通過(guò)這兩個(gè) List 對(duì)象，我們?nèi)サ舻葍r(jià)的表達(dá)式，得出最終的合法表達(dá)式只有 73 種，大大縮小了需要窮舉的表達(dá)式的數(shù)目：

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