| 这个作业属于哪个课程 | 计科23级12班 |
|---|---|
| 这个作业要求在哪里 | 作业要求 |
| 这个作业的目标 | 实现一个自动生成小学四则运算题目的命令行程序，并能检验题目答案正确性 |
一、小组&项目信息：
| 姓名 | 学号 |
|---|---|
| 欧俊希 | 3123002980 |
| 梁展榕 | 3123002977 |
github项目地址：https://github.com/iikachan/calc-trainer/tree/master
二、PSP表格
| PSP2.1 | Personal Software Process Stages | 预估耗时（分钟) | 实际耗时（分钟） |
|---|---|---|---|
| Planning | 计划 | 10 | 10 |
| Estimate | 估计这个任务需要多少时间 | 5 | 5 |
| Development | 开发 | 10 | 15 |
| Analysis | 需求分析（包括学习新技术） | 45 | 40 |
| Design Spec | 生成设计文档 | 30 | 40 |
| Design Review | 设计复审 | 10 | 10 |
| Coding Standard | 代码规范（为目前的开发制定合适的规范） | 5 | 5 |
| Design | 具体设计 | 120 | 120 |
| Coding | 具体编码 | 35 | 45 |
| Code Review | 代码复审 | 15 | 20 |
| Test | 测试(自我测试，修改代码，提交修改) | 30 | 40 |
| Reporting | 报告 | 10 | 10 |
| Test Report | 测试报告 | 15 | 20 |
| Size Measurement | 计算工作量 | 5 | 5 |
| Postmortem & Process Improvement Plan | 事后总结，并提出过程改进计划 | 20 | 20 |
| Total | 合计 | 365 | 405 |
三、效能分析
1. 性能改进时间投入
在程序开发过程中，性能改进环节累计花费约1小时，主要针对表达式生成效率和大规模题目处理进行优化。
2. 改进思路
- 减少无效生成：在
generate_mode函数中，通过限制连续失败次数（consecutive_fail）避免因范围过小导致的无限循环，当连续失败100次时及时报错退出。 - 优化分数运算：
Frac类的构造函数中使用std::gcd进行约分，确保分数始终以最简形式存储，减少后续计算的冗余操作。 - 高效去重逻辑：使用
std::set<std::pair<i64,i64>>存储已生成题目的结果（分子+分母），通过键值对快速判断重复，避免全量字符串比对的高开销。
四、设计实现过程
1. 代码组织结构
程序采用模块化设计，主要包含以下核心组件：
-
数据结构：
Frac<T>：模板类，封装分数的存储、运算（加减乘除）、比较和格式化输出，确保分数始终以最简形式存在。ExprNode：结构体，表示表达式树节点，区分数字节点（isNum）和运算符节点（包含左右子树L/R和运算符op）。
-
核心函数模块：
- 表达式生成：
gen_tree通过递归生成随机表达式树，控制运算符数量（1-3个）和数值范围。 - 表达式转换：
tree_to_string将表达式树转为带括号的字符串，确保运算优先级正确。 - 安全计算：
eval_tree_safe递归计算表达式树，检查中间结果是否为负数或除零，确保符合题目要求。 - 解析与评分：
tokenize和Parser处理表达式字符串解析，grade_mode对比题目与答案文件，生成评分结果。 - 主逻辑：
generate_mode生成题目和答案文件，main函数解析命令行参数并分发功能。
- 表达式生成：
2. 模块关系图
3. 数据流向图
4. 关键函数流程图
以gen_tree - 生成表达式树为例：
五、代码说明
1. 分数处理（Frac类）
template <class T>
struct Frac {T p, q; // 分子、分母Frac(T num, T den) : p(num), q(den) {assert(q != 0);if (q < 0) { // 确保分母为正q = -q;p = -p;}T g = std::gcd(p, q); // 约分if (g != 0) {p /= g;q /= g;}}// 运算符重载（以加法为例）Frac operator+(const Frac& f) const { return {p * f.q + f.p * q, q * f.q}; // 通分后相加}// 比较运算符（以小于为例）bool operator<(const Frac& f) const { return p * f.q < f.p * q; // 避免浮点误差，交叉相乘比较}
};
说明：Frac类通过构造函数确保分母为正且分数最简，运算符重载基于分数运算规则实现，比较时采用交叉相乘避免浮点精度问题。
2. 表达式生成与安全计算
// 生成表达式树
std::shared_ptr<ExprNode> gen_tree(std::mt19937& rng, int ops_left, int range) {if (ops_left == 0) { // 叶子节点：生成自然数std::uniform_int_distribution<i64> d(0, std::max(0, range - 1));return std::make_shared<ExprNode>(d(rng));}// 分割运算符到左右子树std::uniform_int_distribution<int> split(0, ops_left - 1);int left_ops = split(rng);int right_ops = ops_left - 1 - left_ops;// 随机选择运算符std::uniform_int_distribution<int> opdist(0, 3);char ops[4] = {'+', '-', '*', '/'};return std::make_shared<ExprNode>(ops[opdist(rng)], gen_tree(rng, left_ops, range), gen_tree(rng, right_ops, range));
}// 安全计算（检查负数和除零）
std::pair<Frac<i64>, bool> eval_tree_safe(const std::shared_ptr<ExprNode>& node) {if (node->isNum) return {Frac<i64>(node->num), true};auto L = eval_tree_safe(node->L);if (!L.second) return {Frac<i64>(0), false};auto R = eval_tree_safe(node->R);if (!R.second) return {Frac<i64>(0), false};if (node->op == '-') {Frac<i64> res = L.first - R.first;if (res.p < 0) return {Frac<i64>(0), false}; // 确保结果非负return {res, true};} else if (node->op == '/') {if (R.first.p == 0) return {Frac<i64>(0), false}; // 避免除零Frac<i64> res = L.first / R.first;if (res.p < 0) return {Frac<i64>(0), false};return {res, true};}// 其他运算符（+、*）处理逻辑类似...
}
说明：gen_tree通过递归控制运算符数量，eval_tree_safe在计算过程中检查减法结果非负、除法无零除数，确保符合题目约束。
3 评分功能（grade_mode）
int grade_mode(const std::string& exer_file, const std::string& ans_file) {// 读取题目和答案文件// ...（文件读取逻辑）for (size_t i = 0; i < m; ++i) {// 提取题目表达式（如从"1. 1 + 2 = "中提取"1 + 2"）std::string expr = ...;Frac<i64> correct = eval_from_string(expr); // 计算正确答案// 解析学生答案（支持整数、真分数、带分数）std::string aexpr = ...;Frac<i64> stud = ...; // 转换答案为Frac类型// 比较并记录结果if (stud == correct) corrects.push_back(i + 1);else wrongs.push_back(i + 1);}// 写入评分结果到Grade.txt
}
说明：评分功能通过解析题目表达式计算正确答案，再将学生答案（支持多种格式）转换为Frac类型比较，最终生成包含对错题编号的评分文件。
六、测试运行
实际测试中的数据已上传至仓库（包含生成的题目，输出的答案和检验文件），这里取其中一份来进行说明：
在该组测试中，我们生成的数据如下：
1. 2 + 17 =
2. (1 + 12) - (5 / 4) =
3. (13 + 7) * (14 * 11) =
4. 6 / 19 =
5. (0 * 13) * 14 =
6. 18 * (15 + 2) =
7. 18 - (19 - 3) =
8. 16 * 17 =
9. 13 / 19 =
10. (15 + 4) + 15 =其输出对应的答案为：
1. 19
2. 11'3/4
3. 3080
4. 6/19
5. 0
6. 306
7. 2
8. 272
9. 13/19
10. 34经人工检查，答案无误，此时检验程序检验结果为：
Correct: 10 (1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
Wrong: 0 ()
修改答案文件如下，题目不变：
1. 20
2. 11'1/2
3. 3080
4. 6/19
5. 0
6. 306
7. 2
8. 262
9. 11/19
10. 34可以看出，我将1,2,8,9的答案修改为错误答案。此时检验程序检验结果为：
Correct: 6 (3, 4, 5, 6, 7, 10)
Wrong: 4 (1, 2, 8, 9)
可以看出，检验程序的结果符合预期，程序运行无误。
七、项目小结
1. 项目的成果与亮点：
本次项目完整实现了小学四则运算题目生成与自动评分的全部核心需求，成果与亮点可概括为三点：
- 功能合规性强：严格遵循题目约束，包括“计算过程无负数”（通过
eval_tree_safe实时校验减法结果）、“除法结果为真分数”（检查除数非零且结果非负）、“运算符数量≤3个”（gen_tree的ops_left参数控制），所有生成题目均符合要求。 - 模块设计明晰：核心组件分工明确，
Frac类封装分数的存储、运算与格式化（如带分数2'3/8的转换），ExprNode结构体统一表达式树节点类型，生成、解析、评分模块独立且可复用，后续扩展只需修改对应模块。 - 性能与容错兼顾：支持10万道题目生成无报错，通过
consecutive_fail限制无效重试（避免范围过小时的死循环）；评分模块具备容错能力，可处理学生答案的多种格式（整数、真分数、带分数），即使答案格式轻微异常（如多余空格）也能正确解析。
2. 项目中遇到的问题：
开发过程中主要遇到两类问题，均通过针对性调整解决：
- 分数运算与格式解析问题：初期解析学生答案中的带分数时，漏处理“整数部分为0”的场景（如0'1/2），导致解析为01/2的错误；后期在
frac_to_output函数中添加“整数部分为0时仅输出真分数”的判断. - 括号优先级解析问题：初期
parse_factor函数仅支持“因子为数字或单一层括号”，无法处理嵌套括号（如((1+2)*3)）；通过重构解析逻辑（用parse_primary递归解析括号内表达式，parse_term/parse_expr处理优先级），修正了括号嵌套的解析错误。
3. 本次结对项目中得到什么经验教训：
- 需求分析应当细化。刚开始认为本次任务要求比较简单，没考虑充分就开始写代码了。写到后面越写越复杂，后来重新分析需求，细化各模块实现才得以完成本次项目。
- 写代码要伴随测试。本次项目中，代码中的部分问题，在多次测试下才被发现，如果不进行充分的测试难以发现代码中的问题。
4. 结对感受：
- 本次结对开发的高效性远超预期，分工互补大大提升了本次作业项目的实现速度。
- 结对编程极大地提高了代码质量，通过即时代码审查减少了bug数量。两人思维的碰撞产生了更好的设计方案，互相学习到了对方的技术特长。沟通和协作是项目成功的关键因素。
5. 闪光点
- 对分数运算的理解深刻，设计了优雅的Frac类，使得整份代码更加规整且易维护。
- 测试用例设计全面，覆盖了各种边界情况。