Github项目地址传送门
个人博客传送门

项目相关要求

1. (完成)使用 -n 参数控制生成题目的个数。
2. (完成)使用 -r 参数控制题目中数值&＃xff08;自然数、真分数和真分数分母&＃xff09;的范围。该参数可以设置为1或其他自然数。该参数必须给定&＃xff0c;否则程序报错并给出帮助信息。
3. (完成)生成的题目中计算过程不能产生负数&＃xff0c;也就是说算术表达式中如果存在形如e1 − e2的子表达式&＃xff0c;那么e1 ≥ e2。
4. (完成)生成的题目中如果存在形如e1 ÷ e2的子表达式&＃xff0c;那么其结果应是真分数。
5. (完成)每道题目中出现的运算符个数不超过3个。
6. (完成)程序一次运行生成的题目不能重复&＃xff0c;即任何两道题目不能通过有限次交换&＃43;和×左右的算术表达式变换为同一道题目。例如&＃xff0c;23 &＃43; 45 &＃61; 和45 &＃43; 23 &＃61; 是重复的题目&＃xff0c;6 × 8 &＃61; 和8 × 6 &＃61; 也是重复的题目。3&＃43;(2&＃43;1)和1&＃43;2&＃43;3这两个题目是重复的&＃xff0c;由于&＃43;是左结合的&＃xff0c;1&＃43;2&＃43;3等价于(1&＃43;2)&＃43;3&＃xff0c;也就是3&＃43;(1&＃43;2)&＃xff0c;也就是3&＃43;(2&＃43;1)。但是1&＃43;2&＃43;3和3&＃43;2&＃43;1是不重复的两道题&＃xff0c;因为1&＃43;2&＃43;3等价于(1&＃43;2)&＃43;3&＃xff0c;而3&＃43;2&＃43;1等价于(3&＃43;2)&＃43;1&＃xff0c;它们之间不能通过有限次交换变成同一个题目。生成的题目存入执行程序的当前目录下的Exercises.txt文件。
7. (完成)在生成题目的同时&＃xff0c;计算出所有题目的答案&＃xff0c;并存入执行程序的当前目录下的Answers.txt文件。
8. (完成)程序应能支持一万道题目的生成。
9. (完成)程序支持对给定的题目文件和答案文件&＃xff0c;判定答案中的对错并进行数量统计&＃xff0c; 统计结果输出到文件Grade.txt。

代码规范

本次项目的代码遵循了谷歌代码规范(C&＃43;&＃43;)&＃xff0c;但由于谷歌代码规范篇幅太多&＃xff0c;所以我们目前只遵循了其中的部分规范&＃xff0c;具体如下&＃xff1a;

1. 禁止使用宏
2. 分号以前不加空格
3. 行宽原则上不超过80
4. 一行只定义一个变量
5. 左大括号前保留一个空格
6. if, else前后都要一个空格
7. for, while后要有一个空格
8. return 后面的数值不加 ( )
9. 每个文件应该含有版权信息及作者
10. 左圆括号之后和右圆括号之前无空格
11. 函数参数过多时&＃xff0c;每行的参数变量对齐
12. 一目运算符与变量之间不加空格符隔开
13. 禁止使用 using 指示&＃xff08;using-directive&＃xff09;
14. 禁止使用C&＃43;&＃43;的流&＃xff0c;而是用printf之类的替代
15. 要么函数名与参数同行&＃xff0c;要么所有参数并排分行
16. 换行代码缩进2个空格&＃xff0c;并且使用两个空格符取代制表符
17. 二目以上的运算符与变量&＃xff0c;常量之间用空格隔开&＃xff08;各类括号除外&＃xff09;
18. 不论控制语句&＃xff0c;循环语句后面的循环体有多少行&＃xff0c;都必须使用花括号
19. 普通函数&＃xff0c;类型&＃xff08;含类与结构体&＃xff0c;枚举类型&＃xff09;&＃xff0c;常量等使用大小写混合&＃xff0c;不含下划线
20. 除函数定义的左大括号可置于行首以外&＃xff0c;包括函数/类/结构体/枚举声明&＃xff0c;各种语句的左大括号必须置于行末&＃xff0c;所有右大括号独立成行

设计思路

具体设计&关键代码

ImproperFraction类

构建一个ImproperFraction的类&＃xff0c;然后重载这个类的四种运算 &＃43;-x÷ 以及以及六种逻辑关系&＃39;<&＃39; &＃39;&＃61;&＃61;&＃39; &＃39;<&＃61;&＃39; &＃39;!&＃61;&＃39; &＃39;>&＃39; &＃39;>&＃61;&＃39;判断&＃xff0c;在后续的代码编写之中都是基于这个类进行运算

核心代码如下&＃xff1a;

class ImproperFraction {public :ImproperFraction(){}ImproperFraction (int Mole, int Deno, int Coef &＃61; 0) {int g &＃61; std::__gcd (Mole, Deno);g &＃61; std::max(g, 1);mole &＃61; (Mole &＃43; Coef * Deno) / g;deno &＃61; Deno / g;}ImproperFraction operator &＃43; (const ImproperFraction & rhs ) const {int DENO &＃61; deno * rhs.deno;int MOLE &＃61; mole * rhs.deno &＃43; rhs.mole * deno;ImproperFraction res &＃61; ImproperFraction (MOLE, DENO);return res;}ImproperFraction operator - (const ImproperFraction & rhs ) const {int DENO &＃61; deno * rhs.deno;int MOLE &＃61; mole * rhs.deno - rhs.mole * deno;ImproperFraction res &＃61; ImproperFraction (MOLE, DENO);return res;}ImproperFraction operator * (const ImproperFraction & rhs ) const {int DENO &＃61; deno * rhs.deno;int MOLE &＃61; mole * rhs.mole;ImproperFraction res &＃61; ImproperFraction (MOLE, DENO);return res;}ImproperFraction operator / (const ImproperFraction & rhs ) const {int DENO &＃61; deno * rhs.mole;int MOLE &＃61; mole * rhs.deno;ImproperFraction res &＃61; ImproperFraction (MOLE, DENO);return res;}bool operator <(const ImproperFraction & rhs ) const {return mole * rhs.deno (const ImproperFraction & rhs ) const {return !((*this) <&＃61; rhs);}bool operator >&＃61; (const ImproperFraction & rhs ) const {return (*this) > rhs || (*this) &＃61;&＃61; rhs;}private :int mole &＃61; 0; // 分子int deno &＃61; 1; // 分母
};

题集的生成

表达式的生成

在这里选择的是rand() 随机生成 运算符个数&＃xff0c;类型以及每个被运算的数值。

表达式的合法性判断

在生成过程之中&＃xff0c;有两个要点会导致表达式非法
1.运算过程中出现负值
2.在÷运算后面出现0

解决办法&＃xff1a;两个特殊判断即可

表达式的去重

表达式的重复有两种情况:
1.完完全全的重复&＃xff0c;如出现两个1 &＃43; 2 &＃43; 3 的表达式
2.运算顺序上的重复&＃xff0c;如:

1 &＃43; 2 &＃43; 3 和 2 &＃43; 1 &＃43; 3重复
2 &＃43; 3 x 4 和 4 x 3 &＃43; 2重复

解决办法&＃xff1a;
对于(1)的情况只需要将生成的表达式保存进C&＃43;&＃43;STL的set之中即可自动去重。
对于(2)的情况&＃xff0c;则是按照一定规则生成表达式来避免这一情况&＃xff0c;规则如下&＃xff1a;

1.默认左边的运算符的优先度高于右边
2.第一个数字一定不小于第二个数值
因此1 &＃43; 2 &＃43; 3和2 &＃43; 3 x 4不会被生成&＃xff0c;而只会生成2 &＃43; 1 &＃43; 3和4 x 3 &＃43; 2

题集无法生成要求的数量

例如&＃xff1a;
传入的参数是 -n 10000 -r 1 的时候&＃xff0c;很明显无法生成10000道题目&＃xff0c;因此陷入死循环的生成中

解决办法&＃xff1a;
设置一个时间戳time&＃xff0c;当生成表达式的部分循环了1000000次之后自动跳出循环&＃xff0c;终止生成表达式

答案的生成

在表的是合法性判断的时候&＃xff0c;会判断最终的数值是否小于0&＃xff0c;在这里就已经计算标准答案&＃xff0c;保存并打印到answer.txt即可

核心代码如下&＃xff1a;

void questionSetGenerate (int limit, int number) {std::setexpressions;std::vectorexercise;std::vectoranswer;ImproperFraction zero &＃61; ImproperFraction(0, 1);// 时间戳int time &＃61; 0;while (expressions.size() sz) {//保存题集和答案exercise.push_back(addbrackets(exp));answer.push_back(res);}}}
}

答案正确性的检测

用户通过参数-e exercises.txt -a answers.txt&＃xff0c;传进来了题目文件的名称和答案文件的名称。
首先&＃xff0c;由于文件可能不存在或者没有访问的权限&＃xff0c;我们需要对此进行检查&＃xff0c;假如有错误&＃xff0c;则进行报错&＃xff0c;没有异常才进行下一步。
第二步&＃xff0c;我们需要对exercises.txt文件中的题目计算一遍&＃xff0c;然后再和answers.txt文件中的答案进行比较。题目的计算分两步进行&＃xff0c;即先将中缀表达式转化为后缀表达式&＃xff0c;然后计算后缀表达式的答案。
对于这个函数&＃xff0c;我们考虑了exercises.txt行数和answers.txt行数不相等的情况&＃xff0c;此时我们将以exercises.txt的行数为准&＃xff0c;假如answers.txt行数过少&＃xff0c;那么将视为错误答案&＃xff0c;假如过多&＃xff0c;那么将被忽略。

// 检查答案
void checkAnswer(FILE *exerciseFile, FILE *answerFile) {FILE *pFile &＃61; getPointerToGradeFile();int problemID &＃61; 0;char answer[256];char exercise[256];std::vector wrongID;std::vector correctID;// 答案的行数可能不等于题目的行数while (fgets(answer, 256, answerFile)) {if (!fgets(exercise, 256, exerciseFile)) {break;}problemID&＃43;&＃43;;removeRedundantPart(answer, exercise);handleDivideEncoding(exercise);if (getInfixExpressionAnswer(exercise) &＃61;&＃61; stringToImproperFraction(answer)) {correctID.push_back(problemID);} else {wrongID.push_back(problemID);}}while (fgets(exercise, 256, exerciseFile)) {problemID&＃43;&＃43;;wrongID.push_back(problemID);}printID(pFile, const_cast("Correct"), correctID);printID(pFile, const_cast("Wrong"), wrongID);fclose(pFile);printf("Check answer done!\n");
}


// 将中缀表达式转化为后缀表达式
std::queue transformInfixExprToSuffixExpr(const std::string &InfixExpression) {std::stack temp;std::queue result;for (int i &＃61; 0; i }

// 计算后缀表达式的答案
ImproperFraction getSuffixExpressionAnswer(std::queue suffixExpression) {std::stack sta;while (!suffixExpression.empty()) {std::string s &＃61; suffixExpression.front();suffixExpression.pop();if (isOperator(s)) {// 假如遇到运算符&＃xff0c;就取出栈顶元素进行计算ImproperFraction a &＃61; sta.top();sta.pop();ImproperFraction b &＃61; sta.top();sta.pop();if (s[0] &＃61;&＃61; &＃39;x&＃39;) {sta.push(a * b);} else if (s[0] &＃61;&＃61; &＃39;\xc3&＃39;) {sta.push(b / a);} else if (s[0] &＃61;&＃61; &＃39;&＃43;&＃39;) {sta.push(a &＃43; b);} else {sta.push(b - a);}} else {// 假如遇到数字&＃xff0c;就直接进栈sta.push(stringToImproperFraction(s));}}return sta.top();
}


测试报告

首先是各种参数错误的测试

接着是传入正确的参数的测试

生成题集的测试&＃xff1a;

给定的题目文件和答案文件&＃xff0c;判定答案中的对错测试&＃xff1a;

效能分析

本程序主要由生成运算题目和检查答案正确性两个模块&＃xff0c;因此效能分析也主要针对这两个模块进行。
1. 生成运算题目
生成一百万条题目时候的时间占比情况&＃xff1a;

由上图看出了&＃xff0c;占用时间最多的前五个函数为

1. questionSetGenerate
2. gcd
3. addbrackets
4. digToString
5. ImproperFraction

其中&＃xff0c;questionSetGenerate是生成运算题目的函数入口&＃xff0c;占用时间最长。gcd是在题目运算过程&＃xff0c;分数通分时进行调用的&＃xff0c;具体实现是辗转相除法。addbrackets是在生成题目的过程给表达式添加括号。digTostring是在生成题目的过程将数字转化为字符串。ImproperFraction是真分数的类名&＃xff0c;由于生成的表达式中普遍含有真分数&＃xff0c;所以多次调用了它的构造函数。

2. 检查答案正确性
检查五十万条题目时的时间占比情况&＃xff1a;

由上图可以看出&＃xff0c;占用时间最多的前五个函数为&＃xff1a;

1. gcd
2. stringToImproperFraction
3. __deque_buf_size
4. transformInfixExprToSuffixExpr
5. _Deque_base

其中&＃xff0c;gcd用于运算过程的通分&＃xff0c;stringToImproperFraction用于将字符串转化为真分数&＃xff0c; transformInfixExprToSuffixExpr用于将中缀表达式转化为后缀表达式。另外两个函数是系统函数。

因此&＃xff0c;假如要优化效能的话&＃xff0c;可以优先在源代码追踪一下上述函数&＃xff0c;看能否减少这些函数的调用或者优化其实现方式。

PSP

PSP2.1	Personal Software Process Stages	预估耗时&＃xff08;分钟&＃xff09;	实际耗时&＃xff08;分钟&＃xff09;
Planning	计划	60	50
· Estimate	· 估计这个任务需要多少时间	60	50
Development	开发	965	1545
· Analysis	· 需求分析 (包括学习新技术)	50	100
· Design Spec	· 生成设计文档	25	35
· Design Review	· 设计复审 (和同事审核设计文档)	25	35
· Coding Standard	· 代码规范 (为目前的开发制定合适的规范)	25	65
· Design	· 具体设计	60	80
· Coding	· 具体编码	360	415
· Code Review	· 代码复审	60	150
· Test	· 测试&＃xff08;自我测试&＃xff0c;修改代码&＃xff0c;提交修改&＃xff09;	360	665
Reporting	报告	110	130
· Test Report	· 测试报告	60	80
· Size Measurement	· 计算工作量	25	25
· Postmortem & Process Improvement Plan	· 事后总结, 并提出过程改进计划	25	25
合计		1135	1725

项目小结

有待改进的地方

溢出问题&＃xff1a;当给定r过大的时候&＃xff0c;将会导致最终运算结构的分母溢出&＃xff0c;而造成的数据错误
目前方案&＃xff1a;检查溢出&＃xff0c;将发生了溢出的表达式删除
更佳方案&＃xff1a;使用大数的运算&＃xff0c;就可以完美避免数据溢出的问题

生成题目不够友好&＃xff1a;当给定数据范围r稍稍有点大的时候&＃xff0c;最终答案的分母可能超过一亿
目前方案&＃xff1a;不处理
更佳方案: 暂无

死循环生成题目: 当给定题数过大且给定限制太小时,无法生成要求的题目数量, 导致进入死循环
目前方案: 设置时间戳time,只生成1000000次表达式,再进行合法性判断,但也导致有可能无法生成要求题目数量
更佳方案: 暂无

开发项目中发生的问题

1. 一开始的时候是选择暴力深搜生成题集,再随机选取表达式输出,但是生成的效果来看,题目并不是很随机,例如前两个数字是固定死的,思前想后,觉得还是使用rand()随机生成效果更佳
2. 在最开始设计方案的时候,还是思虑的不够多,以至于后面的代码复审(Debug)工作做了很多,远超过代码编写部分
3. 还有各种人性化的设置,如参数错误提示,程序运行结果显示之类话语并没有想到,但是一个软件,一个项目最终都是面向于人群大众,人性化的设置是必须的

团队之中的闪光点

1. 良好的代码风格: 在一开始我们就约束好了团队的代码风格,在后续的代码编写之中我们也能够很好的参照代码风格进行书写,因此在代码复审的时候我们也能够很好的查阅对方的代码
2. 不错的代码能力: 想定思路学习知识之后,可直接进行代码的实现,基本上不会出现一些逻辑错误.后面出现的bug也是因为设计的时候稍稍不够考虑细节,一旦出现bug,都能够立马找到bug和想到相应的修复方案
3. 互帮互助: 在一开始我们就进行了分工,一个人主要负责对给定的题目文件和答案文件进行答案校对、参数组合正确性的检测&＃xff0c;另一个人负责了题集的生成部分。并且在最后&＃xff0c;一起测试并撰写了博客。
   通过这次项目&＃xff0c;我们实践了结对编程&＃xff0c;提高了沟通能力&＃xff0c;加强了团队合作的能力。