C#实现的算24点游戏的算法

From , 2 Years ago, written in C#, viewed 209 times.
URL https://pastebin.vip/view/3596c80a
  1. using System;
  2. using System.Collections.Generic;
  3. using System.Linq;
  4. using System.Text;
  5. using System.IO;
  6.  
  7. namespace Calc24Points
  8. {
  9.     public class Cell
  10.     {
  11.         public enum Type
  12.         {
  13.             Number,
  14.             Signal
  15.         }
  16.         public int Number;
  17.         public char Signal;
  18.         public Type Typ;
  19.         public Cell Right;
  20.         public Cell Left;
  21.  
  22.         /// <summary>
  23.         /// 符号优先级
  24.         /// </summary>
  25.         public int Priority
  26.         {
  27.             get
  28.             {
  29.                 if (Typ == Type.Signal)
  30.                 {
  31.                     switch (Signal)
  32.                     {
  33.                         case '+': return 0;
  34.                         case '-': return 0;
  35.                         case '*': return 1;
  36.                         case '/': return 1;
  37.                         default: return -1;
  38.                     }
  39.                 }
  40.                 return -1;
  41.             }
  42.         }
  43.  
  44.         /// <summary>
  45.         /// 基本单元构造函数
  46.         /// </summary>
  47.         /// <param name="t">单元类型,数值或符号</param>
  48.         /// <param name="num">数值</param>
  49.         /// <param name="sig">符号</param>
  50.         public Cell(Type t, int num, char sig)
  51.         {
  52.             Right = null;
  53.             Left = null;
  54.             Typ = t;
  55.             Number = num;
  56.             Signal = sig;
  57.         }
  58.         public Cell()
  59.         {
  60.             Right = null;
  61.             Left = null;
  62.             Number = 0;
  63.             Typ = Type.Number;
  64.         }
  65.         public Cell(Cell c)
  66.         {
  67.             Right = null;
  68.             Left = null;
  69.             Number = c.Number;
  70.             Signal = c.Signal;
  71.             Typ = c.Typ;
  72.         }
  73.     }
  74.     public class Calc24Points
  75.     {
  76.  
  77.         string m_exp;
  78.         bool m_stop;
  79.         Cell[] m_cell;
  80.         int[] m_express;
  81.         StringWriter m_string;
  82.         public Calc24Points(int n1, int n2, int n3, int n4)
  83.         {
  84.             m_cell = new Cell[8];
  85.             m_cell[0] = new Cell(Cell.Type.Number, n1, '?');
  86.             m_cell[1] = new Cell(Cell.Type.Number, n2, '?');
  87.             m_cell[2] = new Cell(Cell.Type.Number, n3, '?');
  88.             m_cell[3] = new Cell(Cell.Type.Number, n4, '?');
  89.             m_cell[4] = new Cell(Cell.Type.Signal, 0, '+');
  90.             m_cell[5] = new Cell(Cell.Type.Signal, 0, '-');
  91.             m_cell[6] = new Cell(Cell.Type.Signal, 0, '*');
  92.             m_cell[7] = new Cell(Cell.Type.Signal, 0, '/');
  93.             m_stop = false;
  94.             m_express = new int[7];
  95.             m_string = new StringWriter();
  96.             m_exp = null;
  97.         }
  98.  
  99.         public override string ToString()
  100.         {
  101.             if (m_exp == null)
  102.             {
  103.                 PutCell(0);
  104.                 m_exp = m_string.ToString();
  105.             }
  106.             if (m_exp != "") return m_exp;
  107.             return null;
  108.         }
  109.  
  110.         /// <summary>
  111.         /// 在第n位置放置一个单元
  112.         /// </summary>
  113.         /// <param name="n"></param>
  114.         void PutCell(int n)
  115.         {
  116.             if (n >= 7)
  117.             {
  118.                 if (Calculate())
  119.                 {
  120.                     m_stop = true;
  121.                     Formate();
  122.                 }
  123.                 return;
  124.             }
  125.             int end = 8;
  126.             if (n < 2) end = 4;
  127.             for (int i = 0; i < end; ++i)
  128.             {
  129.                 m_express[n] = i;
  130.                 if (CheckCell(n)) PutCell(n + 1);
  131.                 if (m_stop) break;
  132.             }
  133.         }
  134.  
  135.         /// <summary>
  136.         /// 检查当前放置是否合理
  137.         /// </summary>
  138.         /// <param name="n"></param>
  139.         /// <returns></returns>
  140.         bool CheckCell(int n)
  141.         {
  142.             int nums = 0, sigs = 0;
  143.             for (int i = 0; i <= n; ++i)
  144.             {
  145.                 if (m_cell[m_express[i]].Typ == Cell.Type.Number) ++nums;
  146.                 else ++sigs;
  147.             }
  148.             if (nums - sigs < 1) return false;
  149.             if (m_cell[m_express[n]].Typ == Cell.Type.Number) //数值不能重复,但是符号可以重复
  150.             {
  151.                 for (int i = 0; i < n; ++i) if (m_express[i] == m_express[n]) return false;            
  152.             }
  153.             if (n == 6)
  154.             {
  155.                 if (nums != 4 || sigs != 3) return false;
  156.                 if (m_cell[m_express[6]].Typ != Cell.Type.Signal) return false;
  157.                 return true;
  158.             }
  159.             return true;
  160.         }
  161.  
  162.         /// <summary>
  163.         /// 计算表达式是否为24
  164.         /// </summary>
  165.         /// <returns>返回值true为24,否则不为24</returns>
  166.         bool Calculate()
  167.         {
  168.             double[] dblStack = new double[4];
  169.             int indexStack = -1;
  170.             for (int i = 0; i < 7; ++i)
  171.             {
  172.                 if (m_cell[m_express[i]].Typ == Cell.Type.Number)
  173.                 {
  174.                     ++indexStack;
  175.                     dblStack[indexStack] = m_cell[m_express[i]].Number;
  176.                 }
  177.                 else
  178.                 {
  179.                     switch (m_cell[m_express[i]].Signal)
  180.                     {
  181.                         case '+':
  182.                             dblStack[indexStack - 1] = dblStack[indexStack - 1] + dblStack[indexStack];
  183.                             break;
  184.                         case '-':
  185.                             dblStack[indexStack - 1] = dblStack[indexStack - 1]-+ dblStack[indexStack];
  186.                             break;
  187.                         case '*':
  188.                             dblStack[indexStack - 1] = dblStack[indexStack - 1] * dblStack[indexStack];
  189.                             break;
  190.                         case '/':
  191.                             dblStack[indexStack - 1] = dblStack[indexStack - 1] / dblStack[indexStack];
  192.                             break;
  193.                     }
  194.                     --indexStack;
  195.                 }
  196.             }
  197.             if (Math.Abs(dblStack[indexStack] - 24) < 0.1) return true;
  198.             return false;
  199.         }
  200.  
  201.         /// <summary>
  202.         /// 后缀表达式到中缀表达式
  203.         /// </summary>
  204.         void Formate()
  205.         {
  206.             Cell[] c = new Cell[7];
  207.             for (int i = 0; i < 7; ++i) c[i] = new Cell(m_cell[m_express[i]]);
  208.             int[] cStack = new int[4];
  209.             int indexStack = -1;
  210.             for (int i = 0; i < 7; ++i)
  211.             {
  212.                 if (c[i].Typ == Cell.Type.Number)
  213.                 {
  214.                     ++indexStack;
  215.                     cStack[indexStack] = i;
  216.                 }
  217.                 else
  218.                 {
  219.                     c[i].Right = c[cStack[indexStack]];
  220.                     --indexStack;
  221.                     c[i].Left = c[cStack[indexStack]];
  222.                     cStack[indexStack] = i;
  223.                 }
  224.             }
  225.             ToStringFormate(c[cStack[indexStack]]);
  226.         }
  227.  
  228.         void ToStringFormate(Cell root)
  229.         {
  230.             if (root.Left.Typ == Cell.Type.Number)
  231.             {
  232.                 m_string.Write(root.Left.Number);
  233.                 m_string.Write(root.Signal);
  234.             }
  235.             else
  236.             {
  237.                 if (root.Priority > root.Left.Priority)
  238.                 {
  239.                     m_string.Write("(");
  240.                     ToStringFormate(root.Left);
  241.                     m_string.Write(")");
  242.                 }
  243.                 else ToStringFormate(root.Left);
  244.                 m_string.Write(root.Signal);
  245.             }
  246.             if (root.Right.Typ == Cell.Type.Number) m_string.Write(root.Right.Number);
  247.             else
  248.             {
  249.                 if (root.Priority >= root.Right.Priority)
  250.                 {
  251.                     m_string.Write("(");
  252.                     ToStringFormate(root.Right);
  253.                     m_string.Write(")");
  254.                 }
  255.                 else ToStringFormate(root.Right);
  256.             }
  257.         }
  258.     }
  259. }
  260.  
  261. //csharp/6411

Reply to "C#实现的算24点游戏的算法"

Here you can reply to the paste above

captcha

https://burned.cc - Burn After Reading Website