C#实现的算24点游戏算法实例分析
本文实例讲述了C#实现的算24点游戏算法。分享给大家供大家参考。具体如下：
usingSystem;
usingSystem.Collections.Generic;
usingSystem.Linq;
usingSystem.Text;
usingSystem.IO;
namespaceCalc24Points
{
publicclassCell
{
publicenumType
{
Number,
Signal
}
publicintNumber;
publiccharSignal;
publicTypeTyp;
publicCellRight;
publicCellLeft;
///<summary>
///符号优先级
///</summary>
publicintPriority
{
get
{
if(Typ==Type.Signal)
{
switch(Signal)
{
case'+':return0;
case'-':return0;
case'*':return1;
case'/':return1;
default:return-1;
}
}
return-1;
}
}
///<summary>
///基本单元构造函数
///</summary>
///<paramname="t">单元类型，数值或符号</param>
///<paramname="num">数值</param>
///<paramname="sig">符号</param>
publicCell(Typet,intnum,charsig)
{
Right=null;
Left=null;
Typ=t;
Number=num;
Signal=sig;
}
publicCell()
{
Right=null;
Left=null;
Number=0;
Typ=Type.Number;
}
publicCell(Cellc)
{
Right=null;
Left=null;
Number=c.Number;
Signal=c.Signal;
Typ=c.Typ;
}
}
publicclassCalc24Points
{
stringm_exp;
boolm_stop;
Cell[]m_cell;
int[]m_express;
StringWriterm_string;
publicCalc24Points(intn1,intn2,intn3,intn4)
{
m_cell=newCell[8];
m_cell[0]=newCell(Cell.Type.Number,n1,'?');
m_cell[1]=newCell(Cell.Type.Number,n2,'?');
m_cell[2]=newCell(Cell.Type.Number,n3,'?');
m_cell[3]=newCell(Cell.Type.Number,n4,'?');
m_cell[4]=newCell(Cell.Type.Signal,0,'+');
m_cell[5]=newCell(Cell.Type.Signal,0,'-');
m_cell[6]=newCell(Cell.Type.Signal,0,'*');
m_cell[7]=newCell(Cell.Type.Signal,0,'/');
m_stop=false;
m_express=newint[7];
m_string=newStringWriter();
m_exp=null;
}
publicoverridestringToString()
{
if(m_exp==null)
{
PutCell(0);
m_exp=m_string.ToString();
}
if(m_exp!="")returnm_exp;
returnnull;
}
///<summary>
///在第n位置放置一个单元
///</summary>
///<paramname="n"></param>
voidPutCell(intn)
{
if(n>=7)
{
if(Calculate())
{
m_stop=true;
Formate();
}
return;
}
intend=8;
if(n<2)end=4;
for(inti=0;i<end;++i)
{
m_express[n]=i;
if(CheckCell(n))PutCell(n+1);
if(m_stop)break;
}
}
///<summary>
///检查当前放置是否合理
///</summary>
///<paramname="n"></param>
///<returns></returns>
boolCheckCell(intn)
{
intnums=0,sigs=0;
for(inti=0;i<=n;++i)
{
if(m_cell[m_express[i]].Typ==Cell.Type.Number)++nums;
else++sigs;
}
if(nums-sigs<1)returnfalse;
if(m_cell[m_express[n]].Typ==Cell.Type.Number)
//数值不能重复，但是符号可以重复
{
for(inti=0;i<n;++i)if(m_express[i]==m_express[n])returnfalse;
}
if(n==6)
{
if(nums!=4||sigs!=3)returnfalse;
if(m_cell[m_express[6]].Typ!=Cell.Type.Signal)returnfalse;
returntrue;
}
returntrue;
}
///<summary>
///计算表达式是否为24
///</summary>
///<returns>返回值true为24，否则不为24</returns>
boolCalculate()
{
double[]dblStack=newdouble[4];
intindexStack=-1;
for(inti=0;i<7;++i)
{
if(m_cell[m_express[i]].Typ==Cell.Type.Number)
{
++indexStack;
dblStack[indexStack]=m_cell[m_express[i]].Number;
}
else
{
switch(m_cell[m_express[i]].Signal)
{
case'+':
dblStack[indexStack-1]=dblStack[indexStack-1]+dblStack[indexStack];
break;
case'-':
dblStack[indexStack-1]=dblStack[indexStack-1]-+dblStack[indexStack];
break;
case'*':
dblStack[indexStack-1]=dblStack[indexStack-1]*dblStack[indexStack];
break;
case'/':
dblStack[indexStack-1]=dblStack[indexStack-1]/dblStack[indexStack];
break;
}
--indexStack;
}
}
if(Math.Abs(dblStack[indexStack]-24)<0.1)returntrue;
returnfalse;
}
///<summary>
///后缀表达式到中缀表达式
///</summary>
voidFormate()
{
Cell[]c=newCell[7];
for(inti=0;i<7;++i)c[i]=newCell(m_cell[m_express[i]]);
int[]cStack=newint[4];
intindexStack=-1;
for(inti=0;i<7;++i)
{
if(c[i].Typ==Cell.Type.Number)
{
++indexStack;
cStack[indexStack]=i;
}
else
{
c[i].Right=c[cStack[indexStack]];
--indexStack;
c[i].Left=c[cStack[indexStack]];
cStack[indexStack]=i;
}
}
ToStringFormate(c[cStack[indexStack]]);
}
voidToStringFormate(Cellroot)
{
if(root.Left.Typ==Cell.Type.Number)
{
m_string.Write(root.Left.Number);
m_string.Write(root.Signal);
}
else
{
if(root.Priority>root.Left.Priority)
{
m_string.Write("(");
ToStringFormate(root.Left);
m_string.Write(")");
}
elseToStringFormate(root.Left);
m_string.Write(root.Signal);
}
if(root.Right.Typ==Cell.Type.Number)m_string.Write(root.Right.Number);
else
{
if(root.Priority>=root.Right.Priority)
{
m_string.Write("(");
ToStringFormate(root.Right);
m_string.Write(")");
}
elseToStringFormate(root.Right);
}
}
}
}
希望本文所述对大家的C#程序设计有所帮助。