二十四點撲克牌游戲大概所有人都玩過，規則非常簡單，隨機抽出四張牌，由1到9中的數字組成(當然也可以擴展到任意整數)，然後利用加減乘除以及括號組成一個算術表達式，計算這個表達式的結果是否能夠為24(或任意整數)。看到這個題的第一反應就是利用窮舉法來做，也就是建立一個搜索樹，把所有的可能枚舉出來，然後檢查每種可能是否結果可以為24。基於這種思想，我們可以把問題分成三個步驟：
首先可以列出4個整數的所有排列，也就是求集合中元素的所有排列的問題，眼熟了吧？相信很多人都看過這個問題，一般的方式是用函數的遞歸來實現：如果用數組A[4]來保存這4個整數，則第0個位置的可能為4種，第1個位置的可能為3種(因為在前面已經確定1個元素),第2個位置的可能為2種,第3個位置的可能為1種,這樣所有的可能恰好為P(4,4)=24。當然對於有重復元素的情況,比如{1,5,5,5}的全排列數為4,我們需要在遞歸函數中去掉重復，以減少不必要的計算。
其次我們要確定算術表達式中4個整數之間的3個運算符,運算符的確定和前面確定整數的方式類似,只不過我們是從4個運算符中選三次來確定,所以第1個運算符的可能是4種,第2個運算符的可能也是4種,第3個也是如此(因為每一次都可以選擇4個運算符),根據算法原則，所有的可能為4*4*4=64種。如果所有的運算符的優先級都是一樣的話，則這個問題也就到此便可以得出結果了，所有的可能是24*64=1536種。是不是很easy? OK,我們繼續分析。
第三步我們來將運算符的優先級以及可能的括號加進去。優先級？括號？這兩個東西比較麻煩，因為每個整數的前後都可能出現括號，括號中的內容具有高優先級；而運算符中的乘除的優先級高於加減，就算它們出現在後邊也要先進行運算，怎麼辦呢？讓我們來借鑒一下編譯原理中的思想：普通的的算術表達式是中綴表達式，比如((1+2)+3)*4，要去掉這兩個麻煩的東西，最好的途徑是采用後綴表達式(逆波蘭式, Reverse Polish Notation)來表示，例如前面那個算術表達式的逆波蘭式形式為12+3+4*。這樣就簡單明了了吧？！這個步驟於是可以這樣來做，對於確定的整數和運算符，找出所有可能的逆波蘭式進行運算，如果結果為24，則將這個逆波蘭式轉為中綴形式進行輸出(之所以這樣做是中綴表達式更符合人們的閱讀習慣，當然你也可以略過這一步)。現在思路已經很清晰了，那麼剩下的工作就是如何實現的問題了。
解析逆波蘭式的標准算法是利用stack來做，加減乘除都是二元運算符，也就是說運算前stack裡的元素必須為2以上才合法，於是這個找出所有逆波蘭式的問題就變成了一個附加條件下求所有可能的出棧序列。解析的遞歸函數可以這樣來構建：結束的條件是所有的運算符都已經進行運算了，這時候所有的整數都已經運算過,stack裡只有一個top位置的值，其便是最後的計算結果，可以直接將其和24進行比較；進行遞歸的路徑有兩條，一是檢查stack裡的元素是否大於或等於2個，如果是，則將它們pop出來，取出當前的運算符進行運算，把結果push回stack，然後遞歸，另一條是將當前的整數push進stack，直接遞歸。這樣構建下的搜索樹可以覆蓋所有可能的出棧序列，也就是我們要的逆波蘭式。
(代碼由VC++2005/2008編譯通過)
#include "stdafx.h"
#include <assert.h>
#include <iostream>
#include <vector>
#include <string>
#include <utility>
#include <stack>
#include <queue>
#include <algorithm>
#define double_equal(a, b) ((a-b<0.00001) && (b-a)<0.00001)
#define OPSSIZE 4
#define EXPRESULT 24
std::vector<std::string> outputlist;
char operators[OPSSIZE] = {'+','-','*','/'};
void antipolish(std::stack<double>& s, std::queue<int>& q, std::vector<int>& nums, std::vector<char>& ops)
{
if(ops.size() == 0 )
{
assert(nums.size()==0 && s.size()==1);
if(double_equal(s.top(), EXPRESULT))
{
std::string str;
while(!q.empty())
{
str += q.front();
q.pop();
}
outputlist.push_back(str);
}
return;
}
std::stack<double> temps = s;
std::queue<int> tempq = q;
std::vector<int> tempnums = nums;
std::vector<char> tempops = ops;
if(s.size() >= 2)
{
double operand2 = s.top();
s.pop();
double operand1 = s.top();
s.pop();
switch(ops.front())
{
case '+':
operand1 += operand2;
break;
case '-':
operand1 -= operand2;
break;
case '*':
operand1 *= operand2;
break;
case '/':
if(!double_equal(operand2, 0))
operand1 /= operand2;
else
return;
break;
default:
return;
}
s.push(operand1);
q.push(ops.front());
ops.erase(ops.begin());
antipolish(s, q, nums, ops);
s = temps;
q = tempq;
ops = tempops;
}
if(nums.size() >0)
{
s.push(nums.front());
q.push(nums.front()+0x30);
nums.erase(nums.begin());
antipolish(s, q, nums, ops);
s = temps;
q = tempq;
nums = tempnums;
}
}
void search(std::vector<int> nums, int n, std::vector<char> ops)
{
if(n == (static_cast<int>(nums.size())-1))
{
std::stack<double> s;
std::queue<int> q;
antipolish(s, q, nums, ops);
return;
}
for(int i=n; i<static_cast<int>(nums.size()); i++)
{
bool duplicated = false;
for(int k=n; k<i; k++)
if(nums[i]==nums[k])
{
duplicated = true;
break;
}
if(!duplicated)
{
std::swap(nums[n], nums[i]);
for(int j=0; j<OPSSIZE; j++)
{
ops.push_back(operators[j]);
search(nums, n+1, ops);
ops.pop_back();
}
std::swap(nums[n], nums[i]);
}
}
}
int _tmain(int argc, _TCHAR* argv[])
{
std::vector<char> str;
std::vector<int> numbers;
numbers.push_back(1);
numbers.push_back(2);
numbers.push_back(3);
numbers.push_back(4);
search(numbers, 0, str);
return 0;
}
