作业三：结对项目

结对项目

一、作业介绍

这个作业属于哪个课程	班级的链接
这个作业要求在哪里	作业要求的链接
这个作业的目标	完成小学四则运算题目的命令行程序，熟悉项目开发流程，提高团队合作能力

二、成员信息

代码仓库	GitHub
成员1	杨智雄-3122004409
成员2	陈愉锋-3122004387

三、效能分析

各模块耗时

使用Python自带的性能分析模块cProfile进行性能分析。由于答案检查功能只用到单个函数make_correction，性能分析意义较小，故仅对题目生成功能进行性能分析。
在终端中输入对应命令，并以cumtime（指定的函数及其所有子函数从调用到退出消耗的累积时间）降序排序，分别测试在生成100个题目、1000个题目、10000个题目时的程序性能（表达式的数值范围均为[1, 20]），结果如下：
生成100个题目时：

生成1000个题目时：

生成10000个题目时：

生成10w个题目时：

可以看到，在生成100个题目、1000个题目、10000个、10w个题目时，分别耗时0.066s、0.476s、4.517s，45.352s题目生成效率分别为：1515.15题/s、2100.84题/s、2213.86题/s，2204.97题/s,说明生成的题目越多、题目生成的效率越高，不过效率的增加率有略微减缓,这说明代码中的算法已经达到最优，基本呈现O(n)的复杂度，时间消费很低。
分析函数占用的时间，发现在生成100个题目、1000个题目、10000个题目，10w个题目时，函数produce_tree的耗时占总耗时的比例分别为：22.7%、25%、26.3%，26%可以看到：随着题目生成增多，函数produce_tree的耗时占用比例呈线性，无明显变化。

四、设计与实现

1.代码中各类与函数间关系：

主要类	类中主要函数	作用
main	produce_expression check_answer command_line_parser	负责调用其他模块生成表达式和答案，检查文件的答案，和提供命令面板的参数控制
Fraction	to_string_simplified from_string common_denominator gcd add sub mul div	负责操作数的处理层，包括对操作数初始化，化简，通分，和基本的加减乘除运算
BinaryTree	create_tree read_tree calculate_expression transform_tree search_viariant_tree	负责表达式的处理层，用二叉树存放表达式，实现表达式在字符串类型和二叉树形式之间的转换，后序遍历树得到逆波兰表达式配合栈计算结果，以及在二叉树形式上使用生成器寻找所有变体树实现表达式查重
FileUtil	clear_file clear_grade read_exercises write_exercises read_answers write_answers write_grade	负责文件的操作层，具体实现有输入前清空对应文件、将生成的表达式和计算后的答案写入对应文件、读取题目文件和答案文件存入列表、将正确和错误的题目序号存放在成绩文件中

2.流程图：

3.文件结构：

测试结果：

五、代码说明

Main.py

导入argparse

from FileUtil import *
import argparse
random_max=10# 默认值

(函数)通过递归生成表达式 返回值为字符串类型的表达式produce_expression()

def produce_expression():init = random.randint(1, 3)tree_root = create_tree(init)calculate_expression(tree_root)# 这是一步验算if tree_root.error==0 and read_tree(tree_root) not in expressions_list:viariant_trees=search_viariant_tree(tree_root)for viariant_tree in viariant_trees:  # 迭代生成器expressions_list.append(read_tree(viariant_tree))  # 处理并添加生成的表达式return read_tree(tree_root)else:produce_expression()

(函数)检查答案正确性check_answer()

def check_answer(expressions_list,answers_list):for i in range(len(expressions_list)):if answers_list[i] == Fraction().from_string(calculate_expression(transform_tree(expressions_list[i]))).to_string_simplified():right_answers_list.append(i+1)else:wrong_answers_list.append(i+1)

(函数)命令行参数解析command_line_parser()

def command_line_parser():global random_maxparser = argparse.ArgumentParser(description='Fraction arithmetic calculator')parser.add_argument('-n', '--number', type=int, default=0, help='number of exercises')parser.add_argument('-e','--exercise_path', type=str, default=None, help='exercise file path')parser.add_argument('-a','--answer_path', type=str, default=None, help='answer file path')parser.add_argument('-s', '--random_max', type=int, default=None, help='random maximum value')args = parser.parse_args()if args.exercise_path !=  None and args.answer_path != None:FileUtil().clear_grade()FileUtil().read_exercises()FileUtil().read_answers()check_answer(exercises_list,answers_list)FileUtil().write_grade()elif args.exercise_path != None or args.answer_path != None:print("exercise_path and answer_path must be both specified or both not specified")if args.random_max != None :if args.random_max>0:random_max = args.random_max-1else:print("random seed must be a positive integer")if args.number>0:run(args.number)

(函数)生成表达式和对应答案到对应文件中，接口为int类型的生成表达式条数run(n)

def run(n):FileUtil().clear_file()while n>0:test_str=produce_expression()if test_str != None:FileUtil().write_exercises(test_str+"=")root=transform_tree(test_str)result=calculate_expression(root)result=Fraction().from_string(result).to_string_simplified()FileUtil().write_answers(result)n-=1

运行部分

command_line_parser()

BinaryTree.py

初始化列表和运算符字典

from Fraction import *symbols = ['+', '-', '×', '÷']  # 运算符字典
precedence = {'+': 1,'-': 1,'×': 2,'÷': 2}# 优先级字典
expressions_list = []  # 表达式列表
exercises_list = []  # 练习题列表
answers_list = []  # 答案列表
right_answers_list = [] # 正确答案序号列表
wrong_answers_list = [] # 错误答案序号列表

(类)节点的格式

class Node:def __init__(self, value):self.value = valueself.left = Noneself.right = Noneself.error = 0  # 异常标志位：0表示正常，1表示异常 包括负数异常、除数为0异常

(函数)针对四种树型进行随机选择生成 接口为int类型的运算符个数，返回值为节点类型的根节点create_tree(symbols_num)

def create_tree(symbols_num):random_one = random.choice(symbols)root = Node(random_one)  # 创建新的节点root.left = Node(Fraction().to_string_simplified())  # 递归创建左子树root.right = Node(Fraction().to_string_simplified())  # 递归创建右子树if symbols_num > 1:random_two = random.choice(symbols)root2 = Node(random_two)  # 创建新的节点root.left = root2  # 递归创建左子树root2.left = Node(Fraction().to_string_simplified())  # 递归创建左子树root2.right = Node(Fraction().to_string_simplified())  # 递归创建右子树if symbols_num > 2:random_three = random.choice(symbols)root3 = Node(random_three)  # 创建新的节点choice = random.randint(1, 2)if choice == 1:root2.left = root3  # 递归创建左子树root3.left = Node(Fraction().to_string_simplified())  # 递归创建左子树root3.right = Node(Fraction().to_string_simplified())  # 递归创建右子树if choice == 2:root.right = root3  # 递归创建右子树root3.left = Node(Fraction().to_string_simplified())  # 递归创建左子树root3.right = Node(Fraction().to_string_simplified())  # 递归创建右子树return root  # 返回根节点

(函数)中序遍历树实现读取表达式 返回值为字符串类型的表达式 def read_tree(node)

def read_tree(node):str = ""if node is None:return str  # 如果节点为空，则返回if node.left is not None and node.left.value in ['+', '-'] and node.value in ['×', '÷']:str += "("str += read_tree(node.left)str += ")"else:str += read_tree(node.left)str += node.valueif node.right is not None and node.right.value in ['+', '-'] and node.value in ['×', '÷']:str += "("str += read_tree(node.left)str += ")"else:str += read_tree(node.right)return str

(函数)利用后序遍历树和栈结构计算表达式的值 返回值为字符串类型的结果calculate_expression(tree_root)

def calculate_expression(tree_root):# 栈压入的是字符串stack = []def dfs(node):if node is None:returndfs(node.left)dfs(node.right)stack.append(node.value)if stack[-1] == '+':stack.pop()str = Fraction().add(stack.pop(), stack.pop())stack.append(str)if stack[-1] == '-':stack.pop()str = Fraction().sub(stack.pop(), stack.pop())if 'fail' in str:tree_root.error = 1stack.append("-1")# print("出现了负数异常 ")returnstack.append(str)if stack[-1] == '×':stack.pop()str = Fraction().mul(stack.pop(), stack.pop())stack.append(str)if stack[-1] == '÷':stack.pop()str = Fraction().div(stack.pop(), stack.pop())if 'fail' in str:tree_root.error = 1stack.append("-1")# print("出现了除数为0异常")returnstack.append(str)dfs(tree_root)return stack.pop()

(函数)把表达式转化为树,接口为字符串类型的表达式，返回值为树的根节点transform_tree(expression)

def transform_tree(expression):# 去除等于号字符expression = expression.replace("=", "")optr_stack = []  # 运算符栈expt_stack = []  # 表达式树的根节点栈current_number = ''for char in expression:if char.isdigit() or char == '\'' or char == '/':  # 处理数字或分数current_number += charelse:if current_number:expt_stack.append(Node(current_number))  # 创建数字节点并入栈current_number = ''if char in symbols:  # 如果是运算符while (optr_stack and optr_stack[-1] != '(' andprecedence[char] <= precedence[optr_stack[-1]]):# 弹出运算符，构造树top_op = optr_stack.pop()right_node = expt_stack.pop()left_node = expt_stack.pop()operator_node = Node(top_op)operator_node.left = left_nodeoperator_node.right = right_nodeexpt_stack.append(operator_node)  # 重新将构造的树根节点压入expt栈optr_stack.append(char)  # 将当前运算符压入运算符栈elif char == '(':optr_stack.append(char)  # 左括号直接入运算符栈elif char == ')':while optr_stack and optr_stack[-1] != '(':# 弹出运算符，构造树top_op = optr_stack.pop()right_node = expt_stack.pop()left_node = expt_stack.pop()operator_node = Node(top_op)operator_node.left = left_nodeoperator_node.right = right_nodeexpt_stack.append(operator_node)  # 重新将构造的树根节点压入expt栈optr_stack.pop()  # 弹出左括号if current_number:  # 处理最后一个数字expt_stack.append(Node(current_number))# 处理栈中剩余的内容while optr_stack:top_op = optr_stack.pop()right_node = expt_stack.pop()left_node = expt_stack.pop()operator_node = Node(top_op)operator_node.left = left_nodeoperator_node.right = right_nodeexpt_stack.append(operator_node)  # 将新形成的子树放回栈return expt_stack[0] if expt_stack else None  # 返回根节点

(函数)把根节点对应的树进行变换 把树中所有加号和乘号的左右子树交换的情况 返回值为所有变体树的根节点生成器 比如(1+2)×3有3种变体(2+1)*3,3*(1+2),3*(2+1),在表达式形式上都是顺序问题，实现了O(n)的实现复杂度search_viariant_tree(node)

def search_viariant_tree(node):if node == None:return Noneif node.value == '-' or node.value == '÷' or (node.left.value not in symbols and node.right.value not in symbols):return nodeleft_trees = search_viariant_tree(node.left)right_trees = search_viariant_tree(node.right)# 如果当前节点是乘法或加法if node.value == '+' or node.value == '×':for left_tree in left_trees:for right_tree in right_trees:new_tree = Node(node.value)new_tree.left = left_treenew_tree.right = right_treeyield new_treefor left_tree in left_trees:for right_tree in right_trees:new_tree = Node(node.value)new_tree.left = right_treenew_tree.right = left_treeyield new_treeelse:# 处理左子树for left_tree in left_trees:new_tree = Node(node.value)new_tree.left = left_treenew_tree.right = node.rightyield new_tree# 处理右子树for right_tree in right_trees:new_tree = Node(node.value)new_tree.left = node.leftnew_tree.right = right_treeyield new_tree

FileUtil.py

(类)包含五种文件读写函数和一种清空文件函数 主要负责文件的处理层

导入二叉树类的函数

from BinaryTree import *

(函数)清空题目文件和答案文件clear_file(self)

def clear_file(self):with open("exercises.txt", 'r+') as file:file.truncate(0)with open("answers.txt", 'r+') as file:file.truncate(0)

(函数)清空成绩文件clear_grade(self)

def clear_grade(self):with open("grade.txt", 'r+') as file:file.truncate(0)

(函数)读取题目文件read_exercises(self)

def read_exercises(self):with open('exercises.txt', 'r', encoding="utf-8") as f:for line in f:exercises_list.append(line.strip().replace("=", ""))

(函数)读取答案文件read_answers(self)

def read_answers(self):with open('answers.txt', 'r', encoding="utf-8") as f:for line in f:answers_list.append(line.strip())

(函数)写入题目文件write_exercises(self, str)

def write_exercises(self, str):with open('exercises.txt', 'a', encoding="utf-8") as f:f.write(str + "\n")

(函数)写入答案文件write_answers(self, str)

def write_answers(self, str):with open('answers.txt', 'a', encoding="utf-8") as f:f.write(str + "\n")

(函数)写入成绩文件write_grade(self)

def write_grade(self):with open('grade.txt', 'a', encoding="utf-8") as f:f.write(f"Right:{len(right_answers_list)}{right_answers_list}\nWrong:{len(wrong_answers_list)}{wrong_answers_list}\n")

Fraction.py

（类）包含各种数据的格式转换函数 还有数据的随机生成和运算功能 主要负责对分数的格式、生成、运算

导入二叉树类的函数

from BinaryTree import *

点击查看代码

def clear_file(self):with open("exercises.txt", 'r+') as file:file.truncate(0)with open("answers.txt", 'r+') as file:file.truncate(0)

点击查看代码

点击查看代码

点击查看代码

点击查看代码

六、测试运行

10项针对不同函数的测试：

七、PSP表格

PSP2.1	Personal Software Process Stages	预估耗时（分钟）	实际耗时（分钟）
Planing	计划	40	30
.Estimate	.估计这个任务需要多久时间	30	30
Development	开发	110	150
.Analysis	.需求分析 (包括学习新技术)	30	35
.Design Spec	.生成设计文档	30	35
.Design Review	.设计复审	30	45
.Coding Standrd	.代码规范（为目前的开发制定合适的规范）	15	25
.Design	.具体设计	40	50
.Coding	.具体编码	350	420
.Code Review	.代码复审	20	15
.Test	.测试（自我测试，修改代码，提交修改）	60	70
.Reporting	报告	80	75
.Test Report	.测试报告	30	30
.Size Measurement	.计算工作量	30	20
.Postmortem&Process Improvement	.事后总结，并提出过程改进计划	30	35
	.合计	885	1000

八、项目小结

杨智雄：在项目刚开始选择使用不熟悉的python实现项目，是因为上次个人项目里面python自带库使用很便利，没想到在这次项目中没有发挥它的优势，还吃了不熟悉它的苦头，还好这次项目任务难度可以接受，学习到了挺多的知识，也对面向对象的理解更加深刻。在项目构想初期本来是计划将二人把实现过程规划好后划分功能然后分工实现，然后因为对语言不熟悉，也是第一次团队合作致使计划没能顺利发展，期待下次可以更好的合作，学会在团队实现项目。

陈愉锋：在刚接触项目时我有点迷茫，在查阅资料与搭档的交流后，我逐渐理解了项目的大致思路，完成项目后我对于后缀表达式与树的理解变得更加深刻。这次的结对项目主要都是杨智雄操刀，他是一个优秀的搭档，有了他的帮助，我才得以完成这个任务，同时他也教了我很多新的知识。