四则运算生成

项目Github地址：https://github.com/Shrouding-Potion/QuestGen

---

PSP 2.1	Personal Software Process Stages	预估耗时(小时)	实际耗时(小时)
Planning	计划
· Estimate	· 估计这个任务需要多少时间	28.25	33.5
Development	开发
· Analysis	· 需求分析	1	1
· Design Spec	· 生成设计文档	1	0.5
· Design Review	· 设计复审	0.25	0.0
· Coding Standard	· 代码规范	2	1
· Design	· 具体设计	2	4
· Coding	· 具体编码	12	14
· Code Review	· 代码复审	3	3
· Test	· 测试	5	6
Reporting	报告
· Test Report	· 测试报告	1	1
· Size Measurement	· 计算工作量	0	0
· Postmortem & Process Improvement Plan	· 事后总结，提出过程改进计划	1	1
	合计	28.25	31.5

1. 任务目标

• 一阶段 - 要求能生成、计算、支持真分数四则运算，同时能接受用户输入答案，给出总共对错的数量。
• 二阶段 - 要求能支持乘方运算并且支持**和^两种乘方表示方式，支持用户通过设置来选择。
• 三阶段 - 要求将软件实用化，做出电脑图形界面程序、智能手机程序、网页程序或者演示动画。
  
  

2. 思路简述

我们使用一棵二叉树来表示一个运算表达式，如此一来，随机的生成二叉树就能够生成四则运算。如下图所示

二叉表达式树

观察得知，一棵二叉表达式树有以下几个特征：

• 1. 全树由算符节点和数值节点组成
• 2. 数值节点为叶子节点
• 3. 由于四则运算为双目运算符，算符节点都拥有左、右子树
• 4. 算符节点数 = 数值节点数 - 1
     
     
     由此，我生成四则运算的思路就是，生成n个数值节点和n-1 个算符节点。
• 1. 两个列表：filled[], unfilled[]分别保存已填充子树的和未填充子树的。
• 2. 初始时，数值节点由于不需要子树，全放入filled中；算符节点由于需要安装子树，都存放在unfilled中。
• 3. 之后，对每个unfilled列表中的元素x，从filled列表中随机取出2个元素作为左右子树，再将x移动到filled列表中。
• 4. 当unfilled为空时，表达式树构造完成。
     
     

去重

题目中有去重的要求。我们的去重方法是生成表达式树时，将表达式的左右子树比较大小（比较输出的字串即可），若右树大于左树，则交换它们（仅应用于满足交换律的乘法、加法）。此操作自底向下递归进行，直至整棵树有序。这样，我们就可以追本溯源，将相同表达式，但异构的树归为一相同的树。

表达式树的归一化


解决了异构问题，我们就使用了Python的集合set()操作，将树转为字符串存入。在产生新的树时，若是集合中已存在，就意味着重复，应当剔除。
去重集合

求值

对表达式求值，同样采用自底向下的方法 。由于任意算符节点都是对左右子树进行运算，应当优先求得子树的值。计算除法时，我们使用Python的Fraction类来实现。Fraction类实现了分数的四则运算，并含有自动约分，为我们的求值提供了极大方便

参数开关

任务要求的参数较多，我们使用getopt库进行参数的识别
在shell中，使用main -h即可显示帮助信息：

  
  Usage:
    -h, print this help, 显示帮助
    -n, num of expressions to generate (default: 4), 生成表达式数量
    -l, num of operators in each expression (default: 4), 每个表达式的算符数
    -e, enable Exponential Operator, 允许指数算符
    -p, Exponential Operator print as '^' rather than '**', 
        指数算符输出为 '^', 而不是'**'3
    -v, verbose output, 冗长输出 - 打印将写入的题目和答案
    -i, interactive mode, 交互模式，允许用户输入答案并得到正误统计

我们的命令行程序支持使用-n 设定生成表达式数量，-l 设定算符数目，-e开关控制是否允许指数算符，-p设置指数算符显示为**还是^
此外，不仅能够输出成文件，还可以加上-v使结果在控制台打印
-i 交互模式是可以用户输入答案，程序统计正误数量

GUI

图形界面的设计，我们选用了方便快捷的PyQt5
Qt丰富的自带控件和独树一帜的信号槽机制使我们方便的编写界面逻辑
我们制作的界面如图所示

答题界面
历史回顾界面
在我们的GUI程序中，可以设置符号数、可以判断用户输入对错、拥有倒计时，倒计时结束后不会一概而论的否决用户的作答，而是将现有输入进行判断对错。
题目历史可以回顾曾经出过的题目，回顾其答案以及当时用户是否正确作答。

3. 单元测试

我们为主要模块的方法都进行了单元测试。我们总计设计了20个测试用例，以尝试发掘模块中潜在的漏洞

单元测试 Green-Across-the-Board

4. 性能分析

我们使用了cProfile对命令行程序进行了整体的性能分析
执行使用shell命令：

python -m cProfile -s cumulative .\src\main.py -n 1000 -e -l 6 -p

这样，我们的命令行程序会生成1000个四则运算，包含指数，算符数为6，指数符号为-^
运行时，cProfile会对我们的程序进行采样，以分析CPU资源消耗。

cProfile性能分析
从结果看出，生成算法中，耗时最长的部分是深拷贝操作（copy.deepcopy）。该操作是去重操作的不可或缺的前置操做，其本身又是Python自带模块，难以进一步优化。

5. 收获体会

这次合作项目，我们2人分工明确，各司其职，最终圆满的完成了任务书中的全部要求。在此我的感受颇丰，激动之心情溢于言表。我从软件设计开始直至单测、性能分析全程参与项目，同组同学也积极完成分配到的任务，不断地优化他的代码，我们一起一次又一次超出了我们一开始对项目的预期。

在项目中，我学得了分工合作的基本要领、实践了课堂所学的软件设计语言和软件设计方法、巩固了Python程序设计的技能。着实为我未来的职业生涯添砖加瓦，巩固了基础。