24点游戏 程序(三)
增加了部分去重复的功能，以及后缀转中缀显示。
代码语言：javascript代码运行次数：0运行复制#include <iostream>
#include <stack>
#include <algorithm>
#include <string>
#include <cmath>
#include <time.h>
using namespace std;
struct TOperData
{
int operType;
double data;
};
//检查计算的参数是否合法，也可以用于过滤一些重复的表达式
bool checkjisuan(double a, double b, int op)
{
if (op == '/' && b < 1e-6 && b > -1e-6)
return false;
if (op == '-' && b < 1e-6 && b > -1e-6)
return false;
if (op == '/' && (fabs(b-1.0f) < 1e-6 || fabs(b+1.0f) < 1e-6))
return false;
if (op == '+' || op == '*')
return a <= b;
return true;
}
//消除重复
bool checkOp(TOperData computeData[])
{
for (int i = 0; i < 6; i++)
{
int type1 = computeData[i].operType;
int type2 = computeData[i+1].operType;
if (type1 == '-' && (type2 == '+' || type2 == '-'))
{
return false;
}
else if (type1 == '/' && (type2 == '*' || type2 == '/'))
{
return false;
}
}
return true;
}
//求值
double jisuan(double a, double b, int op)
{
switch(op)
{
case '+':
return a + b;
case '-':
return a - b;
case '*':
return a * b;
case '/':
return a / b;
default:
return -1;
}
}
//计算表达式的值
double process(TOperData data[])
{
int len = 7;
stack<TOperData> suffix;
for (int i = 0; i < len; i++)
{
if (data[i].operType == 0)
{
suffix.push(data[i]);
}
else if (data[i].operType > 0)
{
if (suffix.empty())
return false;
if (suffix.top().operType == 0)
{
double a = suffix.top().data;
suffix.pop();
if (!suffix.empty() && suffix.top().operType == 0)
{
double b = suffix.top().data;
suffix.pop();
if (!checkjisuan(b,a,data[i].operType)) return -1;
double c = jisuan(b,a,data[i].operType);
TOperData opdata;
opdata.operType = 0;
opdata.data = c;
suffix.push(opdata);
}
else
{
return -1;
}
}
else
{
return -1;
}
}
}
if (suffix.empty()) return -1;
if (suffix.top().operType == 0)
{
double r = suffix.top().data;
suffix.pop();
if (suffix.empty()) return r;
}
return -1;
}
int op(char x)
{
if (x == '+')return 1;
else if (x == '-')return 1;
else if (x == '*')return 2;
else if (x == '/')return 2;
else return 0;
}
//后缀转中缀
string posttomid(TOperData data[])
{
stack<char> a, b;
//后缀转回中缀
stack<TOperData> ope;
stack<string> opn;
string tmp1, tmp2;
for (int i = 0; i < 7; i++)
{
if (data[i].operType == 0)
{
char buffer [33];
itoa (data[i].data,buffer,10);
string tt = "";
tt += buffer;
opn.push(tt);
ope.push(data[i]);
}
else
{
if (op(ope.top().operType) != 0 && (op(data[i].operType) > op(ope.top().operType) || (op(data[i].operType) == op(ope.top().operType) && (data[i].operType == '-' || data[i].operType == '/'))))
{
tmp2 = "(";
tmp2 += opn.top();
tmp2 += ")";
}
else
{
tmp2 = opn.top();
}
opn.pop();
ope.pop();
if (op(ope.top().operType) != 0 && op(data[i].operType) > op(ope.top().operType))
{
tmp1 = "(";
tmp1 += opn.top();
tmp1 += ")";
}
else
{
tmp1 = opn.top();
}
ope.pop();
opn.pop();
tmp1 += data[i].operType;
tmp1 += tmp2;
opn.push(tmp1);
ope.push(data[i]);
}
}
string result = opn.top();
cout<<result<< endl;
return result;
}
//打印成功的结果
void printResult(TOperData computeData[])
{
for (int i = 0; i < 7; i++)
{
if (computeData[i].operType == 0)
{
cout<<computeData[i].data<<" ";
}
else
{
cout<<(char)computeData[i].operType<<" ";
}
}
cout<<endl;
}
int start(double data[])
{
int shunxu[][7] = { 1,1,1,1,2,2,2 ,
1,1,1,2,1,2,2 ,
1,1,1,2,2,1,2 ,
1,1,2,1,1,2,2 ,
1,1,2,1,2,1,2
};
int operAll[] = {'+','-','*','/'};
TOperData computeData[7];
double copydata[4];
copydata[0] = data[0];
copydata[1] = data[1];
copydata[2] = data[2];
copydata[3] = data[3];
//5个后缀表达式遍历
for (int m = 0; m < 5; m++)
{
do
{
int oper[3];
for(int n = 0; n < 4; n++)
{
oper[0] = operAll[n];
for(int nn = 0; nn < 4; nn++)
{
oper[1] = operAll[nn];
for(int nnn = 0; nnn < 4; nnn++)
{
oper[2] = operAll[nnn];
int j = 0;
int k = 0;
for (int i = 0; i < 7; i++)
{
if (shunxu[m][i] == 1)
{
computeData[i].operType = 0;
computeData[i].data = data[j++];
}
else if (shunxu[m][i] == 2)
{
computeData[i].operType = oper[k++];
}
}
if (!checkOp(computeData)) continue;
double r = process(computeData);
if (r-24 > -1e-6 && r-24 < 1e-6)
{
cout<<copydata[0]<<" "<<copydata[1]<<" "<<copydata[2]<<" "<<copydata[3]<<",";
//printResult(computeData);
posttomid(computeData);
return 1;//如果只要求一个结果，这个地方就可以返回了
}
}
}
}
}
while ( next_permutation (data,data+4) );
}
return 0;
}
int main(void)
{
long beginTime =clock();//获得开始时间，单位为毫秒
double data[4];
for (int i = 1; i< 14; i++)
{
data[0] = i;
for (int ii = i; ii< 14; ii++)
{
data[1] = ii;
for (int iii = ii; iii< 14; iii++)
{
data[2] = iii;
for (int iiii = iii; iiii< 14; iiii++)
{
data[3] = iiii;
double copydata[4];
copydata[0] = data[0];
copydata[1] = data[1];
copydata[2] = data[2];
copydata[3] = data[3];
start(copydata);
}
}
}
}
long endTime=clock();//获得结束时间
cout<<"time:"<<endTime-beginTime<<endl;
return 0;
}部分结果：
1 1 1 8,(1+1+1)*8 1 1 1 11,(1+1)*(1+11) 1 1 1 12,1*(1+1)*12 1 1 1 13,(1+1)*(13-1) 1 1 2 6,2*(1+1)*6 1 1 2 7,(1+2)*(1+7) 1 1 2 8,1*(1+2)*8 1 1 2 9,(1+2)*(9-1) 1 1 2 10,2*(1+1+10)
。。。
大概6s取得单一结果，一共1362个解。
取得全部结果需要14s。其实还是有很多重复。离。需要更细化的过滤。
这部分暂时不做了。有空还是想做一个android的24点小游戏。
发布评论