C#实现的算24点游戏算法实例分析

using System;using System.Collections.Generic;using System.Linq;using System.Text;using System.IO;namespace Calc24Points{ public class Cell {  public enum Type  {   Number,   Signal  }  public int Number;  public char Signal;  public Type Typ;  public Cell Right;  public Cell Left;  /// <summary>  /// 符号优先级  /// </summary>  public int Priority  {   get   {    if (Typ == Type.Signal)    {     switch (Signal)     {      case '+': return 0;      case '-': return 0;      case '*': return 1;      case '/': return 1;      default: return -1;     }    }    return -1;   }  }  /// <summary>  /// 基本单元构造函数  /// </summary>  /// <param name="t">单元类型，数值或符号</param>  /// <param name="num">数值</param>  /// <param name="sig">符号</param>  public Cell(Type t, int num, char sig)  {   Right = null;   Left = null;   Typ = t;   Number = num;   Signal = sig;  }  public Cell()  {   Right = null;   Left = null;   Number = 0;   Typ = Type.Number;  }  public Cell(Cell c)  {   Right = null;   Left = null;   Number = c.Number;   Signal = c.Signal;   Typ = c.Typ;  } } public class Calc24Points {  string m_exp;  bool m_stop;  Cell[] m_cell;  int[] m_express;  StringWriter m_string;  public Calc24Points(int n1, int n2, int n3, int n4)  {   m_cell = new Cell[8];   m_cell[0] = new Cell(Cell.Type.Number, n1, '?');   m_cell[1] = new Cell(Cell.Type.Number, n2, '?');   m_cell[2] = new Cell(Cell.Type.Number, n3, '?');   m_cell[3] = new Cell(Cell.Type.Number, n4, '?');   m_cell[4] = new Cell(Cell.Type.Signal, 0, '+');   m_cell[5] = new Cell(Cell.Type.Signal, 0, '-');   m_cell[6] = new Cell(Cell.Type.Signal, 0, '*');   m_cell[7] = new Cell(Cell.Type.Signal, 0, '/');   m_stop = false;   m_express = new int[7];   m_string = new StringWriter();   m_exp = null;  }  public override string ToString()  {   if (m_exp == null)   {    PutCell(0);    m_exp = m_string.ToString();   }   if (m_exp != "") return m_exp;   return null;  }  /// <summary>  /// 在第n位置放置一个单元  /// </summary>  /// <param name="n"></param>  void PutCell(int n)  {   if (n >= 7)   {    if (Calculate())    {     m_stop = true;     Formate();    }    return;   }   int end = 8;   if (n < 2) end = 4;   for (int i = 0; i < end; ++i)   {    m_express[n] = i;    if (CheckCell(n)) PutCell(n + 1);    if (m_stop) break;   }  }  /// <summary>  /// 检查当前放置是否合理  /// </summary>  /// <param name="n"></param>  /// <returns></returns>  bool CheckCell(int n)  {   int nums = 0, sigs = 0;   for (int i = 0; i <= n; ++i)   {    if (m_cell[m_express[i]].Typ == Cell.Type.Number) ++nums;    else ++sigs;   }   if (nums - sigs < 1) return false;   if (m_cell[m_express[n]].Typ == Cell.Type.Number)   //数值不能重复，但是符号可以重复   {    for (int i = 0; i < n; ++i) if (m_express[i] == m_express[n]) return false;      }   if (n == 6)   {    if (nums != 4 || sigs != 3) return false;    if (m_cell[m_express[6]].Typ != Cell.Type.Signal) return false;    return true;   }   return true;  }  /// <summary>  /// 计算表达式是否为24  /// </summary>  /// <returns>返回值true为24，否则不为24</returns>  bool Calculate()  {   double[] dblStack = new double[4];   int indexStack = -1;   for (int i = 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) return true;   return false;  }  /// <summary>  /// 后缀表达式到中缀表达式  /// </summary>  void Formate()  {   Cell[] c = new Cell[7];   for (int i = 0; i < 7; ++i) c[i] = new Cell(m_cell[m_express[i]]);   int[] cStack = new int[4];   int indexStack = -1;   for (int i = 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]]);  }  void ToStringFormate(Cell root)  {   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(")");    }    else ToStringFormate(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(")");    }    else ToStringFormate(root.Right);   }  } }}