面向对象设计与构造第一单元总结
设计分析
第一次作业
总体架构
第一次作业仅处理简单幂函数和常数的多项式，且不需要判断输入字符串的合法性，所以构造相对简单，总共只有三个类。PolynomialDerivation类负责读入与输出；Polynomial类负责解析多项式，将其分割为多个项；Monomial类负责处理各项。
类的分析
（1）度量分析
各方法度量分析如下表所示：
computeCoefficient和derivation方法中嵌套了较多if-else语句和try-catch语句，导致认知复杂度较高；derivation的本质复杂度较高，是因为设计时采用较多if语句来返回各种特殊情况下的求导值。
| Method | CogC | ev(G) | iv(G) | v(G) |
|---|---|---|---|---|
| Monomial.Monomial(String) | 0 | 1 | 1 | 1 |
| Monomial.computeCoefficient(String) | 10 | 1 | 5 | 5 |
| Monomial.computeExp(String) | 7 | 1 | 4 | 4 |
| Monomial.derivation() | 10 | 9 | 3 | 9 |
| Monomial.getCoefficient() | 0 | 1 | 1 | 1 |
| Monomial.getExp() | 0 | 1 | 1 | 1 |
| Monomial.setCoefficient(BigInteger) | 0 | 1 | 1 | 1 |
| Monomial.setExp(BigInteger) | 0 | 1 | 1 | 1 |
| Polynomial.Polynomial(String) | 0 | 1 | 1 | 1 |
| Polynomial.derivation() | 4 | 1 | 3 | 3 |
| Polynomial.mergeMap(Monomial) | 2 | 1 | 2 | 2 |
| Polynomial.splitMonomial() | 1 | 1 | 2 | 2 |
| PolynomialDerivation.main(String[]) | 3 | 1 | 3 | 3 |
下表为对每一个类的度量分析，复杂度最高的是Monomial类，这是因为该类中包含较为复杂的求导方法等。
| Class | OCavg | OCmax | WMC |
|---|---|---|---|
| Monomial | 2.62 | 9 | 21 |
| Polynomial | 2 | 3 | 8 |
| PolynomialDerivation | 3 | 3 | 3 |
（2）类图分析
-
PolynomialDerivation类：用于读入与输出字符串，同时对字符串进行简单处理，如去除空白项等操作。
-
Polynomial类：用于表达式的处理和求导，包括以下功能：
-
正则提取项
用正则表达式对项依次进行匹配，匹配到的项传入Monomial类中处理。
笔者在设计正则表达式时比较投机取巧，因为在本次作业中，每个项的结尾只有‘+’、‘-’、或者字符串结尾三种可能性，所以完全可以利用正则表达式中的环视进行模糊匹配，因为能保证输入的字符串绝对合法。
-
同类项合并
将项加入对应的容器中时根据幂次方进行同类项合并，方便求导。
-
求导
本质是调用存储容器中各个元素的求导方法，并将求导结果以字符串形式拼接起来。
-
-
Monomial类：用于项的处理和求导，包括以下功能：
-
因子提取
通过‘*’符号分割各因子，并获取系数、幂函数指数等信息。
-
求导
根据系数、指数等信息，返回求导后的项的字符串。对于特殊的项（如仅有数字、指数为0或1等），需进行特殊处理，其余情况按照a*x**b的形式输出。
-
（3）优缺点分析
- 优点
- 层次简单，保证正确性。
- 正则表达式设计简单清晰，缩短了代码篇幅。
- 缺点
- 部分设计并没有完全解耦，一些方法设计较为臃肿。
- 部分方法嵌套了过多if语句，降低了代码可读性。
- 缺乏可扩展性。
第二次作业
这次作业出现了正弦函数sin(x)**k和余弦函数cos(x)**k，还新增了以括号包裹的表达式因子。显然，之前的正则表达式匹配不适用于本次作业，快进到重构环节。
总体架构
本次作业的思路是采用递归下降解析字符串，按照表达式->项->因子的递进结构解析字符串，解析完后得到的是一个多叉树结构。以下为实现此架构的核心思路：
- 对于表达式，可以看作一个项或者多个项加减，因此用Sum类存储表达式及表达式因子。Sum类中包含各个项。
- 对于项，可以看作一个因子或者多个因子相乘，因此用Mult类存储项。Mult类中包含各个因子。
- 对于因子，表达式因子按照Sum类处理，其余因子按性质分为sin、cos、constant、power四类，通过正则表达式匹配，采用工厂模式生成。
- 以上提到的所有类都实现一个Derivative接口，该接口定义了求导方法。
- 对于项、因子的提取方法单独定义在方法类InputHandler类中。
- 维护全局变量以定位表达式所解析到的位置。
- 考虑到递归下降时可能会出现冗余的项或者因子，递归过程很容易超时，所以对于Sum类和Mult类，定义剪枝方法以缩短多叉树的深度。
类的分析
（1）度量分析
各方法度量分析如下表所示：
| Method | CogC | ev(G) | iv(G) | v(G) |
|---|---|---|---|---|
| Constant.Constant(BigInteger) | 0 | 1 | 1 | 1 |
| Constant.Constant(String) | 0 | 1 | 1 | 1 |
| Constant.Constant(int) | 0 | 1 | 1 | 1 |
| Constant.derivation() | 0 | 1 | 1 | 1 |
| Constant.getVal() | 0 | 1 | 1 | 1 |
| Constant.setVal(BigInteger) | 0 | 1 | 1 | 1 |
| Constant.toString() | 0 | 1 | 1 | 1 |
| Cos.Cos(BigInteger) | 0 | 1 | 1 | 1 |
| Cos.Cos(String) | 2 | 1 | 2 | 2 |
| Cos.derivation() | 2 | 3 | 2 | 3 |
| Cos.getExp() | 0 | 1 | 1 | 1 |
| Cos.setExp(BigInteger) | 0 | 1 | 1 | 1 |
| Cos.toString() | 2 | 3 | 1 | 3 |
| Factory.facMaker(String) | 6 | 7 | 3 | 7 |
| Factory.init() | 0 | 1 | 1 | 1 |
| InputHandler.cutBranch(Derivable) | 2 | 3 | 3 | 3 |
| InputHandler.getIndex() | 0 | 1 | 1 | 1 |
| InputHandler.getPre() | 0 | 1 | 1 | 1 |
| InputHandler.parseFactor() | 1 | 2 | 1 | 2 |
| InputHandler.parseTerm() | 3 | 1 | 3 | 4 |
| InputHandler.setIndex(int) | 0 | 1 | 1 | 1 |
| InputHandler.setPre(String) | 0 | 1 | 1 | 1 |
| Mult.Mult(ArrayList<Derivable>) | 0 | 1 | 1 | 1 |
| Mult.Mult(ArrayList<Derivable>,Boolean) | 1 | 1 | 2 | 2 |
| Mult.cutBranch() | 5 | 2 | 4 | 4 |
| Mult.derivation() | 17 | 6 | 8 | 11 |
| Mult.getFactorList() | 0 | 1 | 1 | 1 |
| Mult.simplify(ArrayList<Derivable>) | 6 | 1 | 5 | 9 |
| Mult.toString() | 4 | 1 | 3 | 3 |
| PolynomialDerivation.main(String[]) | 0 | 1 | 1 | 1 |
| Power.Power(BigInteger) | 0 | 1 | 1 | 1 |
| Power.Power(String) | 2 | 1 | 2 | 2 |
| Power.derivation() | 2 | 3 | 3 | 3 |
| Power.getExp() | 0 | 1 | 1 | 1 |
| Power.setExp(BigInteger) | 0 | 1 | 1 | 1 |
| Power.toString() | 3 | 4 | 1 | 4 |
| Sin.Sin(BigInteger) | 0 | 1 | 1 | 1 |
| Sin.Sin(String) | 2 | 1 | 2 | 2 |
| Sin.derivation() | 2 | 3 | 2 | 3 |
| Sin.getExp() | 0 | 1 | 1 | 1 |
| Sin.setExp(BigInteger) | 0 | 1 | 1 | 1 |
| Sin.toString() | 2 | 3 | 1 | 3 |
| Sum.Sum() | 2 | 1 | 3 | 3 |
| Sum.Sum(ArrayList<Derivable>) | 0 | 1 | 1 | 1 |
| Sum.cutBranch() | 5 | 2 | 4 | 4 |
| Sum.derivation() | 7 | 3 | 4 | 5 |
| Sum.getExprList() | 0 | 1 | 1 | 1 |
| Sum.toString() | 4 | 1 | 3 | 3 |
Mult类中derivation的复杂度较高，是因为在该方法中由于函数相乘的求导规则加上自己的设计问题，有2层嵌套的for循环，复杂度显著高于其他方法。
对于每个类的度量分析，可以得出Mult类的复杂度被Derivation抬高了很大一部分。
| Class | OCavg | OCmax | WMC |
|---|---|---|---|
| Constant | 1 | 1 | 7 |
| Cos | 1.83 | 3 | 11 |
| Factory | 4.5 | 8 | 9 |
| InputHandler | 1.86 | 4 | 13 |
| Mult | 4.43 | 10 | 31 |
| PolynomialDerivation | 1 | 1 | 1 |
| Power | 2 | 4 | 12 |
| Sin | 1.83 | 3 | 11 |
| Sum | 2.67 | 5 | 16 |
（2）类图分析
可以看到，笔者的结构中并没有继承关系，而是将所有存储表达式相关信息的类都实现一个Derivate接口，让各个类实现求导方法。PolynomialDerivation类与第一次作业中功能相同，不作赘述，下面介绍其他类的功能。
-
Sum类
存储表达式中各个项及表达式因子中各个项。
Sum类求导方法的本质是对容器中各个项的求导结果的拼接，得到的仍然是一个多叉树，最后是通过toString方法输出求导后的字符串。
Sum类剪枝方法的本质是：若Sum类容器中存储有Sum类元素，则将该元素容器中的所有子元素提取出来，并删除原来存储的Sum类元素；如果Sum中只有一个元素，完全可以舍弃Sum这层外壳，直接返回该元素。
-
Mult类
存储项中各个因子（包括表达式因子）。
Mult类求导方法的本质是按照函数相乘的求导规则，对容器中各个项的求导结果的拼接，得到的是一个多叉树。
Mult类剪枝方法的本质与Sum类相似，在于减少多叉树深度，以免递归过程冗杂导致超时。
显然，Mult类的求导方法实际上比Sum类复杂，导致设计时的复杂度显著提高。
-
Constant/Cos/Sin/Power类
这四类都属于简单因子，所以归为一类介绍。
上述4类各自实现简单求导方法，是递归下降中最底层的类。
-
InputHandler类
用于提取项和因子的方法类，单独实现以实现低耦合的目标。
-
Factory类
用于生成简单因子类的方法类，采用正则匹配返回对应的因子类型。
（3）优缺点分析
- 优点
- 逻辑结构清晰，保证正确性。
- 采用递归下降以生成一个多叉树，在代码可读性和可扩展性上都有显著提升。
- 缺点
- 部分设计并没有实现高内聚低耦合，完全可以将优化方法和剪枝方法写在单独的方法类中实现。
- 没有完全利用面向对象编程的优点，例如Constant/Cos/Sin/Power四类完全可以继承一个Factor类的接口或类，使结构层次更加清晰；同理，Sum/Mult类可以实现一个接口来实现剪枝方法等。
第三次作业
本次作业中三角函数内可嵌套表达式因子，还加入了合法性检查。对于前者，笔者第二次作业的架构完全可以胜任，只需要新增方法以读取三角函数内的表达式因子即可；而对于后者，由于笔者之前对于空白字符采用直接清除的方式，根本没有考虑合法性要求，因此在原有的架构上，需要加入与空白字符相关的代码，此项任务比较复杂。
总体架构
在第二次作业上的改进思路如下：
- 新增Pair类，以存储三角函数内嵌套表达式因子的类型。
- 每次读取表达式、项时，优先判断有无空白字符，有则直接吃掉；对于简单因子，修改正则表达式使其能够识别有空白字符的因子；对于表达式因子，在读取到左括号后，优先判断有无空白字符，其余操作和表达式的读取方式无异。
- 对于括号个数不匹配的判断，可以利用全局变量判断。全局变量越界或者表达式读取提前结束都能够说明括号个数不匹配。
类的分析
（1）度量分析
各方法度量分析如下表所示：
| Method | CogC | ev(G) | iv(G) | v(G) |
| Constant.Constant(BigInteger) | 0 | 1 | 1 | 1 |
| Constant.Constant(String) | 0 | 1 | 1 | 1 |
| Constant.Constant(int) | 0 | 1 | 1 | 1 |
| Constant.derivation() | 0 | 1 | 1 | 1 |
| Constant.getVal() | 0 | 1 | 1 | 1 |
| Constant.setVal(BigInteger) | 0 | 1 | 1 | 1 |
| Constant.toString() | 0 | 1 | 1 | 1 |
| Cos.Cos(BigInteger) | 0 | 1 | 1 | 1 |
| Cos.Cos(String) | 4 | 1 | 3 | 3 |
| Cos.derivation() | 2 | 3 | 2 | 3 |
| Cos.getExp() | 0 | 1 | 1 | 1 |
| Cos.setExp(BigInteger) | 0 | 1 | 1 | 1 |
| Cos.toString() | 2 | 3 | 1 | 3 |
| Factory.facMaker(String) | 7 | 7 | 4 | 8 |
| Factory.findExp(String) | 1 | 2 | 2 | 2 |
| Factory.init() | 0 | 1 | 1 | 1 |
| Factory.pairFacMaker(String) | 8 | 3 | 6 | 6 |
| InputHandler.cutBranch(Derivable) | 2 | 3 | 3 | 3 |
| InputHandler.getIndex() | 0 | 1 | 1 | 1 |
| InputHandler.getPre() | 0 | 1 | 1 | 1 |
| InputHandler.parseFactor() | 1 | 1 | 1 | 2 |
| InputHandler.parseTerm(char) | 16 | 1 | 10 | 15 |
| InputHandler.setIndex(int) | 0 | 1 | 1 | 1 |
| InputHandler.setPre(String) | 0 | 1 | 1 | 1 |
| Mult.Mult(ArrayList<Derivable>) | 0 | 1 | 1 | 1 |
| Mult.Mult(ArrayList<Derivable>,Boolean) | 1 | 1 | 2 | 2 |
| Mult.cutBranch() | 5 | 2 | 4 | 4 |
| Mult.derivation() | 17 | 6 | 8 | 11 |
| Mult.getFactorList() | 0 | 1 | 1 | 1 |
| Mult.simplify(ArrayList<Derivable>) | 6 | 1 | 5 | 9 |
| Mult.toString() | 4 | 1 | 3 | 3 |
| Pair.Pair(String,String,Derivable) | 0 | 1 | 1 | 1 |
| Pair.Pair(String,String,Derivable,int) | 1 | 1 | 2 | 2 |
| Pair.derivation() | 4 | 3 | 2 | 4 |
| Pair.toString() | 2 | 3 | 1 | 3 |
| PolynomialDerivation.main(String[]) | 1 | 1 | 2 | 2 |
| Power.Power(BigInteger) | 0 | 1 | 1 | 1 |
| Power.Power(String) | 4 | 1 | 3 | 3 |
| Power.derivation() | 2 | 3 | 3 | 3 |
| Power.getExp() | 0 | 1 | 1 | 1 |
| Power.setExp(BigInteger) | 0 | 1 | 1 | 1 |
| Power.toString() | 3 | 4 | 1 | 4 |
| Sin.Sin(BigInteger) | 0 | 1 | 1 | 1 |
| Sin.Sin(String) | 4 | 1 | 3 | 3 |
| Sin.derivation() | 2 | 3 | 2 | 3 |
| Sin.getExp() | 0 | 1 | 1 | 1 |
| Sin.setExp(BigInteger) | 0 | 1 | 1 | 1 |
| Sin.toString() | 2 | 3 | 1 | 3 |
| Sum.Sum() | 8 | 1 | 7 | 7 |
| Sum.Sum(ArrayList<Derivable>) | 0 | 1 | 1 | 1 |
| Sum.cutBranch() | 5 | 2 | 4 | 4 |
| Sum.derivation() | 7 | 3 | 4 | 5 |
| Sum.getExprList() | 0 | 1 | 1 | 1 |
| Sum.toString() | 4 | 1 | 3 | 3 |
| WrongFormatException.WrongFormatException() | 0 | 1 | 1 | 1 |
| WrongFormatException.WrongFormatException(String) | 0 | 1 | 1 | 1 |
不难看出，相比于第二次作业，大部分方法的复杂度都没有显著变化，除了parseTerm方法。这是因为笔者在设计合法性判断时，采用了极为简单粗暴的方法，即直接在原有方法上增加合法性判断的代码。
下表为对每一个类的度量分析，可见复杂度最高的仍是Factory和Mult类，其他类均在一个较为合理的水平上。
| Class | OCavg | OCmax | WMC |
|---|---|---|---|
| Constant | 1 | 1 | 7 |
| Cos | 2 | 3 | 12 |
| Factory | 4.5 | 9 | 18 |
| InputHandler | 2.57 | 9 | 18 |
| Mult | 4.43 | 10 | 31 |
| Pair | 2.5 | 4 | 10 |
| PolynomialDerivation | 2 | 2 | 2 |
| Power | 2.17 | 4 | 13 |
| Sin | 2 | 3 | 12 |
| Sum | 3 | 5 | 18 |
| WrongFormatException | 1 | 1 | 2 |
（2）类图分析
相比于第二次作业，除了新增加了WrongFormatException、Pair类，其余改变主要是InputHandler类中。这里介绍第三次作业中的更进：
-
pair类
该类中设置external和internal，分别表示外部的函数类型（这里只能是sin、cos中的一个）和内部的函数类型。该类实现Derivable接口以实现求导方法。
-
WrongFormatException类
自定义的Exception，根据题目要求，对于所有错误的格式返回"WRONG FORMAT!"。
-
合法性判断
个人认为自己的合法性判断设计过于面向过程。对于合法性的判断，主要难点在于空白字符的处理和括号的处理。对于出现在简单因子中的不符要求的空白字符，可以通过正则表达式匹配来解决；对于表达式因子中不符要求的空白字符，需要在读取过程中单独判断；对于括号判断，正如讲解思路时所说，可以通过返回最终读取结束的位置以判断是否存在括号不匹配的情况。
（3）优缺点分析
- 优点
- 逻辑结构清晰，保证正确性。
- 在原有作业基础上进行改动，保持了代码的可扩展性。
- 缺点
- 合法性判断的设计过于面向过程，降低了代码可读性。
- 第二次作业中的问题没有得到解决。
Bug分析
第一次作业
1.读入时忽略了可能连续出现三个符号的情况（如+-+ 2*x）,导致程序执行时陷入死循环。
问题出现在PolynomialDerivation.main方法中，这是因为我图方便，将符号的预处理直接写在主函数中（这是坏习惯，之后设计代码时应注意）。在添加了对三符号的处理后，仅仅添加了2行代码，复杂度没有变化。
第二次作业
第二次作业是一遍过的，很大程度上源于重构时是一边写代码一边进行功能测试，所以没有出现强侧Bug和被hack的Bug。
第三次作业
第三次作业中在强测时出现了奇怪的Bug：程序正确输出了WRONG FORMAT!，并且表达式确实不合法，但是显示RUNTIME ERROR。根据检查，发现是因为程序在抛出异常后，执行了以下代码：
System.out.println("WRONG FORMAT!");
System.exit(-1);
由于返回值是-1，导致程序并没有正常结束（正常结束的返回值是0），所以得到了RUNTIME ERROR。更离谱的是，在其他错误判断时，我都调用的System.exit(0)返回，唯独这句出错了，强测直接90分，巨亏无比，希望各位能引以为戒，不要返回一些奇怪的值。
Hack策略
阅读别人的代码
阅读别人的代码是一个痛苦的过程，因为每个人的想法或多或少都有偏差，并且在明知有人会hack代码的情况下，很难看到写的很完备的注释。但个人认为，既然我们有进行”白箱测试“的机会，那么根据别人的代码进行针对性的测试未尝不是一种方法，同时，在阅读过程中可以借鉴别人好的代码，完善自己的程序。
自动化评测机
肉眼debug显然是很痛苦的，而且局限性大。针对本单元的作业，通过python的xeger库以逆向生成数据，我们可以做到生成合法的随机数据，并且使其尽量达到极限要求（如最大长度，最大嵌套次数等），对别人的代码进行边界测试和压力测试。最大的好处在于，自动化评测机往往能造出你想不到的刁钻数据。
重构总结
笔者仅在第一次作业到第二次作业之间进行了重构，此重构基本改变了所有的程序框架。
通过类图可以显然比对出结果：
显然，第二次作业的结构和度量数据都比第一次显著复杂了许多。
第一次作业仅处理常数和简单幂函数，所以设计时没有专门设计因子层次，并且程序结构极为简单，即表达式->项->因子三层结构，所有的项和因子的提取都可以通过字符串函数和正则表达式完美解决；求导直接返回各项拼接后的字符串即可，不存在复杂的函数调用。
第二次作业则进行了大改，从设计结构上来说，将表达式以多叉树的形式存储，采用递归下降的思路实现对表达式因子的嵌套，不再是表达式->项->因子三层结构，而是循环嵌套的递归结构；仅简单因子采用字符串函数和正则表达式处理，复杂的表达式因子需要递归调用表达式的解析方法，很大程度上提高了程序的复杂度。
心得体会
这是面向对象设计的第一次单元作业，设计难度对我来说是一个挑战。在设计出正确性有保障的程序后，还需要考虑如何优化性能，并且不影响到正确性以及超时，这是很难的一点。我常常在写出正确的代码后，失去了优化的动力。
但通过面向对象的作业，个人认为自己编写程序的能力得到了显著提升，作业的同时也在慢慢地将面向对象的思想带入代码中（虽然代码结构还是很臃肿）。作业的迭代开发，也让我学习到了如何写出可扩展性强的代码。