Home > Backend Development > C#.Net Tutorial > Algorithm for calculating 24-point game implemented in C#

Algorithm for calculating 24-point game implemented in C#

大家讲道理
Release: 2016-11-10 16:21:50
Original
1915 people have browsed it

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 &#39;+&#39;: return 0;
                        case &#39;-&#39;: return 0;
                        case &#39;*&#39;: return 1;
                        case &#39;/&#39;: 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, &#39;?&#39;);
            m_cell[1] = new Cell(Cell.Type.Number, n2, &#39;?&#39;);
            m_cell[2] = new Cell(Cell.Type.Number, n3, &#39;?&#39;);
            m_cell[3] = new Cell(Cell.Type.Number, n4, &#39;?&#39;);
            m_cell[4] = new Cell(Cell.Type.Signal, 0, &#39;+&#39;);
            m_cell[5] = new Cell(Cell.Type.Signal, 0, &#39;-&#39;);
            m_cell[6] = new Cell(Cell.Type.Signal, 0, &#39;*&#39;);
            m_cell[7] = new Cell(Cell.Type.Signal, 0, &#39;/&#39;);
            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 &#39;+&#39;:
                            dblStack[indexStack - 1] = dblStack[indexStack - 1] + dblStack[indexStack];
                            break;
                        case &#39;-&#39;:
                            dblStack[indexStack - 1] = dblStack[indexStack - 1]-+ dblStack[indexStack];
                            break;
                        case &#39;*&#39;:
                            dblStack[indexStack - 1] = dblStack[indexStack - 1] * dblStack[indexStack];
                            break;
                        case &#39;/&#39;:
                            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);
            }
        }
    }
}
Copy after login

source:php.cn
Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
Popular Tutorials
More>
Latest Downloads
More>
Web Effects
Website Source Code
Website Materials
Front End Template