《口算大作战 2》DLC:算法真奇妙

211614331 王诚荣 　　　　211614354 陈斌　--第一次结对作业

DLC

DLC：三年级混合运算模块现已更新！现在您可以愉快的使用三年级题库啦。同时您必须拥有本体才能使用此DLC

单击此处查看本体：《口算大作战 2》标准版

一、开发时间表

PSP2.1	Personal Software Process Stages	预估耗时（分钟）	实际耗时（分钟）
Planning	计划
• Estimate	• 估计这个任务需要多少时间	10	5
Development	开发
• Analysis	• 需求分析 (包括学习新技术)	10	10
• Design Spec	• 生成设计文档	10	15
• Design Review	• 设计复审	5	5
• Coding Standard	• 代码规范 (为目前的开发制定合适的规范)	5	10
• Design	• 具体设计	30	60
• Coding	• 具体编码	300	1320
• Code Review	• 代码复审	30	35
• Test	• 测试（自我测试，修改代码，提交修改）	60	100
Reporting	报告
• Test Repor	• 测试报告	40	60
• Size Measurement	• 计算工作量	5	5
• Postmortem & Process Improvement Plan	• 事后总结, 并提出过程改进计划	20	15
	合计	525	1640

二、用户需求分析

本次的需求分析，我没有去过多的研究，因为在作业博客中，已经有了明确的需求：

• 运算符在2～4个，至少两个不同的运算符
• 可以加括号
• 减法运算的结果不能有负数
• 除法运算除数不能为0，不能有余数
• 同时要有一二年级的题库在里面
• 要分别满足一二三年级运算的需求

经过分析，我认为，这个程序应当：

• **一二年级只要符合上次作业的需求即可，不需要再次分析 **
• 三年级加减乘除中都不能有负数
• 且在除法中，需要特别关注程序除零时的异常处理

三、项目设计分析

1. 设计思路

这次作业由于是结对作业，因此我们有一些明确的分工。在分析完需求之后，我们发现，四则运算是需要重点攻克的难题，但是如果两个人把全部的时间都放在这个地方的话，那么进度一定会被拖慢，无法正常完成任务。所以我们在经过讨论之后，决定先一起讨论一下四则运算的逻辑和解决办法，然后由我负责三年级四则运算的编码，我的队友则负责完成其他模块功能的实现，以此来满足任务需求。最后再把所有的代码整合在一起，完成此次任务。

因此，下面我主要介绍的是 “《口算大作战 2》DLC：算法真奇妙 ” 这个部分的具体细节

• 首先，我要大声的说：一个好的算法是真的很厉害！！！ 逆波兰大法好！！！算法真奇妙！！！（ps：至于具体为什么，等下我就吐槽一下我编码时的辛酸史）

• 首先，我和我的队友需要攻克逆波兰表达式的实现方法，以及背后的逻辑

• 为此我设计了两个类，一个是不断出题并把题目喂给四则运算类，另一个是四则运算类，其中使用了逆波兰和调度场算法来解决四则运算的问题。（我也说一下我们整个程序所用到的类：共有九个类，三年级模块两个类，一二年级四个类，一个运算父类，一个主方法，一个输出类）

  设计类图如下：

• 在本次设计中，遇到了一个关键的问题，就是中缀表达式如何转后缀表达式，以及逆波兰算法。在这个地方，我觉得没有什么比两张张动态图更能理清思路了，通过这两张图片，以及博客说明，我理清了逆波兰和调度场的大致思路。图片转自算法表达式求值--逆波兰算法介绍：
  

• 调度场是用栈的方式来存储遍历的题目结果，并且以特定的规则弹栈和压栈。首先要有两个栈，一个是临时栈，一个是用来存储后缀表达式的栈。然后遍历题目，当为数字时，直接压入后缀栈，遇到符号时，左括号直接进栈，加减乘除要和临时栈顶比较优先级，和是否同级，如果优先级高直接压入临时栈，如果是同级或者优先级低，则临时栈要弹出栈顶--并把栈顶放入后缀栈，以此循环，直到准备进入的符号优先级比栈顶高（此处要注意空栈的情况）。当遇到右括号是，右括号直接抛弃，临时栈开始弹栈--并压入后缀栈，直到临时栈的栈顶为左括号，然后将左括号抛弃

2. 实现方案

• 准备工作：先在Github上创建仓库，克隆到本地，在本地新建Pair_211614331_211614354文件夹，在eclipes中创建工程
• 技术关键点：
  • 逆波兰算法的实现（理解，外加各种空栈异常判断）
  • 随机出题目的逻辑，以及加括号时的逻辑判断

四、引擎模块

写在前面的小花絮：

在一开始，我并没有打算使用调度场和逆波兰算法，我有点想自己尝试着写出四则运算的解决办法。于是我开始了异常艰难的旅程。可以说编码的一大半时间都放在了这里。在当时，我的想法是，既然四则运算，括号优先级最高，那么我是不是可以先遍历题目，找到最里面的一个括号，再调用函数把括号里的值算出来，得到结果后，返回个题目，然后继续遍历，寻找括号。

沿着这个思路，我就建立了两个类，一个是找呀找呀找括号的类，一个是复制运算不带括号的四则运算类。经过长时间的编码和除bug，我的程序是可以跑起来的，可以正常解题！！！当时还是有点小激动的。这份喜悦直到我开始大量的出题目时被彻底浇灭了，我的这套解题程序，遇到几个题目还好，当遇到了大量题目时，根本反应不过来，处理速度极慢，尤其是到了四百多题的时候，变的越来越慢，越来越慢，最后就是几秒钟才弹出题目和答案......然后我就迷茫了，这时我去看了室友的解决办法，他使用的是调度场和逆波兰， 哇！真的不敢想象，题目就那样刷的一下，连同答案一起跳出来了！！！这也太快了吧，我的算法是个什么垃圾......

然后我才乖乖的开始学习逆波兰和调度场，学习效率比我快十几倍的算法。所以说，还是那句话：算法真奇妙！！！

1. 调试日志

记录编码调试的日志，请记录下开发过程中的 debug 历程

• 在使用调度场算法编码的过程中，主要遇到的还是在入栈符号优先级更低，和同级情况下，临时栈弹出后，循环判断时，容易出现空栈的情况。
  • 这个问题我一开始也是没有头绪的，就想到一个，使用do-while进行循环判断，但是一直卡在了循环跳出时的判断，因为跳出时判断有多重情况，一个是弹玩就是空栈，一个是栈顶还是优先级大于等于入栈元素。后来我在do-while语句中间，加了一个判断是否为空的语句，当空就直接break循环,才解决的
• 还有一个问题就是，括号出现的问题，这里我暂时采用的是定位随机的办法，即我事先规定了十多种括号的出现情况，把他们分别存储在字符串中（取名为括号标准定位码），然后用随机的办法，选择一种括号情况，放入事先出好的题目中。这种办法，并没有真正的随机出现括号，但是因为我不带括号的题目是随机生成的，题目各不相同，因此，在一定情况下，也可以看作是随机生成的带括号的四则运算式子。

2. 关键代码

请展示一段程序的关键代码，并解释代码的作用

switch (order) {
				case 1:{
					positionCode="(---)-(---)";    //定位码的几种情况，随机选定后，扫描定位码，发现括号则加入；
					break;        //一部分情况
				}
				case 2:{
					positionCode="--(---)-(---)";
					break;
				}
				case 3:{
					positionCode="--((---)--)";
					break;
				}
				case 4:{
					positionCode="--((---)-(---))";
					break;
				}
				case 5:{
					positionCode="(-----)";

程序产生括号的代码确实不够优雅，但也能临时解决问题，同时其实是可以不用扫描定位码的，可以换一种形式，比如直接存左右括号的位置，这样加入集合也更加迅速。当然，还有真正正牌的随机办法，但我没有想到......

if(!shortStack.isEmpty()) {
						


					 if(shortStack.peek().matches("[\+\-\*\/]")) {	// 栈顶为同级或加减
						 do {
							 postFixStack.push(shortStack.pop());//栈顶和入栈的同级，或级别更高
							 if(shortStack.isEmpty())//判断弹玩是否变空
								 break;//弹玩后，变空
							 
						 }while(shortStack.peek().matches("[\+\-\*\/]") );//栈顶还是这些时
						 shortStack.push(partNumber);	// 把当前元素入栈
					 }
					 else
						 shortStack.push(partNumber);	// 栈顶就是括号的时候，把当前元素入栈	
				}
				else
					shortStack.push(partNumber); //是空直接压栈

中缀转后置表达式很大一部分的报错都是因为弹的是空栈，所以理清楚这个，就算是完成了一大步了。

3. 代码规范

请给出本次实验使用的代码规范：

• 第一条：代码中的命名均不能以下划线或美元符号开始，也不以一下划线或美元符号结束
• 第二条：代码中的命名严禁使用拼音与英文混合的方式，更不允许直接使用中文的方式
• 第三条：类名使用UpperCamelCase风格
• 第四条：方法名、参数名、成员变量、局部变量都统一使用 lowerCamelCase 风格
• 第五条：杜绝完全不规范的缩写，避免忘文不知义，都以英文单词命名
• 第六条：采用4个空格缩进，禁止使用tab字符
• 第七条：不同逻辑、不同语义、不同业务的代码之间插入一个空行分割开来以提升可读性。
  

4.结对编程

• 在结对编程中我们在有明确的分工，才尽可能的保证了项目的进度。
• 同时我们也相互讨论各自所遇到的问题，一开始没有头绪，但双方讨论后，可能就会瞬间想到思路

五、BUG调试

请思考并记录你认为必要的测试点，并记录测试用例与测试结果

六、开发者有话说

• 好的算法尤其重要，它更轻量也更加高效，在完成我负责的部分里，我们两个都认识到了算法的重要性，真的不一样！！！

• 同时，当有还要有团队合作的能力，要学会与队友沟通和交流，有时候，思路就是在交流中闪现的，一个人想不到，几个人就会有不一样的思路，俗话说的好，三个臭皮匠，顶个诸葛亮。

• 当项目越来越大的时候，一个人就很难在规定的时间内完成任务，也就是说，我们在今后一定会经常遇到与他人合作的情况。很大一部分情况中1+1>2，所以在团队中，尽力去做，效果也会翻倍！！！

• 当然，在沟通时，也要有耐心，同时要想办法把自己的想法表达出来，这点我还是需要学习的。