廖永祺
谭钧灏 3123004628
GitHub项目地址：
| 这个作业属于哪个课程 | <班级的链接> |
|---|---|
| 这个作业要求在哪里 | https://edu.cnblogs.com/campus/gdgy/Class12Grade23ComputerScience/homework/13470 |
| 这个作业的目标 | 熟悉小组合作的形式并在该形式中思考团队完成开发任务时需考虑的具体细节 |
PSP表格
| PSP2.1 | Personal Software Process Stages | 预估耗时（分钟） | 实际耗时（分钟） |
|---|---|---|---|
| Planning | 计划 | 15 | 10 |
| · Estimate | · 估计这个任务需要多少时间 | 15 | 10 |
| Development | 开发 | 165 | 155 |
| · Analysis | · 需求分析（包括学习新技术） | 20 | 15 |
| · Design Spec | · 生成设计文档 | 10 | 8 |
| · Design Review | · 设计复审 | 5 | 5 |
| · Coding Standard | · 代码规范（为目前的开发制定合适的规范） | 10 | 12 |
| · Design | · 具体设计 | 25 | 22 |
| · Coding | · 具体编码 | 60 | 70 |
| · Code Review | · 代码复审 | 15 | 13 |
| · Test | · 测试（自我测试，修改代码，提交修改） | 20 | 10 |
| Reporting | 报告 | 20 | 20 |
| · Test Report | · 测试报告 | 10 | 10 |
| · Size Measurement | · 计算工作量 | 5 | 5 |
| · Postmortem & Process Improvement Plan | · 事后总结，并提出过程改进计划 | 5 | 5 |
| 合计 | 200 | 185 |
效能分析
函数性能消耗分布 (基于算法复杂度):
| 排名 | 函数名 | 占比 | |
|---|---|---|---|
| 1 | ExpressionGenerator.generateCompoundExpr | 32% | |
| 2 | AnswerValidator.parseExpression | 28% | |
| 3 | Fraction.gcd() | 15% | |
| 4 | ExpressionGenerator.normalizeExpression | 10% | |
| 5 | AnswerValidator.parseWithoutBrackets | 8% | |
| 6 | FileHandler.readFileLines | 4% | |
| 7 | Fraction.valueOf() | 2% | |
| 8 | Other Functions | 1% |
能耗第一名：ExpressionGenerator.generateCompoundExpression()
性能消耗原因：
递归调用导致调用栈深度
约束检查失败时的重试循环
运算符数量增加时复杂度急剧上升
generateCompoundExpression() - 32% load
├── Complexity: O(2^n) - 指数级增长
├── Avg call depth: 3-5 levels
├── Memory alloc: 2-5KB/call
├── Issue: 递归+重试循环
└── Recommendation: 添加重试限制
能耗第二名：
性能消耗原因：
深度递归解析嵌套表达式
频繁的字符串拼接和子串操作
括号匹配的线性扫描
parseExpression() - 28% load
├── Complexity: O(n²) - 字符串操作
├── Max recursion: 10+ levels
├── Memory alloc: 1-3KB/call
├── Issue: 深度递归风险
└── Recommendation: 改为迭代算法
能耗第三名：Fraction.gcd()
性能消耗原因：
每个分数构造时调用
每次运算后构造新分数时调用
大数时迭代次数增加
gcd() - 15% load
├── Complexity: O(log(min(a,b)))
├── Calls: 高频调用 (每个分数运算)
├── Issue: 大数性能下降
└── Optimization: 已较好优化
优化方案
一、算法优化（2-3小时）
1.递归改用迭代的表达式
2.优化括号匹配算法
3.改进表达式规范化
二、设备优化（硬件设施更换）
1.优化并行处理支持
2.优化内存的使用
系统架构设计和代码说明
核心组件
1.主控制器(MathExerciseGenerator)
组件说明：函数先对终端输入的参数进行解析并判断，匹配对应的模式，随后在对应模式下选择生成题目或者验证答案，最后输出文件。
表达式生成器
组件说明：应用builder模式和composite模式，构建表达式树以及逐步构建复杂数学表达式
核心算法设计
1.表达树生成算法
算法说明：表达式树生成算法采用递归分治策略，将复杂表达式的生成问题分解为更小的子问题，通过组合子树来构建完整的表达式树。
入口控制 - generateUniqueProblem()
| 步骤顺序 | 任务 |
|---|---|
| 1 | 启动生成流程 |
| 2 | 循环尝试生成（防止无限循环） |
| 3 | 调用 generateExpression(3) 生成表达式树 |
| 4 | 进行表达式规范化处理 |
| 5 | 检查唯一性（HashSet去重） |
| 6 | 返回合格的MathProblem对象 |
递归生成 - generateExpression(maxOperators)
| 步骤顺序 | 任务 |
|---|---|
| 1 | 输入：最大运算符数量 |
| 2 | 判断：如果maxOperators=0 或 10%概率 → 生成叶子节点（基本表达式） |
| 3 | 否则 → 生成复合表达式（generateCompoundExpression） |
| 4 | 返回：Expression对象（包含表达式字符串和计算结果） |
复合表达式生成 - generateCompoundExpression(operators)
情况1：operators = 1（单运算符）
├── 选择随机运算符（+、-、×、÷）
├── 生成左操作数 generateBasicExpression()
├── 生成右操作数 generateBasicExpression()
├── 验证运算约束（减法非负、除法真分数）
└── 构建表达式 "(左 运算符 右)"
情况2：operators > 1（多运算符）
├── 分割运算符数量：左子树 ← random(1, operators-1)
├── 计算右子树：operators - 左子树 - 1
├── 递归生成左子树 generateExpression(左子树)
├── 递归生成右子树 generateExpression(右子树)
├── 选择随机运算符
├── 验证运算约束
└── 构建表达式 "(左子树 运算符 右子树)"
基本表达式生成 - generateBasicExpression()
随机选择类型：
├── 50%概率：生成整数
│ └── 范围：[1, range-1]
│
└── 50%概率：生成分数
├── 分母：随机[2, range-1]
├── 分子：随机[1, 分母-1]（确保真分数）
└── 50%概率转为带分数
├── 整数部分：随机[1, range-2]
└── 组合：整数部分'分子/分母
算法复杂度分析
时间复杂度
最好情况：O(1) - 直接生成基本表达式
最坏情况：O(2^n) - 递归生成复合表达式
平均情况：O(n) - 受最大运算符数限制
空间复杂度
调用栈：O(n) - 递归深度
内存使用：O(m) - 唯一表达式存储
2.表达树解析算法
主解析入口 - parseExpression(expr)
| 步骤顺序 | 任务 |
|---|---|
| 1 | 输入：表达式字符串并移除所有空白字符 |
| 2 | 检查表达式是否为空 |
| 3 | 查找最外层括号位置 |
| 4 | 如果找到括号，则定位匹配并递归解析括号内容，随后用计算结果替换括号内容，生成新的表达式 |
| 5 | 如果没有括号，则调用 parseWithoutBrackets(expr) 解析无括号表达式 |
| 6 | 返回：Fraction计算结果 |
括号匹配算法 - findMatchingBracket(expr, start)
输入：表达式字符串和左括号位置
↓
初始化括号计数器 bracketCount = 1
↓
从左括号后一个字符开始遍历：
├── 遇到 '(' → bracketCount++
├── 遇到 ')' → bracketCount--
├── 遇到 ''' → 跳过带分数部分（避免误判）
├── 当bracketCount = 0时 → 找到匹配右括号
└── 继续遍历直到找到匹配或字符串结束
↓
返回：匹配右括号位置，未找到返回-1
分数解析算法 - parseFraction(str)
输入：分数字符串
↓
检查是否包含 "'"（带分数）：
├── 是：按 "'" 分割为整数部分和分数部分
├── 解析整数部分
├── 递归解析分数部分
├── 计算：整数部分 + 分数部分
└── 返回组合结果
↓
检查是否包含 "/"（普通分数）：
├── 是：按 "/" 分割为分子和分母
├── 验证分母不为0
├── 创建Fraction对象
└── 返回分数
↓
否则（整数）：
├── 解析为整数
├── 创建Fraction(整数, 1)
└── 返回结果
算法复杂度分析
时间复杂度
最好情况：O(n) - 简单表达式线性扫描
最坏情况：O(n²) - 深度嵌套括号，多次字符串操作
平均情况：O(n log n) - 递归解析平衡的表达式树
空间复杂度
调用栈：O(d) - d为括号嵌套深度
临时存储：O(n) - 分词列表和临时字符串
测试运行
测试数据
测试结果
测试成绩
对于题目的生成：
生成完全按照要求所给的参数生成，同时满足没有负数和其他不合适的符号，题目也没有产生重复或者空白。
对于题目的判断：
判断按照要求对真分数进行额外的识别，加之整数的运算判断，并且根据输入的答案判断出正确和错误的对应题号，符合作业要求。