四则运算之二十点小游戏(持续更新)

//github相关链接

//完整工程源码：https://github.com/Dawnfoxer/ranh941/commit/ac9f7ee72751591a6e03b311c04e4f8053e5e77c

//UML：https://github.com/Dawnfoxer/ranh941/tree/c7f1c779b2162fcd99d9b97c68d7473ef3794d04/C_Sharp/twefourpoint/UML

//docs:待定

背景：此前自己闲时写过一个C#的二十四点程序，符合Teacher Young的第一次作业编程要求。相关源码和文档已上传GitHub。

一、需求描述

　　设计一个“二十四点”游戏程序，图形界面类似下图所示，要求可以校验输入答案是否正确（表达式支持括号操作），同时具有自动求解功能（该算法需要在报告中详细说明）；另外，如无解应重新出题。

可选功能：计时、记录成绩排行榜

二、功能分析

1.1 基础功能

（1）出题；

（2）若当前题目存在结果为24的表达式则给出，若不存在则显示不存在；

（3）检验输入答案是否正确；

（4）记录答题时间；

（5）记录成绩排行榜。

1.2 实际功能

（1）游戏启动时，自动出题。用户也可以手工出题；

（2）用户可选择开始和暂停游戏；

（3）存在24的表达式时给出答案，不存在则显示不存在；

（4）设定每次答题时间为60s，同时记录每次答题开始时间、结束时间、答题时长和答题结果；

（5）暂停游戏后答题，只有一次答题机会，若正确则根据提示重新开始游戏或返回当前游戏（自动显示系统正确答案），若错误则直接给出答案，同时结束本次游戏；

（6）在有效时间内答题次数不限制，若答题正确则根据提示重新开始游戏或返回当前游戏（自动显示系统正确答案），若错误则根据提示重新开始游戏或返回当前游戏继续答题。

（7）查询记录。查询每次答题信息，包括起始时间、时长和答题结果。可选择清楚历史答题记录。

（8）游戏玩法和版权。关于游戏的信息介绍。

1.3 程序基本界面（具体图形界面见附录）

三、具体实现

1.1 开发环境

开发工具：Visual Studio 2015 64位 + Windows10 64位。

测试机器：Windows10 64位，Windows7 32位。

其他：StartUML。

1.2 实现过程

（1）根据面向对象编程模块化思想，将游戏的界面和逻辑处理分离。确定程序涉及到的各个功能，先针对每个功能做原型测试，再将各个功能集成。最后才根据题目要求确定界面。

（2）将题目的基本要求完成之后，再进行功能上的拓展。前后总共用四天左右的时间，主要时间是用在原型测试上。最先做的原型是对一表达式求值，然后是四个数插入四则符号组成的表达式，最后是带括号的表达式。

（3）在编码的过程中，完善逻辑上的处理，对数据和操作的封装。

1.3 程序易忽视点

1. 用户输入的表达式元素是否是当前的四个基础元素；

2. 四个基础元素的顺序可以改变；

3. 将字符串通过Split函数处理时产生的额外的空格；

4. 用户输入的表达式存在空格；

5. 进行四则计算时对分数或小数或负数的处理；

6. 在主窗体上新建子窗体，同时锁定父窗体，父窗体无法操作；

7. 每次处理完文件需要关闭文件流，否则线程占用；

8. 以什么形式记录数据到本地。

1.4 系统的UML静态图

四、关键问题

1.1 求表达式的值

1.1.1 算法陈述

采用栈的数据结构。

首先建立两个栈，操作数栈ovs用来记录表达式中的操作符，运算符栈ops用来存放表达式中的操作符。一开始表达式是按照从左到右顺序存放在字符串数组中，以‘；’作为结束符。对数组进行遍历，假设当前遍历的元素是str。根据不同的元素进行如下如下的处理：

（1）如果是操作数，则入栈ovs;

（2）如果是操作符，则需要考虑以下情况：

1. 第一个操作符都入栈ops;

2. 若操作符为左括号，则入栈ops;

3. 若操作符为右括号，则存在两种可能：

A. 若ops栈顶元素为左括号，ops出栈;

B. 否则将ovs栈栈顶两个元素弹出，ops栈顶元素弹出，设先后弹出的操作数为a、b，再从运算符栈ops中弹出一个运算符，设为+，然后作运算a+b,并将运算结果压入操作数栈ovs。

4. 若操作符为四则运算符（+=*/）,则存在三种可能：

A. 若当前ops栈顶元素不为左括号,分两组情形：

a) 若当前遍历操作符优先级低于等于操作符栈ops栈顶元素优先级，则将ovs栈栈顶两个元素弹出，ops栈顶元素弹出，设先后弹出的操作数为a、b，再从运算符栈ops中弹出一个运算符，设为+，然后作运算a+b,并将运算结果压入操作数栈ovs和当前遍历的运算符压入操作符栈ops。

b) 若当前遍历操作符优先级高于操作符栈ops栈顶元素优先级，则入栈ops；

B. 若当前ops栈顶元素为左括号，则入栈ops;

（3）如果为‘；’，则存在两种可能：

1. 若ops中元素为0，则ovs栈顶元素弹出，作为表达式最终的结果；

2. 若ops中元素不为0，则

A. ovs栈栈顶两个元素弹出，ops栈顶元素弹出，设先后弹出的操作数为a、b，再从运算符栈ops中弹出一个运算符，设为+，然后作运算a+b,并将运算结果压入操作数栈ovs;

B. 重复A的操作，直到ops中元素为0，重复（3）中1.的操作。

  1         //求表达式值
  2         static int opsExp(string[] arr)
  3         {
  4             arr = arr.Where(s => !string.IsNullOrEmpty(s)).ToArray();
  5             Stack<string> ovs = new Stack<string>();//操作数
  6             Stack<string> ops = new Stack<string>();//操作符
  7             int res = 0;
  8             foreach (string str in arr)
  9             {
 10                 if (str.Equals(";"))
 11                 {
 12                     while (ops.Count != 0)
 13                     {
 14                         if (ovs.Count >= 2)
 15                         {
 16                             string firOps = ovs.Pop();
 17                             string secOps = ovs.Pop();
 18                             string onceOps = ops.Pop();
 19                             int[] resOps = opsAl(secOps, firOps, onceOps);
 20                             if (isValid(resOps[0]))
 21                             {
 22                                 ovs.Push(resOps[1].ToString());
 23 
 24                             }
 25                             else
 26                             {
 27                                 return res;
 28 
 29                             }
 30 
 31                         }
 32                     }
 33 
 34                     if (ops.Count == 0)
 35                     {
 36 
 37                         res = int.Parse(ovs.Pop());
 38                         break;
 39                     }
 40 
 41                 }
 42                 if (ovsArr.Contains(str))
 43                 {
 44                     ovs.Push(str);
 45                 }
 46                 else if (opsArr.Contains(str))
 47                 {
 48                     //第一个运算符
 49                     if (ops.Count == 0)
 50                     {
 51                         ops.Push(str);
 52                     }
 53                     else {
 54 
 55                         //遇到左括号
 56                         if (str.Equals("("))
 57                         {
 58                             ops.Push(str);
 59                         }
 60 
 61                         //15/12/24 3:30 by hr
 62                         // 还需要考虑括号隔两个操作符的情况！
 63                         //遇到右括号且当前栈顶元素为左括号 
 64                         //if (str.Equals(")") && ops.Peek().Equals('('))
 65                         if (str.Equals(")"))
 66                         {
 67                             //还需要考虑括号隔两个操作符的情况！
 68                             while (!ops.Peek().Equals("("))
 69                             {
 70                                 if (ovs.Count >= 2)
 71                                 {
 72                                     string firOps = ovs.Pop();
 73                                     string secOps = ovs.Pop();
 74                                     string onceOps = ops.Pop();
 75                                     int[] resOps = opsAl(secOps, firOps, onceOps);
 76                                     if (isValid(resOps[0]))
 77                                     {
 78                                         ovs.Push(resOps[1].ToString());
 79                                     }
 80                                     else
 81                                     {
 82                                         return res;
 83                                     }
 84                                 }
 85 
 86                             }
 87                             if (ops.Peek().Equals("("))
 88                             {
 89                                 ops.Pop();
 90                             }
 91 
 92                         }
 93 
 94 
 95                         if ((str.Equals("+") || str.Equals("-") || str.Equals("*") || str.Equals("/")))
 96                         {
 97 
 98                             //当前操作符优先级低于操作符栈顶元素优先级 
 99                             if (!ops.Peek().Equals("(") && privority(ops.Peek()) >= privority(str))
100                             {
101                                 if (ovs.Count >= 2)
102                                 {
103                                     string firOps = ovs.Pop();
104                                     string secOps = ovs.Pop();
105                                     string onceOps = ops.Pop();
106                                     int[] resOps = opsAl(secOps, firOps, onceOps);
107                                     if (isValid(resOps[0]))
108                                     {
109                                         ovs.Push(resOps[1].ToString());
110                                         ops.Push(str);
111                                     }
112                                     else
113                                     {
114                                         return res;
115                                     }
116 
117                                 }
118                             }
119 
120                             //当前运算符优先级大于运算符栈顶元素优先级
121                             if (!ops.Peek().Equals("(") && privority(ops.Peek()) < privority(str))
122                             {
123                                 ops.Push(str);
124                             }
125 
126                             if (ops.Peek().Equals("("))
127                             {
128                                 ops.Push(str);
129                             }
130 
131 
132                         }
133                     }
134 
135                 }
136                 else
137                 {
138                     //Console.WriteLine("存在不合法数据或符号");
139                     break;
140                 }
141 
142             }
143 
144             return res;
145         }

1.2 四个数和四则运算以及括号组成的表达式

可以采取分治的思想。先考虑四个数的组合情况（四个数一开始是生成了的，也就是说四个数给定了的），再考虑向四个数中插入三个运算符，最后再考虑加入括号的情况。四个数不重复的组合数是4*3*2*1=24种，从四个运算符中选3个组成的组合共有4^3=64种，也就是说不含括号的表达式总共有24*64=1536种可能。再来考虑加括号的可能，分为两种情况，四个数加括号的有效情况：一种是只有一对括号，一种是只有两对括号，均为5种，因此带括号的表达式总共1536*10=15360种。这说明采取枚举法是可取的。

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24

红色格子为插入数字，黑色为插入运算符，其余部分则是插入括号。

将数字和运算符的位置固定，用循环对其赋值，括号的位置可直接枚举后，循环进行赋值，如此即可获取所有的表达式组合。

  1         //满足24的表达式
  2         //返回值为空字符时 表示不存在满足条件的表达式
  3         static string rightExp(string ops0, string ops1, string ops2, string ops3)
  4         {
  5             string[] exp = new string[200];//存储表达式 无括号
  6             string[] expKhArr = new string[200];//存储表达式 带括号
  7             exp[199] = ";";//表达式结束符
  8             string rExp = "";//存放正确的表达式
  9 
 10             exp[2] = ops0;
 11             exp[8] = ops1;
 12             exp[14] = ops2;
 13             exp[20] = ops3;
 14 
 15             //无括号
 16             for (int o = 0; o < 4; o++)
 17                 for (int p = 0; p < 4; p++)
 18                     for (int q = 0; q < 4; q++)
 19                     {
 20                         exp[5] = fOps[o];
 21                         exp[11] = fOps[p];
 22                         exp[17] = fOps[q];
 23 
 24                         //默认 没有括号的情况
 25                         rExp = isRightExp(exp);
 26                         if (rExp.Count() != 0)
 27                         {
 28                             return rExp;
 29                         }
 30 
 31                         //一对括号
 32                         for (int i = 0; i < kh1ps.Length; i += 2)
 33                         {
 34 
 35                             expKhArr = expKh(exp, false, i, (i + 1));
 36                             rExp = isRightExp(expKhArr);
 37                             if (rExp.Count() != 0)
 38                             {
 39                                 return rExp;
 40                             }
 41 
 42                             //清除此次运算的括号 运算符和操作数是固定位置 可被覆盖 因此不作考虑
 43                             exp[kh1ps[i]] = "";
 44                             exp[kh1ps[i + 1]] = "";
 45 
 46                         }
 47 
 48                         //两对括号
 49                         for (int i = 0; i < kh2ps.Length; i += 4)
 50                         {
 51 
 52                             expKhArr = expKh(exp, true, i, (i + 1), (i + 2), (i + 3));
 53                             rExp = isRightExp(expKhArr);
 54                             if (rExp.Count() != 0)
 55                             {
 56                                 return rExp;
 57                             }
 58                             
 59                             //清除此次运算的括号
 60                             exp[kh2ps[i]] = "";
 61                             exp[kh2ps[i + 1]] = "";
 62                             exp[kh2ps[i + 2]] = "";
 63                             exp[kh2ps[i + 3]] = "";
 64 
 65                         }
 66                     }
 67 
 68             return rExp;
 69         }
 70 
 71         //产生四个基础元素
 72         public static string[] randElem()
 73         {
 74             string[] elem = new string[4];
 75             Random a = new Random();
 76             int elemNum = 0;
 77             while (elemNum < 4)
 78             {
 79                 int opsEle = a.Next(0, 13);
 80                 string opsTemp = ovsArr[opsEle];
 81                 if (!elem.Contains(opsTemp))
 82                 {
 83                     elem[elemNum++] = opsTemp;
 84                     //  Console.WriteLine("基础："+opsEle);
 85                 }
 86 
 87             }
 88             return elem;
 89         }
 90 
 91         //考虑正确表达式带括号 
 92         //flag false为一括号 true为二括号
 93         static string[] expKh(string[] expKh, bool flag, int a, int b, int c = 0, int d = 0)
 94         {
 95             if (!flag)
 96             {
 97 
 98                 expKh[kh1ps[a]] = "(";
 99                 expKh[kh1ps[b]] = ")";
100             }
101             else
102             {
103                 expKh[kh2ps[a]] = "(";
104                 expKh[kh2ps[b]] = ")";
105                 expKh[kh2ps[c]] = "(";
106                 expKh[kh2ps[d]] = ")";
107             }
108             return expKh;
109         }
110 
111         //获取表达式的值是否为24
112        static string isRightExp(string[] exp)
113         {
114             string rightExp = "";
115             if (opsExp(exp) == 24)
116             {
117                 rightExp = String.Join("", exp.Where(s => !string.IsNullOrEmpty(s)).ToArray());
118                 return rightExp.TrimEnd(';');
119             }
120             else {
121                 rightExp = "";//清空数据 下次不受影响
122             }
123 
124             return rightExp;
125         }
126 
127         //基础元素的组合
128         static string[] opsP(string[] ops)
129         {
130             string[] opsP = new string[222];
131             int opsPNum = 0;
132             int opsNum = ops.Length;
133             for (int i = 0; i < opsNum; i++)
134                 for (int j = 0; j < opsNum; j++)
135                     for (int k = 0; k < opsNum; k++)
136                         for (int l = 0; l < opsNum; l++)
137                         {
138                             if (i != j && i != k && i != l && j != k && j != l && k != l)
139                             {
140                                 opsP[opsPNum++] = ops[i];
141                                 opsP[opsPNum++] = ops[j];
142                                 opsP[opsPNum++] = ops[k];
143                                 opsP[opsPNum++] = ops[l];
144 
145                             }
146                         }
147 
148             return opsP;
149         }
150 
151         //值为的24表达式组合是否存在
152         public static string beginTestRightExp(string[] eleArr)
153         {
154             string[] opsPArr = opsP(eleArr);
155             string rightexp = "";
156             for (int i = 0; i < opsPArr.Length; i += 4)
157             {
158                 rightexp = rightExp(opsPArr[i], opsPArr[i + 1], opsPArr[i + 2], opsPArr[i + 3]);
159                 if (rightexp.Length != 0)
160                 {
161                     return rightexp;
162                 }
163 
164             }
165 
166             return rightexp;
167         }

View Code

附录：

附加：

　　1. 疑问，这能算是投机取巧？在进度条中的代码量应该记为0？

　　2. 在大一下使用GitHub,虽然每次重装系统后都会安装好GitHub Windows客户端，但是除了看看别人的代码，基本就没使用。这次使用，折腾了49min（包含网络影响）。忏愧。图有其表，差评。待改进。后期补上相关博客（截止日期16/3/21）。

　　3. 因程序基本完成，本打算对代码进行效能分析（performance wizard？）。此前从未接触过，网上查询相关资料（40~60min），失败。后期完成（截止日期16/3/28）。耽误太多时间。

　　4. 第一次编辑（109min）；第二次编辑（预计60min/实际73min）。

　　5. 该程序作为分析程序，独立出来，关于四则运算程序重新编写（截止时间2016/03/18）。

路漫漫其修远兮，吾将上下而求索；