24点的三种算法思路及代码(3)

先公布一下第一篇文章中提出的问题的答案：
1,5,5,5：(5-1/5)*5=24
3,3,8,8：8/(3-8/3)=24

此文所贴代码均为面向过程的C(++)代码，在VC6下编译通过。

第二种思路：

还是尽量避免处理括号，实在是很麻烦。有一种没有括号的表达式——逆波兰表达式（后缀表达式），逆波兰表达式严格地按照从左至右的顺序执行。因此，只需把所有的数字的排列组合与所有的符号的排列组合再进行排列组合即可遍历所有可能的表达式。在输出结果时，只需把逆波兰表达式按照规则还原成正常的表达式即可。

说明：’-‘和’/’有两种情况，’a-b’用’a-b’表示,’b-a’用’a|b’表示，’a/b’用’a/b’表示，’b/a’用’a\b’表示，’\’是转义字符，要用’\\’表示。

程序代码如下：

/********************************/
/* fdream.net */
/* Author:Fdream */
/* 引用此算法请保留此信息 */
/********************************/

#include
#include
#include

using namespace std;

const double PE=1E-6;
const int RESULT = 24;

//F((A,B),C),D)
double num12[6]={0}; //计算第1个数和第2个数
string exp12[6]; //两个数的表达式
double num123[6]={0}; //计算第3个数和上面2数运算后的结果
string exp123[6]; //上述运算的表达式
double numRes1[6]={0}; //计算第4个数和上面3数运算后的结果
string expRes1[6]; //上述运算的表达式

//F((A,B),(C,D))
double num34[6]={0}; //计算第3个数和第4个数
string exp34[6]; //上述运算的表达式
double numRes2[6]={0}; //计算第1、2数和第3、4个数运算后的结果
string expRes2[6]; //上述运算的表达式

//计算两个数，保存结果与表达式
void Caculate(double a,double b,double numRes[],string expRes[],string expa,string expb){
numRes[0]=a+b;
expRes[0]='(‘+expa+’+’+expb+’)’;
numRes[1]=a-b;
expRes[1]='(‘+expa+’-‘+expb+’)’;
numRes[2]=b-a;
expRes[2]='(‘+expb+’-‘+expa+’)’;
numRes[3]=a*b;
expRes[3]='(‘+expa+’*’+expb+’)’;
if(b){
numRes[4]=a/b;
expRes[4]='(‘+expa+’/’+expb+’)’;
}
if(a){
numRes[5]=b/a;
expRes[5]='(‘+expb+’/’+expa+’)’;
}
}

void main(void){
int com[24][4]={0};
int number[4]={0};
int i,j,m,n,k=0,comNum=0,s=0,flag=1;

//输入数据
for(i=0;i<4;i++)
cin >> number[i];

//生成数据的排列组合
for(i=0;i<4;i++){
for(j=0;j<4;j++){
if(j!=i){
for(m=0;m<4;m++){
if(m!=i&&m!=j){
for(n=0;n<4;n++)
if(n!=i&&n!=j&&n!=m){
flag=1;
for(s=0;s if(com[s][0]==number[i]&&com[s][1]==number[j]&&com[s][2]==number[m]&&com[s][3]==number[n]){
flag=0;
}
}
if(flag){
com[k][0]=number[i];
com[k][1]=number[j];
com[k][2]=number[m];
com[k][3]=number[n];
k++;
comNum++;
}
}
}
}
}
}
}

for(i=0;i char buffer[20];
string expa,expb;
itoa(com[i][0],buffer,10);
expa=buffer;
itoa(com[i][1],buffer,10);
expb=buffer;

Caculate(com[i][0],com[i][1],num12,exp12,expa,expb);

//F((A,B),C),D)
for(j=0;j<6;j++){
itoa(com[i][2],buffer,10);
expb=buffer;
Caculate(num12[j],com[i][2],num123,exp123,exp12[j],expb);
for(m=0;m<6;m++){
itoa(com[i][3],buffer,10);
expb=buffer;
Caculate(num123[m],com[i][3],numRes1,expRes1,exp123[m],expb);
for(k=0;k<6;k++){
if(fabs(numRes1[k]-RESULT) cout << expRes1[k] << endl;
}}
}

//F((A,B),(C,D))
itoa(com[i][2],buffer,10);
expa=buffer;
itoa(com[i][3],buffer,10);
expb=buffer;
Caculate(com[i][2],com[i][3],num34,exp34,expa,expb);
for(m=0;m<6;m++){
for(n=0;n<6;n++){
Caculate(num12[m],num34[n],numRes2,expRes2,exp12[m],exp34[n]);
for(k=0;k<6;k++)
if(fabs(numRes2[k]-RESULT) cout << expRes2[k] << endl;
}
}
}
}

系列文章：
24点的三种算法思路及代码(1)
24点的三种算法思路及代码(2)
24点的三种算法思路及代码(3)