爱华网首先可以列出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 PolishNotation)来表示，例如前面那个算术表达式的逆波兰式形式为12+3+4*。这样就简单明了了吧？！这个步骤于是可以这样来做，对于确定的整数和运算符，找出所有可能的逆波兰式进行运算，如果结果为24，则将这个逆波兰式转为中缀形式进行输出(之所以这样做是中缀表达式更符合人们的阅读习惯，当然你也可以略过这一步)。现在思路已经很清晰了，那么剩下的工作就是如何实现的问题了。
解析逆波兰式的标准算法是利用stack来做，加减乘除都是二元运算符，也就是说运算前stack里的元素必须为2以上才合法，于是这个找出所有逆波兰式的问题就变成了一个附加条件下求所有可能的出栈序列。解析的递归函数可以这样来构建：结束的条件是所有的运算符都已经进行运算了，这时候所有的整数都已经运算过,stack里只有一个top位置的值，其便是最后的计算结果，可以直接将其和24进行比较；进行递归的路径有两条，一是检查stack里的元素是否大于或等于2个，如果是，则将它们pop出来，取出当前的运算符进行运算，把结果push回stack，然后递归，另一条是将当前的整数push进stack，直接递归。这样构建下的搜索树可以覆盖所有可能的出栈序列，也就是我们要的逆波兰式。
(代码由VC++2005/2008编译通过)
// P24.cpp : Defines the entry pointfor the console application.//
#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 OPSSIZE4
#define EXPRESULT24
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(intargc, _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;
}
