扑克牌游戏2.doc

本科学生实验报告

C++课程设计

组长姓名 黄跃武 组长学号 0104024
专 业 软件工程 班级 软件105班
实验项目 扑克牌游戏问题
实验类别 综合性实验
指导教师 严军勇
开课学期 2011 至 2012 学年 第一 学期

一、 实验设计方案
实验名称：扑克牌游戏问题
实验时间： 2011-11-12——2011-11-26
实验场地： w101
软件环境： VC6.0/Windows XP
小组成员姓名与学号：黄强 0104026
1、 实验内容与目的（简单介绍实验内容，说明实验目的）
实验目的：实现扑克牌游戏：对于任意的四个1到13的整数（四张扑克牌），求能算出24的表达式；运算符有()+-*/；若无解则输出相应的信息。
实验内容：文件输入（input.txt）输出(output.txt)，输出全部结果；输入输出格式自定。
——————————————————————————————————————
2、 实验准备工作（阐述解决问题所涉及的算法思想，至少要画一个算法流程图来说明）
算法思想：
本实验采用类似于穷举法，结合堆栈来实现的。
首先是穷举法的过程，采用+、-、*、/、（、）使四个数计算成24，可以将表达式分为3种情况：
1. 无括号，组成的表达式中只有四个数和三个运算符，总共7个字符；
2. 有一个括号，组成的表达式中有四个数、三个运算符、一个括号，总共9个字符；
3. 有两个括号，组成的表达式中有四个数、三个运算符、两个括号，总共11个字符
将输入的四个数进行全排列，根据四个数字中有多少个相同数字将全排列后的组数可以分4种情况：
1. 四个数都不相同，全排列后的种数为4*3*2*1=24；
2. 四个数中有两个相同，全排列后的种数为4*3*2*1/(2*1)=12；
3. 四个数中有三个相同，全排列后的种数为4*3*2*1/(3*2*1)=4;
4. 四个数中有三个相同，全排列后的种数为4*3*2*1/(4*3*2*1)=4;
为避免全排列的中有相同的排列，首先将四个数24种全排列存放在二维数组中（sort[24][4]），此时若属于第2、3、4种情况时，sort[24][4]中有重复的排列，则利用循环语句将sort[24][4]中的排列转存至ZL_sort[24][4]（元素初值全为24），并用m计算二维数组ZL_sort[24][4]中的排列数，下次比较时将sort中的元素与ZL_sort进行比较，若sort中的这种排列与ZL_sort中的24种排列都不相同，则写入ZL_sort中，并成为第m+1个元素。
处理没有括号的情况，此时需要进行三步运算，运算符的选取方法总共有4*4*4=64种情况，用一个二维数组char_sort[64][3]存储选取的64种运算符。那么表达式的排列有m*64种，将这m*64种情况存入二维数组x[1536][8](1536表示m取最大值24时m*64=1536,8表示4个数、3个运算符、#，#在处理堆栈时应用)，且处理时满足条件则n++（n初始值为0）。
处理一个括号的情况，可以分为（a^b）^c^d、a^(b^c)^d、a^b^(c^d)、(a^b^c)^d、a^(b^c^d)五种情况，所有的排列种数为4*4*4*5种情况，显然存在许多不必要排列，例如:(a+b)+c+d、(a*b)+c-d、a+(b*c)-d……没有必要添加括号，可以当作无括号的情况处理，经过分析之后，总共有112种情况。那么表达式的排列有m*112种，将这m*112种情况存入二维数组x1[2688][10](2688表示m取最大值24时m*122=2688,10表示4个数、3个运算符、（、）、#，#在处理堆栈时应用)。因为括号分为5种情况所以处理时也须将这五种情况一一考虑，且处理时满足条件则w++（w初始值为0），w在这5种情况中连续使用。
处理两个括号时情况，此时只有(a^b)^(c^d)这种情况时括号才有意义，也不和前面的表达式重复，总共有2*2*2=8种情况。那么表达式的排列有m*8种，将这m*8种情况存入二维数组x[192][12](192表示m取最大值24时m*8=192,12表示4个数、3个运算符、2个括号、#，#在处理堆栈时应用)，且处理时满足条件则v++（v初始值为0）。
利用穷举法已经将所有的表达式给出，此时只需将表达式植入堆栈中进行运算即可。处理堆栈运算首先要建立两个栈类型，一个是整形用来存放数字，一个字符型用来存放运算符；然后创建两个空栈，在字符栈中首先压入字符’#’，以便一个表达式执行完后（表达式中最后一个字符为#和首先压入的#抵消）退出；最后进行表达式的运算，表达式的运算是出栈和入栈的操作：若读入数据为数字，则直接入操作数栈，若读入的数据是字符，则与栈中栈顶元素进行优先级比较，小于则直接入栈，等于则消去栈顶元素，大于则取出操作数栈中的栈顶元素和次栈顶元素进行运算。

算法流程图：
4个数全排列：
i,j,k,l取0-3中不同的值
将s[i].s[j].s[k].s[l]依次存入二维数组sort[m]([0].[1].[2][3])中
将sort[m][0].sort[m][1].sort[m][2].sort[m][3]与ZL_sort中0-24进行比较全部不相同
ZL_sort[n]=sort[m],m++，n++
m=24
否
结束
是

运算符间的优先关系：

表达式求值：

二、实验步骤、测试与结果分析
1、源程序的设计（在此附上源程序（cpp文件）清单）
——————————————
#include<iostream>
#include<fstream>
using namespace std;

#define STACK_INIT_SIZE 100 //栈申请分配存储空间的大小
#define STACKINCREMENT 10 //栈分配空间不足时增加存储空间

int c[4]; //输入的4个数
char s[4]; //+、-、*、/四种运算符
int sort[24][4]; //4个数的24种全排列
int ZL_sort[24][4]; //整理后4个数的全排列
char char_sort[64][3]; //无括号时运算符排列
char x[1536][8]; //无括号时表达式排列
char x1[2688][10]; //一个括号时表达式排列
char x2[192][12]; //两个括号时表达式排列
int i,j,k,l;
int m; //整理后4个数的全排列数
int n; //无括号时表达式排列数
int w; //一个括号时表达式排列数
int v; //两个括号时表达式排列数

//======================24种全排列=============================
void Sort(int h[])
{
int count=0; //整形变量计算种类的多少
for(i=0;i<4;i++)
for(j=0;j<4;j++)
for(k=0;k<4;k++)
for(l=0;l<4;l++)
if(l!=k&&l!=j&&l!=i&&k!=i&&k!=j&&i!=j)
{ //取不同的数
sort[count][0]=c[i];
sort[count][1]=c[j];
sort[count][2]=c[k];
sort[count][3]=c[l];
count++;
}
}

//==================24种排列中去掉重复的排列==================
void ZL_Sort()
{
int count1=24;
int count2=0;
int type[24];
for(i=0;i<24;i++)
type[i]=14;
for(i=0;i<24;i++)
{
for(l=0;l<24;l++)
if(i!=type[l])
for(j=i+1;j<24;j++)
if((sort[j][0]==sort[i][0])&&(sort[j][1]==sort[i][1])
&&(sort[j][2]==sort[i][2])&&(sort[j][0]==sort[i][0]))
{ //没有重复则写入数组中
for(k=0;k<4;k++) sort[j][k]=0;
count1--;
type[count1]=j;
}
}
for(i=0;i<24;i++)
if((sort[i][0]!=0)&&(sort[i][1]!=0)&&(sort[i][2]!=0)&&(sort[i][3]!=0))
{
ZL_sort[count2][0]=sort[i][0];
ZL_sort[count2][1]=sort[i][1];
ZL_sort[count2][2]=sort[i][2];
ZL_sort[count2][3]=sort[i][3];
count2++;
}
m=count2;
}

//====================无括号时的运算符排列===================
void ZF_Sort()
{
s[0]='+';
s[1]='-';
s[2]='*';
s[3]='/';
int count9=0;
for(i=0;i<4;i++)
for(j=0;j<4;j++)
for(k=0;k<4;k++)
{
char_sort[count9][0]=s[i];
char_sort[count9][1]=s[j];
char_sort[count9][2]=s[k];
count9++;
}
}

//-------------------------------------------------------------------------
//================字符栈============
struct SqStack_T
{
char *base; //栈底指针
char *top; //栈顶指针
int stacksize; //存储空间
};

//================数字栈=============
struct SqStack_N
{
int *base;
int *top;
int stacksize;
};

//==============创建字符空栈==============
int InitStack_T(SqStack_T &S)
{
S.base=(char *)malloc(STACK_INIT_SIZE*sizeof(char));
//申请分配存储空间
if(!S.base) exit(0);//申请不成功，退出
S.top=S.base; //空栈
S.stacksize=STACK_INIT_SIZE;
return 1;
}

//==============创建数字空栈===============
int InitStack_N(SqStack_N &S)
{
S.base=(int *)malloc(STACK_INIT_SIZE *sizeof(int));
if(!S.base) exit(0);
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
return 1;
}

//=============在字符栈中插入元素===============
int Push_T(SqStack_T &S,char e)
{
if(S.top-S.base>=S.stacksize)
{ //如果存储空间不足，再次申请
S.base=(char *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(char));
if(!S.base) exit(0);
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*S.top++=e; //插入的元素为新的栈顶元素
return 1;
}

//==============在数字栈中插入元素===============
int Push_N(SqStack_N &S,int e)
{
if(S.top-S.base>=S.stacksize)
{
S.base=(int *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(int));
if(!S.base) exit(0);
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*S.top++=e;
return 1;
}

//=============栈顶元素赋值给常数e==================
int Pop_T(SqStack_T &S,char &e)
{
if(S.top==S.base) return 0; //栈为空
e=*--S.top;
return 1;
}

int Pop_N(SqStack_N &S,int &e)
{
if(S.top==S.base) return 0;
e=*--S.top;
return 1;
}

//==============取栈顶元素============
char GetTop_T(SqStack_T S)
{
char e;
if(S.top==S.base) return 0; //栈为空
e=*(S.top-1);
return e;
}

int GetTop_N(SqStack_N S)
{
int e;
if(S.top==S.base) return 0;
e=*(S.top-1);
return e;
}

//===================运算符优先级===================
char OP[7][7]={'>', '>', '<', '<', '<', '>', '>',
'>', '>', '<', '<', '<', '>', '>',
'>', '>', '>', '>', '<', '>', '>',
'>', '>', '>', '>', '<', '>', '>',
'<', '<', '<', '<', '<', '=', 'E',
'>', '>', '>', '>', 'E', '>', '>',
'<', '<', '<', '<', '<', 'E', '='};
//====================对两个数进行运算=====================
int GetOperator(char Operator)
{
int r;
r=-1;
switch(Operator)
{
case '+': r=0;break;
case '-': r=1;break;
case '*': r=2;break;
case '/': r=3;break;
case '(': r=4;break;
case ')': r=5;break;
case '#': r=6;break;
}
return r;
}

//============比较两个运算符的优先级===========
char Precede(char c1, char c2)
{
int Operator1,Operator2;
Operator1=GetOperator(c1);
Operator2=GetOperator(c2);
if(Operator1<0||Operator1>6||Operator2<0||Operator2>6) exit(0);
//不是合法运算符，退出
return OP[Operator1][Operator2]; //返回两运算符的关系
}

//==============对两个数进行运算================
int Operate(int a,char theta,int b)
{
int s;
switch(theta)
{
case '+':s=a+b;break;
case '-':s=a-b;break;
case '*':s=a*b;break;
case '/':
if(b!=0) s=a/b;
else break;
}
return s;
}
//-----------------------------------------------------------------------------

//=============无括号时的组合===========
void ZL_2sort()
{
//Sort();
//ZL_Sort();
//ZF_Sort();
n=0;
for(i=0;i<m;i++)
for(j=0;j<64;j++)
{
x[n][0]=ZL_sort[i][0]+'0';
x[n][2]=ZL_sort[i][1]+'0';
x[n][4]=ZL_sort[i][2]+'0';
x[n][6]=ZL_sort[i][3]+'0';
x[n][1]=char_sort[j][0];
x[n][3]=char_sort[j][1];
x[n][5]=char_sort[j][2];
x[n][7]='#';
n++;
}
/*for(i=0;i<n;i++)
{
for(j=0;j<8;j++)
cout<<x[i][j]<<" ";
cout<<endl;
}*/
}

//===========一个括号时的组合===========
void ZL_1KSort()
{
//Sort();
//ZL_Sort();
w=0;
for(i=0;i<m;i++)
{
for(j=0;j<2;j++)
for(k=2;k<4;k++)
for(l=0;l<4;l++)
{
x1[w][0]='(';
x1[w][1]=ZL_sort[i][0]+'0';
x1[w][2]=s[j];
x1[w][3]=ZL_sort[i][1]+'0';
x1[w][4]=')';
x1[w][5]=s[k];
x1[w][6]=ZL_sort[i][2]+'0';
x1[w][7]=s[l];
x1[w][8]=ZL_sort[i][3]+'0';
x1[w][9]='#';
w++;
}
}
for(i=0;i<m;i++)
{
for(j=1;j<4;j=j+2)
for(k=0;k<2;k++)
for(l=0;l<4;l++)
{
x1[w][0]=ZL_sort[i][0]+'0';
x1[w][1]=s[j];
x1[w][2]='(';
x1[w][3]=ZL_sort[i][1]+'0';
x1[w][4]=s[k];
x1[w][5]=ZL_sort[i][2]+'0';
x1[w][6]=')';
x1[w][7]=s[l];
x1[w][8]=ZL_sort[i][3]+'0';
x1[w][9]='#';
w++;
}
}
for(i=0;i<m;i++)
{
for(j=0;j<3;j=j+2)
for(k=0;k<2;k++)
for(l=2;l<4;l++)
{
x1[w][0]=ZL_sort[i][0]+'0';
x1[w][1]=s[j];
x1[w][2]='(';
x1[w][3]=ZL_sort[i][1]+'0';
x1[w][4]=s[k];
x1[w][5]=ZL_sort[i][2]+'0';
x1[w][6]=')';
x1[w][7]=s[l];
x1[w][8]=ZL_sort[i][3]+'0';
x1[w][9]='#';
w++;
}
}
for(i=0;i<m;i++)
{
for(j=0;j<4;j++)
for(k=1;k<4;k++)
for(l=0;l<2;l++)
{
x1[w][0]=ZL_sort[i][0]+'0';
x1[w][1]=s[j];
x1[w][2]=ZL_sort[i][1]+'0';
x1[w][3]=s[k];
x1[w][4]='(';
x1[w][5]=ZL_sort[i][2]+'0';
x1[w][6]=s[l];
x1[w][7]=ZL_sort[i][3]+'0';
x1[w][8]=')';
x1[w][9]='#';
w++;
}
}
for(i=0;i<m;i++)
{
for(j=0;j<2;j++)
for(k=0;k<4;k++)
for(l=2;l<4;l++)
{
x1[w][0]='(';
x1[w][1]=ZL_sort[i][0]+'0';
x1[w][2]=s[j];
x1[w][3]=ZL_sort[i][1]+'0';
x1[w][4]=s[k];
x1[w][5]=ZL_sort[i][2]+'0';
x1[w][6]=')';
x1[w][7]=s[l];
x1[w][8]=ZL_sort[i][3]+'0';
x1[w][9]='#';
w++;
}
}
for(i=0;i<m;i++)
{
for(j=2;j<4;j++)
for(k=0;k<2;k++)
for(l=2;l<4;l++)
{
x1[w][0]='(';
x1[w][1]=ZL_sort[i][0]+'0';
x1[w][2]=s[j];
x1[w][3]=ZL_sort[i][1]+'0';
x1[w][4]=s[k];
x1[w][5]=ZL_sort[i][2]+'0';
x1[w][6]=')';
x1[w][7]=s[l];
x1[w][8]=ZL_sort[i][3]+'0';
x1[w][9]='#';
w++;
}
}
for(i=0;i<m;i++)
{
for(j=1;j<4;j=j+2)
{
for(k=0;k<2;k++)
for(l=0;l<4;l++)
{
x1[w][0]=ZL_sort[i][0]+'0';
x1[w][1]=s[j];
x1[w][2]='(';
x1[w][3]=ZL_sort[i][1]+'0';
x1[w][4]=s[k];
x1[w][5]=ZL_sort[i][2]+'0';
x1[w][6]=s[l];
x1[w][7]=ZL_sort[i][3]+'0';
x1[w][8]=')';
x1[w][9]='#';
w++;
}
}
}
for(i=0;i<m;i++)
{
for(j=1;j<4;j=j+2)
{
for(k=2;k<4;k++)
for(l=0;l<2;l++)
{
x1[w][0]=ZL_sort[i][0]+'0';
x1[w][1]=s[j];
x1[w][2]='(';
x1[w][3]=ZL_sort[i][1]+'0';
x1[w][4]=s[k];
x1[w][5]=ZL_sort[i][2]+'0';
x1[w][6]=s[l];
x1[w][7]=ZL_sort[i][3]+'0';
x1[w][8]=')';
x1[w][9]='#';
w++;
}
}
}
}

//===============两个括号时的组合================
void ZL_2KSort()
{
//Sort();
//ZL_Sort();
v=0;
for(i=0;i<m;i++)
for(j=0;j<2;j++)
for(k=2;k<4;k++)
for(l=0;l<2;l++)
{
x2[v][0]='(';
x2[v][1]=ZL_sort[i][0]+'0';
x2[v][2]=s[j];
x2[v][3]=ZL_sort[i][1]+'0';
x2[v][4]=')';
x2[v][5]=s[k];
x2[v][6]='(';
x2[v][7]=ZL_sort[i][2]+'0';
x2[v][8]=s[l];
x2[v][9]=ZL_sort[i][3]+'0';
x2[v][10]=')';
x2[v][11]='#';
v++;
}
}

//================判断是否为运算符===============
int In(char Y)
{
if((Y=='+')||(Y=='-')||(Y=='*')||(Y=='/')||(Y=='(')||(Y==')')||(Y=='#')) return 1;
return 0;
}

//=================表达式求值=====================
int EvaluateExpression(char ch[])
{
SqStack_T OPTR;
SqStack_N OPND;
int a,b,y;
int e;
char c,theta;
InitStack_T(OPTR);
Push_T(OPTR,'#');
InitStack_N(OPND);
int COUNT=0;
c=ch[0];
while(c!='#'||GetTop_T(OPTR)!='#')
{
if(!In(c))
{ //c是数字
y=c-'0';
Push_N(OPND,y);
COUNT++;
c=ch[COUNT];
while(!In(c))
{
Pop_N(OPND,e);
e=e*10+c-'0';
Push_N(OPND,e);
COUNT++;
c=ch[COUNT];
}
}
else
switch(Precede(GetTop_T(OPTR),c))
{ //c是字符
case'<':Push_T(OPTR,c);COUNT++;c=ch[COUNT];break;
case'=':Pop_T(OPTR,c);COUNT++;c=ch[COUNT];break;
case'>':
Pop_T(OPTR,theta);
Pop_N(OPND,b);Pop_N(OPND,a);
Push_N(OPND,Operate(a,theta,b));
break;
}
}
return GetTop_N(OPND);
}

int main()
{
ofstream outfile("output.txt",ios::out);//定义文件流对象，打开output.txt文件
if(!outfile)
{ //如果打开文件失败，outfile返回0值
cout<<"文件打开失败！"<<endl;
exit(1);
}
outfile.close();
char f;
ifstream infile("input.txt",ios::in);
if(!infile)
{ //如果打开文件失败，infile返回0值
cout<<"“input.txt”打开失败。是否创建“input.txt”？<Y/N>"<<endl;
cin>>f;
if(f=='Y'||f=='y')
{
ofstream output("input.txt");
if(!output)
{
cout<<"“input.txt”文件创建失败！"<<endl;
exit(1);
}
else
{
cout<<"“input.txt”创建成功，请在“input.txt”中写入数据后重启本程序。"<<endl;
output.close();
system("PAUSE");
return 0;
}
}
else
{
system("pause");
return 0;
}
}
for(i=0;i<4;i++)
c[i]=0;
int z;
int t;
int num;
while(!infile.eof())
{
for(i=0;i<4;i++)
infile>>c[i];
for(j=0;j<4;j++)
if(c[j]==0)
{
cout<<"未读到有效数据，请写入数据后再打开本程序。"<<endl;
system("PAUSE");
return 0;
}
ofstream output("output.txt",ios::app);
if(!output)
{
cout<<"文件打开失败！"<<endl;
exit(1);
}
output<<"—————————————————————————"<<endl;
num=0;
for(i=0;i<4;i++)
output<<c[i]<<" ";
output<<"等于24的表达式："<<endl;
Sort(c);
ZL_Sort();
ZF_Sort();
ZL_2sort();
char ch[8];
//cout<<"无括号时的解："<<endl;
for(i=0;i<n;i++)
{
for(j=0;j<8;j++)
ch[j]=x[i][j];
z=EvaluateExpression(ch);
if(z==24)
{
num++;
output<<num<<".";
for(k=0;k<7;k++)
{
if(!In(ch[k]))
{
t=ch[k]-'0';
output<<t;
}