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

本文实例讲述了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);
  }
 }
}
}

希望本文所述对大家的C#程序设计有所帮助。