3119005347叶杞豪 / 31119005341唐振凯

作业github链接

1、PSP表格

2、设计思路

2.1 表达式用二叉树表示

我们平常见到的表达式：3+4×5÷(6-7)+8是一种中缀表达式，表达式可以用二叉树来表示，二叉树有以下特点：

• 非叶子节点表示算术符号，叶子节点表示数
• 非叶子节点的左孩子和右孩子非空
  因此上面表达式转化为二叉树就是
  
  黄色为符号节点，白色为数字节点

2.2 运算符数量控制

因为限定符号数不超过3个，可以用随机函数随机生成一个小于等于3的数，在构建一棵子树的时候顺便算出子树的计算结果和树高

2.3 防止计算过程产生负数

负数的产生是因为减法运算，由于在生成子树的时候会计算结果，可以判断一下结果是否是负数，如果是负数，就取绝对值，即将左右子树互换

2.4 防止题目重复

递归判断两棵表达式树k1、k2, 如果k1和k2的左右子树分别相同，就可以判定k1，k2是两棵相同的树，也就是表达式一样。如果不相同并且符号是＋或者×的时候，再判断k1->left == k2->right && k1->right == k2->left，如果结果为真，说明是相同的一个表达式树。其他情况才是不相同的树，比如

2.5 计算表达式结果

将整数也当做分数来计算，在运算的过程中需要保证分数最简。结果的计算和二叉树的生成同时进行。

3、项目流程和各模块功能

3.1 项目流程图

3.2 项目结构

4、具体实现

1、四则运算过程的具体实现

2、生成二叉树
从根节点开始，向下递归生成左子树和右子树，同时计算表达式结果和树高

3、判断表达式是否重复
两棵表达式树k1、k2的左右子树是否相同，如果相同可以判定表达式重复。如果不相同并且符号是＋或者×的时候，再判断k1->left == k2->right && k1->right == k2->left。

4、输出表达式
按照中序遍历的顺序输出二叉树，形成表达式，同时随机生成括号

5、输出题目到txt文件
给题目加上序号，并按序写进txt文件

6、将作答结果写入txt文件

5、计算模块接口部分的性能

可以发现cpu占用率最高的几个方法都和生成表达式有关，因此生成表达式的算法对程序性能的影响最大

6、计算模块部分单元测试展示

1、生成表达式测试

测试结果：

2、四则运算测试

测试结果：

3、文本读写测试

测试结果：

7、项目功能测试

生成一万道题目：

题目：

答案：

作答情况：

8、小结

叶杞豪：通过本次练习，体会到了二叉树在随机生成表达式和查重方面的巧妙运用，同时通过结队编程，我更深刻地体验到代码规范的重要性。多人结队编程，如果不遵守规范，就会造成组合代码时要花费很多时间。
唐振凯：由于之前从未参与过多人合作项目开发，因此花费了很多功夫进行准备工作。两人合作的好处是形成互补，遇到难题时解决效率会提高。此外积累了一定的合作经验，养成了写注释的习惯。