24点扑克牌游戏的算法实现

24点扑克牌游戏的算法实现2010-06-02 csdn博客清晨的老巢二十四点扑克牌游戏大概所有人都玩过，规则非常简单，随机抽出四张牌，由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;
}