「BUAA-OO-Unit-1-HW4」第一单元总结

• 「BUAA-OO-Unit-1-HW4」第一单元总结
  • Part 0 前言
  • Part 1 第一次作业
    • 架构
    • 复杂度分析
    • 测试
    • 总结
  • Part 2 第二次作业
    • 架构
      • 优点
      • 缺点
    • 测试
    • 复杂度分析
    • 总结
  • Part 3 第三次作业
    • 架构
      • 优点
      • 缺点
    • 复杂度分析
    • 测试
    • 性能
    • 总结
  • Part 4 自动化测试
    • 体会
  • Part 5 单元总结
  • Part 6 展望

Part 0 前言

OO第一单元作业主题是表达式化简，具体为通过对表达式结构进行建模，完成单变量多项式的括号展开，体会层次化设计和面向对象的思想。如今，第一单元已经告一段落，在这里再次对自己的学习内容和成果加以总结。

Part 1 第一次作业

第一次作业为对包含幂函数与常数的表达式进行化简，涉及相对简单的嵌套，UML类图如下所示。

架构

数据存储上，依照形式化表达设计为Expr->Term->Factor。Parser和Lexer作为工具类，分别承担句法分析和词法分析的功能。

值得注意的是，本次架构中对于Factor的设计较为不完善，事实上没有区分Num和Power，而是将其统一为Unit类，存储一个形如\(a \times x ^ b\)的因子。

在读取和存储过程中，Parser和Lexer合作，构建了一棵多叉表达式树。

Factor接口为因子类的公共接口，所有的因子都实现了这个接口；Extendable接口为拥有扩展行为的类的公共接口，所有因子类及Term都实现了这个接口。

下图展示了这种读取和存储的过程的一个例子：

获得答案的计算过程是和读取解析相解耦合的。在调用顶层Expr对象的toString()方法后，逐层向下调用expend()方法，得到展开式。这其中，得益于Unit类的统一性，每一层向上返回的都是一个Unit对象的集合，达到了形式上和接口的统一。

复杂度分析

本次作业部分方法复杂度如下图，其余方法复杂度较低，未在图中体现。

可以看到，Parser中的parseFaactor()方法复杂度较高，分析原因知，设计该方法时对于常数和幂函数的解析都全部列在其中，没有分别抽象为分别的方法；Expr中的case2方法和caseMore方法复杂度较高，分析原因知，这两个方法负责在输出时处理较为具体的如x**2体现为x*x等化简情形，因此较为琐碎，复杂度较高；Expr中的expend()方法复杂度较高，原因是没有将加法和合并同类项单独抽象出来，而是一股脑写在其中，导致复杂度较高。

测试

本次作业在中测和强测中没有出现bug，在互测中出现bug。

其中，互测的bug在于代码中化简\(-x\)打头时忘记输出。

在对room内其他同学互测时，发现两个bug：一个是没有处理\(0\)作为指数的情况；另一个是没有处理表达式因子前有负号的情况。

同时，我在此次作业中设计并实现了一个自动化评测机，这对检验程序的正确性有不小的帮助，将在Part 4 自动化评测部分介绍。

总结

在设计本次作业之初，我设计过很多架构，在设计阶段就推倒重来若干次。尽管在Pre中的冒险者游戏中已经初步领会了面向对象的思想，但是面对较为抽象的表达式解析仍然显得无从下手。

尽管如此，得益于training部分提供的Parser和Lexer思路以及和助教与同学们的帮助，我最终得以确定这个较为面向对象的设计。但是，这个架构依然存在相当的不足，在后面的迭代开发介绍中将会着重介绍。

Part 2 第二次作业

架构

在本次作业中，我新增了SeflDefineFunc类和Sum类处理待解析表达式中的这两类函数调用；新增了Func类处理自定义函数的定义式；新增了Num和Power类将这两类因子抽离出来；新增了Add和Mul方法处理加法和乘法；新增了Sin和Cos类处理三角函数；修改了Unit类，其现在存储形如\(a \times x^b \times \prod_{i=1}^{n}(sin(expr_i))\prod_{j=1}^{n}(cos(expr_j))\)的基元。

整体架构上，依然遵循Expr->Term-Factor的结构，其中，Num,Power,SelfDefineFunc,Sum,Sin,Cos都实现了Factor接口。

在sum和自定义函数的代入过程中，没有采取在原字符串暴力替换的方法，而是采用了解析出变量式再替换的办法，更好符合了语义。

UML类图如下所示，可以点开大图查看细节。

优点

1. 简化和统一了接口与计算，Add和Mul始终只需要处理两个Unit集合（\(a \times x^b \times \prod_{i=1}^{n}(sin(expr_i))\prod_{j=1}^{n}(cos(expr_j))\)）的加法和乘法即可。
2. 数据存储和运算相解耦合。具体来说，在解析原字符串时，按照其结构存储为一棵多叉树；在运算过程中，从最顶层依次递归向下调用，获得Unit集合，结构清晰，同时不更改原有存储数据。

缺点

1. 可扩展性不佳。其中的Unit类一旦遇到新的因子，就需要重构，对Add和Mul类也是同理。
2. 涉及深浅拷贝问题，较为复杂和琐碎。
3. Sin和Cos类可以设计为Tri类的两个子类，这样更加符合其特点。

测试

1. 本次作业在强测中出现了较大问题，具体为，设计解析三角函数方法时，忽略了形式化表达中指数可以带有+与前导0的情况。仔细分析，原因应该是我没有单独将解析指数抽离出来，而是在每一个可能出现指数的地方都重写了该操作。

2. 对于替换变量后的sum函数和自定义函数，出现了可能不满足Parser和Lexer要求的字符串形式，即，没有进行预处理，这是对细节处理的疏忽。

复杂度分析

圈复杂度较高的方法如上图所示。其中，Parser中caseSelfDefineFuncF/G/H三个方法分别解析f,g,h自定义函数，其复杂度高的原因在于其中较多的进行了类似特判的操作，如在获取参数的时候是否是一个参数以及是否参数读取完毕。复盘来看，这更应该分别抽离出来方法执行相应操作。

Expr中的caseCos和caseSin方法复杂度高的原因在于，在输出字符串得时候，将化简和获取耦合在一起。举例而言，对于sin(x)，在该方法中特殊处理，使之不输出sin((1*x))。复盘来看，更应该对于这种特殊情况再抽象出方法单独处理，而不是耦合在其中。

Parser中的caseSin()和caseCos()复杂度较高，原因在于，对于其因子单独写了读取方法，而没有利用已有的读取整数和读取幂指数的方法。这更应该抽离出来，在每个需要读取指数的地方直接调用即可。

总结

这次作业在设计阶段耗时过多，直到星期四才开始写代码，挤压了后面测试和优化的时间。复盘看来，尽管设计和架构很重要，但是代码也很重要，应当两条腿走路，不能顾此失彼。

经过和同学与助教讨论，一种较为泛用的工程方法是，大致确定所需要的类和功能，然后在代码中逐步完善乃至小范围重构。事实上，代码细节有相当多不够漂亮乃至不得不很丑陋的地方，这是在设计阶段难以考虑全面的，因此，应该在思路大体确定的情况下就快速进行代码开发，为后续的测试等留有余地，这是本次作业最大的感悟。

Part 3 第三次作业

架构

本次作业进行了部分重构，具体为：扩展Sin和Cos类使之支持表达式因子的情况；新增RemoveWhite类，将对表达式的空白符即连续加减符号进行预处理的功能抽离出来；利用序列化与反序列化进行深拷贝。

优点

1. 架构依旧较为清晰，递归层次分明，对数据存储和数据处理解耦合。
2. 体现了面向对象设计的特点。

缺点

1. 可扩展性不强，如果还要新增如tan类等，需要对原有代码结构进行修改而非新增，并对Unit类进行重构，对Add和Sum类进行重构等。

复杂度分析

圈复杂度较高的方法如上图是，具体分析而言，本次作业中由于重写equals()方法，使得各层级的equals()方法内容较多，复杂度较高；Add和Mul中则由于计算与合并同类项没有解耦合，计算之后将结果插入时直接进行合并，使得这部分复杂度较高。

测试

本次作业在中测和互测中没有出现问题，在强测中一个点判错。

分析而言，是在合并同类项阶段，对两个Unit集合是否相等的判断出错。出错的方法为：将一个Unit集合映射到另一个Unit集合，如果每个元素都可以映射过去，则判等。事实上，这样做的巨大缺陷在于，如果两者为真子集关系，则会出现误合并。针对该bug，修复办法为判断双射才进行合并。

互测中，发现了sum函数中上下限有的同学设置为int的bug以及sum中变量式为sin((-i))的bug。这说明在细节处理方面仍然有很多需要注意地方，同时，测试只能找到bug，不能证明没有bug，需要通过自动测试、覆盖测试、针对测试等多种手段提高程序没有bug的可能性。

性能

本次作业性能不佳，具体原因为对于sin和cos，没有将可以去括号化简的部分进行化简，如：sin((x))可以被化简为sin(x)。

总结

本次作业中，对于合并同类项的判等写得琐碎而不漂亮，而且没有办法证明完全没有问题，最终出现了失误。对于Unit的设计思想，其对新需求的支持过弱，需要重新修改其内部大量细节，不够漂亮。

性能方面，为了求稳妥没有处理哪怕最简单的拆括号，归根结底是对测试没有信心，自己在本地测试也不够充分，这在以后应当加强。

Part 4 自动化测试

在本单元作业中，实现了一个自动化测试工具，其具体做法已经在讨论区分享过，这里附上链接「BUAA OO Unit 1 HW1」面向测试小白的简易评测机

体会

测试机构建主要需要python语言知识以及java编译知识，实现一个支持随机数据的评测机在自测是很有用的，可以大规模覆盖评测，这有很大帮助。

尽管测试机可以构造大量复杂度不同、情况不同的测试数据，但是对于特定数据可能不一定会恰巧出现，如有些同学设计了\(sin(x)^2+cos(x)^2=1\)的优化，这需要手动构造数据验证，或在测试机中加入特殊数据池。

研讨课分享时，我和大家分享了这个较为简陋和朴素的评测机结构，也向其他班级分享的同学学习了很多新的思路，如姜雨竺同学分享的开闭性原则等，这开拓了我的视野和思路。

Part 5 单元总结

本单元作业中，我更加深刻体会了面向对象的设计思想。特别地，在寒假Per2作业中作为引入的冒险者游戏的例子非常形象，很容易利用其理解面向对象以及Java语言的诸多特点，但是本单元作业相比较而言较为抽象的需求也可以很好地利用面向对象的思想，这是很大的收获。

同时，在本单元作业中，我第一次亲手实现了一个简易评测机，并更加深入地体会测试在工程开发中的重要性。真实需求中可能没有足够充分和全面的数据供使用，需要自己构建数据乃至评测机以尽可能全面地检查程序。

最后，在本单元作业中，老师、助教和同学们都给予了我相当大的帮助，数千行代码的书写也进一步提升了我的代码能力，并将我从面向过程的舒适区中拽了出来。

Part 6 展望

本单元作业面对了诸多挑战，也有诸多收获，在以后的课程学习中，我希望在以下几个方面可以更多加注意和学习：

1. 设计、代码和测试并重。在第二次作业中，因为设计挤占了过多时间导致了后面两项工作时间仓促，工程产生了巨大问题。因此，以后应当设计出大概后便开始着手代码书写，并尽可能构造测试数据进行测试。
2. 更多注重设计模式。在本单元作业中，虽然知道有诸如工厂模式等优越的设计模式，但没有认真学习和实现，而以后应当更多了解并使用这些经过实践检验的方法。
3. 不拖延ddl。OO作业具有越早开始越从容的特点，尽可能早地讨论作业内容，设计大致思路会有很大帮助。
4. 更多向大佬们学习。在本单元作业中，虽然有诸多助教和同学们的帮助，但是更多的我可能还是在单打独斗，这并不顺利。因此，以后要更多和助教与同学们讨论分享，头脑风暴出好的设计和思路。