写在前面:关于结对编程
结对编程我一直认为是一种非常好的合作方式,他的形式主要是由一个人负责代码编写,另一个人则在一旁即时对写下的代码进行审查,这样可以大大减少代码实现方面的错误。
这次我的结对伙伴是小芦荟(学号后四位为1221)。他平时喜欢打篮球,打的也挺不错的,三国杀也是高手(都100多级了),是一个比较靠谱的人。但是在编程这方面他可能不太擅长,因此这次结对项目就变成了我一个人写,他在旁边看着……不过有时他也会指出我的代码中非常明显的问题,这也保证了我的代码正确性较高。设计的单元测试几乎全是一次通过。
附结对编程图片:
关于Design by Contract、Information Hiding
本次结对项目要求对上次的个人项目进行封装,并写一个界面来调用这些封装好的函数。这就需要我们对相关接口制定一个规范,我和另一个队伍(pair16)的同学约定好了代码接口,便于之后的测试。
对于Information Hiding原则,我们这次其实做的并不好,所有的类属性也均为public,这主要考虑到本次程序会封装为程序编写的方便。
我们core部分均采用Win32 Console Application实现,图形界面部分均采用MFC Application实现。core编写完成,测试完成后,生成dll并提供两个接口,用来实现要求的两个功能。接口的定义均提前约定。
关于接口定义、dll封装的具体内容在第二篇博客中会详细介绍。
设计与实现
算法设计
我们本次项目沿用了上次我的个人项目的设计,只不过在其基础上添加了对负数、有无括号、有无乘除法的限制,以及对运算符个数的限制。
具体来说,对于四则运算题目生成的部分:
- 获取到传入的参数限制,包括运算符个数限制、数值限制、有无分数、有无负数
- 递归生成一个表达式树
- 递归进行表达式的正确性检验(是否出现了负数、除0以及不能整除的情况)
- 递归对表达式树进行最小表示
- 如果得到的算式之前没有生成过,则将该算式加入到生成队列中。
- 如果当前的表达式个数已经达到要求,则将表达式与答案返回。
其中,在生成表达式树的过程中,首先需要判断树中当前的节点是否为分支节点(即运算符)。如果当前的树的总结点数为0,那么该节点必须为分支节点,如果当前树中的分支节点已经打到了要求的上限,则该节点必须为叶子结点(即操作数)。有了这个信息之后,针对当前结点的类型不同,就可生成对应的结构,之后如果当前结点为分支节点的话,就递归生成其左右子树。
在对表达式进行正确性检验的过程中,如果当前结点为叶子节点,那么我们仅需要检验这个叶子结点的数值是否满足要求。否则,先递归对它的左右子树进行正确性检验,在确保左右子树正确的情况下,检验当前结点的运算是否会造成不合法的情况,如果有的话则进行修复。
在对表达式最小表示的过程中,同样是先递归对其左右子树进行最小表示,之后再看,如果当前结点为'+'或'×',则判断一下他的两个子树的hash值大小,在不改变运算顺序的前提下使表达式变为最小标识的形式。
检验算式仍然采用了第一次作业的形式,以一个STL的set来存放最小表示后的字符串,通过字符串的比较进行判重。
对于计算表达式结果的功能,仍然没什么好说的,采用了STL的两个栈来维护。
具体实现
首先来看UML类图:
本次项目*用到了4个类。CFactor类是对上次Factor的一个扩展,加入了对负数的支持。CExpressionNode类是表达式树的一个节点。CExpression类是表达式树,CProblemSet类对两种操作进行了封装。这四个类形成如上的关联关系。
根据这个这个类图,顺便说一下本次结对项目的代码规范:
- 类名均以 C 开头,大括号不换行
- 类属性以 m _ 开头
- 类方法均使用小写字母,单词之间采用下划线分开。
- 每个类方法前必须有必要的注释
这样的规范主要考虑到本次项目要与MFC结合,因此使用了一些Win32的代码习惯。
CFactor类中,我重载了各种运算符,包括输入输出、四则运算和比较运算符。重载运算符后会大大降低编程复杂度,但是过多地采用流输入输出可能会对程序效率造成影响……这也是我在测试的时候才发现的问题。
CExpressionNode类则没什么好说的,就是储存了一个树节点的信息,包括其左右子树、当前结点的运算符以及当前子树的表达式的值。
CExpression类则是一个表达式树,他内部采用了一个CExpressionNode类型的数组用来存储表达式中的所有结点,并通过new_node
方法实现获取一个新节点的操作。这样做避免了每次的动态内存分配,一定程度上可以提高程序效率,但是这样做则要求表达式不能太长,不过在实际应用中不会用到太长的表达式。
CProblemSet类则没什么好说的了,他实例化了一个CExpression类的对象,每次调用该类的 build_expression_tree
方法生成一个表达式并使用set进行重复检验。
单元测试
本次项目的基础就是CFactor类,如果该类的实现有问题,那么所有功能都不能正常工作,因此我主要对该类进行了单元测试。
VS2013单元测试我也是第一次使用,不知道为什么Managed Test Project 创建后会无法连接C++console Application的代码,最后采用了 Native Unit Test Project 来做单元测试,它的语法与Managed Test Project略有不同,但是也很简单,我针对CFactor类的各种方法写了37条Unit Test, 并且全部通过了。
代码覆盖率:
注:我的VS2013是社区版,没有代码覆盖率分析工具,所以在我编写完测试用例后,借用了同寝室的另一个人的电脑来测试并进行代码覆盖率检验。