BUAA面向对象设计与构造——第一单元总结

BUAA面向对象设计与构造——第一单元总结

第一阶段：只支持一元多项式的表达式求导

1. 程序结构

　　由于是第一次接触面向对象的编程，加之题目要求不算复杂，我在第一次作业中并没有很好利用面向对象的特点，只建了两个类。

　　第一个DerivativeFunc类只包含main函数，而剩余所有功能包括正确性检查、求导和输出都全在类Poly里。这两个类之间也没有继承等关系，所以整体看起来还是偏向C语言的思路，这也是这次作业最大的问题。在类Poly里面，我建立了两个链表来分别存储每一项的系数和幂指数。

　

　　从以上两个复杂度统计可以看出，因为第一次作业只有两个类，因此大部分的操作都集中在在OutputPoly这个输出函数中。这也导致了它的复杂度偏高。

2. 特殊处理

　　关于输出字符串的正确性检查，我使用了正则表达式的匹配。题目中给了关于大数处理的提示，因此我选择了使用java自带的BigInteger类型来处理系数和指数。

3. 存在的bug

　　第一次作业没有考虑正则表达式爆栈的情况，确实是考虑不够全面。后来看到评论区提供的独占模式，我就在后两次作业中都改掉了。在强测中虽然通过了全部的正确性检查，但是性能分没有拿到满分。原因在于我的优化部分少优化了一种情况：对于首项为负数系数，而之后的项中有正数系数的表达式，可以先输出正数系数的项，以减少一个‘+’的长度。

第二阶段：支持一元幂函数与三角函数乘法和加法的表达式求导

1. 程序结构

　

　　在上次作业中，我的整个表达式都存储在一个类里，没有进行划分。而这次由于加减法相连的项的格式不统一，所以我将表达式分割为了多个项，为每一个项实例化了一个Term类。

　　　　　　　

2. 特殊处理

　　一开始我的设想是为表达式、项和因子都分别建一个类，因子相乘得到项，项相加得到表达式，上层类使用链表存储下层类的实例化对象。但是后来我发现在这次作业中，每个项的形式都能用a*x^b*sin(x)^c*cos(x)^d来表示，因此无需建立因子类（当然这个时候不建第三次作业也得建）。

　　我在Expression类中建立了以Term类为键值的Hashmap，而value部分则存储这一项的常数因子。

　　private HashMap<Term, BigInteger> hashExp = new HashMap<>();

　　由于Hashmap可以通过键值直接查找结点，因此这样的存储方式可以方便同类项的合并。为了实现这一功能，需要在Term类里重写equals()和hashCode()函数。每个项由numDegree, xDegree, sinDegree, cosDegree四个参数来确定，只要后三个指数参数相同了，那么就可以判定两项是同类项，再将系数相加，就可以实现同类项合并。

　　对于优化部分，我只实现了cos²x + sin²x = 1, 1 - cos²x = sin²x , 1 - sin²x = cos²x 三种形式的优化。由于无脑优化上述三种情况可能会使得输出长度反而增加，因此我只使用二重循环遍历了hashMap，将确定会减少长度的情况进行了优化。包括系数相等的情况，以及系数不相等但优化后可以合并同类项这两大类。我这次所做的优化是不完备的，我只能保证我优化的情况一定可以减少长度，但是所有能减少长度的情况我并没有涵盖完全。例如(cos²x + sin²x)² = 1这种整体再平方的优化我就无法识别了。

3. 存在的bug

　　这次强测中错了一个点，线下检查的时候发现是优化导致的错误。在Term类的replaceTerm()方法中，当系数不相等时应该剩余系数大的项，而我使用了系数小的项的幂指数来进行sinx的指数-2的修改，导致了错误。这主要还是因为我线下自己测试的数据不够完善。

第三阶段：支持一元幂函数与三角函数乘法、加法及嵌套的表达式求导

1. 程序结构

　　

　　这一次作业由于出现了嵌套规则，使得整个表达式必须分割成不同的因子，分别求导再组合。因此我设置了表达式类、项类和一系列因子类。这些同等级别的因子类同时实现一个DifferPrinciple接口。通过这个接口可以在Term类里统一管理不同类的因子，使得他们可以在同一个链表里存在。每个因子内部有求导函数differ()和原字符串返回函数getOriginStr()，像sin和cos两个类的求导函数，还会递归调用各种因子类的求导函数。通过调用每个因子的这两个函数，可以在Term里实现因子相乘的求导。最后在Expression类调用Term类的求导结果并相加。

　　从上面的统计中可以看到主类MainDiffer中有三个方法复杂度很多，这一点在下一节“特殊处理”中详述。除此之外的类由于划分比较细，因此复杂度都比较低，实现了高内聚低耦合。

2. 特殊处理

　　这次作业由于出现了三角函数的嵌套嵌套形式，因此如果用“sin\\(.+\\)”来匹配sin因子，会导致sin(x)+cos(x)被识别为一个因子。因此我没有使用正则表达式直接匹配，而是使用了类似于编译原理中递归下降分析法的形式，通过三个分别检查表达式、项、因子的方法相互调用来分割表达式并检查正确性的。这也就导致了这三个表达式的复杂度较高。这里有一个值得改进的地方在于，我第一遍扫描输入字符串时只检查了正确性，然后去掉全部空格，再传入Expression类进行第二遍扫描并分割实例化其他类。这样两次扫描比较多余，应该在第一次扫描时同时进行分割操作。当初只是为了贪图去掉全部空格这个操作，才导致代码架构的冗余。

　　对于表达式因子这个特殊的因子，我还是建了一个类，在这个类内部先对括号进行识别并且去掉多余的括号，再实例化Expression类。这样结构更清晰，也避免了在三角函数因子类直接实例化Expression类导致的括号匹配错误等问题。

　　由于这次性能分只占了5分，因此我没有做过多的优化。只是针对系数为±1，幂指数为1，多层括号等简单优化。

3. 存在的bug

　　强测中还是错了一个点，经过排查是因为表达式因子去除多层括号的时候不够严谨，去掉了不该去的。在ExpFactor类differ()函数中，我判断了如果内层嵌套函数是由一对括号括起来的，那么求导后输出也不需要加括号。但是我忽略了例如(x+x)*sin(x)+cos(x)这种表达式形式，也会被识别为前后由括号括起来。因此会导致我求导后的输出少括号，结果也就不可能正确了。

4. 测试策略

　　由于我们没有互测，以下的测试策略只是针对我个人程序调试。对于正确样例，我是先列一张表，横向和纵向都是各类因子，然后每个交叉点都要覆盖这两种因子的相加、相乘和嵌套（不符合规则的则去掉），然后手工写一系列的测试代码。错误样例包括在各种地方出现的空格、括号不匹配、非法字符和不完整表达式等。不过在我写这篇博客之前，我浏览了一些别人的博客，发现很多人是另写一个程序或者脚本来自动生成大量测试样例，瞬间觉得自己手工写测试代码太低级了。这一点也是下一单元很需要改进的地方。

总结

1.重构模式

　　后两次作业我都是完全重构写的，主要是因为前一次写的时候没怎么考虑功能的扩展，即使第二次稍微考虑了也没想到嵌套规则的复杂度。这虽然在第一单元里没有太费时间，但是我觉得在之后更高难度的题目中，如果我每次都重构可能时间和精力都要浪费很多。因此第二单元开始尤其是第一次作业，最好就考虑全面一些，而不是只为了实现这一次作业的要求。目前为止我的程序结构更贴近于工厂模式，通过实例化同一接口下的不同类来完成要求。

2.感想与收获

　　这是我第一次完整的用面向对象的思想来编程，所以一开始还不太适应，总是想写很多个方法来互相调用。到了第三次作业稍微有些进步，将输入分割成很多个不同的类，每个类自己求导，而更高一层次的类再实例化不同的类来组合。由于16级没有互测部分，因此我对自己程序的bug发现与调试还不够完善，测试程序的完备性也有待提高，这些都是未来需要解决的问题。总之有很大收获，也有更多需要改进之处。