下面资料是关于 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;
- public int Priority
- {
- get
- {
- if (Typ == Type.Signal)
- {
- switch (Signal)
- {
- case '+': return 0;
- case '-': return 0;
- case '/': return 1;
- default: return -1;
- }
- }
- return -1;
- }
- }
- 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[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;
- }
- 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;
- }
- }
- 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;
- {
- 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;
- }
- 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;
- break;
- case '/':
- dblStack[indexStack - 1] = dblStack[indexStack - 1] / dblStack[indexStack];
- break;
- }
- --indexStack;
- }
- }
- if (Math.Abs(dblStack[indexStack] - 24) < 0.1) return true;
- return false;
- }
- 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);
- }
- }
- }
- }
来源: http://www.bubuko.com/infodetail-2921515.html