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

二十四点扑克牌游戏或许所有人都玩过，法则很是简朴，随机抽出四张牌，由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;
}