BUAA-2024年春-OO第一单元总结_北航数据结构大作业2024

1.第一次作业

第一次作业的内容是读入一个包含加、减、乘、乘方以及括号（其中括号的深度至多为 1 层）的单变量表达式，输出恒等变形展开所有括号后的表达式。可以看到hw1并不算非常复杂，具体各个类如下所示，我将在下文中解释每个类的设计考虑。

架构

在课程组的引导下，我以递归下降法为基础思路完成这次作业，hw1以及后续的两次作业大致分为预处理、文法分析、解析、输出四个部分。下面我将逐一进行解释。

在处理输入的内容时，由于输入内容可能有前导零、空白符和不多于三个的连续正负号，这些干扰如果不加处理直接进行解析，无疑会增加解析部分的难度。所以我对输入内容专门建立了一个Processer类进行预处理，其唯一作用就是去掉前导零和空白符，并将连续的正负号转换为单个正负号，如果最终为单个负号则将其替换为-1*的形式。

在对输入内容进行Processer类的预处理之后，此时的输入内容应该和蔼可亲了许多。但是它的形式仍然是字符串，为了便于后续解析以及增强代码的可读性，我为预处理后的内容建立了Lexer类进行文法分析。对此我建立了Token类，将字符串的内容分为ADD，SUB，LP，RP等Token.Type，将字符串形式的表达式转换为一个ArrayList<Token>，并将该ArrayList传入到解析部分。

解析部分根据作业的形式化设计，我建立了Parser类，为需要解析的内容建立了Expr，Term，Factor三类，由于括号的存在，Factor的具体形式可以有很多种，所以我将Factor定义为接口，底层分为Expr，ExprFactor，Variable，Number四个类。其具体思路以递归下降法为基础。将整个解析式视作一个expr的形式，然后每个expr视作term+term+term，每个term由factor*factor*factor组成。如果factor中出现括号，则将括号内的部分视作一个表达式，再次按照上述思路来进行解析，最后返回一个factor对象即可。这样就可以自上而下地对整个表达式进行解析。这也是此次作业的核心部分。经过这一系列解析，最后我们就得到了一个含有ArrayList<Term>的expr，而ArrayList中的每个term都有一个ArrayList<Factor>。这里比较绕，但是根据递归下降法的思想就很好理解。

此时我们只是得到了一个非常抽象的expr，以及其内部的ArrayList<Term>以及其内部的内部的ArrayList<Factor>。但作业要求是输出化简之后的表达式，显然我们需要进行一个输出处理。在这里我参考了Hyggge学长的思路，将expr转换为一个poly多项式，所以expr下面的term和factor都实现了toPoly()方法。我们按照自底向上的方法将整个expr转换为poly多项式，此时我们只差一步，就是将poly多项式转换为可视性极强的字符串。这里我们改写了toString方法。同样按照自底向上的方法将poly多项式下面的每个mono单项式转换为字符串a*x^b的形式。最后输出整个poly的字符串。自此，第一次作业大致完成。

复杂度分析

下图列出了一部分方法的复杂度，可以看出Parser类中的parseFactor()方法复杂度较高，因为我在该方法中实现了对factor的四种可能形式的处理，所以较为复杂。此外Processer类中的Processer()方法复杂度也非常高，因为我直接将对输入内容的预处理功能放在Processer类的构造函数中了，对于前导零、连续的正负号以及空白字符进行处理，使得该方法成为此次作业中最复杂的部分。

测试

此次作业通过了强测，但是有一个测试点未能达到性能分满分，因为我在将poly中的mono转换为字符串形式之前，会按系数从大到小进行一次排序，这样的好处是可以节省负数的一个负号长度。但是我的逻辑是，对排完序后的mono，第一项直接输出，从第二项开始对系数是否为0，符号等进行判别。这也导致了我有时会原封不动的输出一个0，从而造成了性能失分。

总结

我感觉hw1的任务量并不算大，但是对于头一次接触递归下降法的我，完全理解这个方法着实花了很长时间，此外就是对于优化考虑仍有欠缺，没有考虑到一些特殊情况。此外，感谢同学搭建的评测机。

2.第二次作业

第二次作业的内容是读入一系列自定义函数的定义以及一个包含幂函数、指数函数、自定义函数调用的表达式，并实现多层括号嵌套，输出恒等变形展开所有括号后的表达式。我以为这次迭代不复杂，但OO狠狠地给我上了一课。下图为我在hw2中设置的类。

架构

hw2基本沿用了hw1的整体思路，由于递归下降法在处理括号方面有着天然的优势，所以对于多层括号无需额外处理。我们只需要解决自定义函数和指数函数的问题。相比于hw1，我在hw2中新增了三个类，分别是FuncFactor，Definer和ExpFactor。前两个类用于处理自定义函数，最后一个类用于处理指数函数。同样，我将自定义函数和指数函数视为Factor的一种，所以在Parser中进行解析时，遇到自定义函数和指数函数的处理方法与先前的Number，Variable等类似，只需要在解析读到exp或者函数名fgh后进入相应的方法，最后返回一个Factor即可。

除此之外，对于自定义函数需要进行额外的处理，将形参与实参对应起来，然后在函数定义式中进行替换，即可得到自定义函数的内容。我在这里将自定义函数的返回类型设为Factor中的Expr，然后利用Parse的parseExpr()方法即可对其进行进一步处理，无需重复造轮子。

对于指数函数exp()括号中的内容，我同样将其视为Expr，利用Parse的parseExpr()方法进行解析，然后将其转换为一个个mono组成的多项式。

复杂度分析

相对于hw1，可以看到Processer()方法复杂度仍然很高。此外，在hw2中Parser.parseFactor()因为新增了两类因子，复杂度有所提高，我为自定义函数因子定义的解析方法Parser.parseFuncFactor()实现了将抽象形式的函数转换为表达式，由于fgh三种函数名和xyz三种形参我都是用简单的if-else判别，所以复杂度较高。

测试

hw2中我虽然通过了强测，但是没有逃脱同学的hack。经过检查，我发现bug出现在自定义函数部分，因为我在读入函数实参的时候，是通过循环判断右括号数量是否等于左括号数量，如果相等则视为所有实参均被读入。但是我忽略了跳出循环的时机，所以导致当函数最后一个右括号外还有右括号的时候，我的程序便会将函数外的括号读入，进而导致这个括号丢失，这直接改变了表达式的语义。

总结

hw2远比我想的复杂，我将表达式转换一个个mono组成的多项式，每个mono的形式为a*exp(b)*x^c。但是我利用ArrayList数据结构来存取exp()括号中的内容，由于java中ArrayList的clone是浅克隆，所以在进行乘法合并同类项的时候我便遇到了灵异事件。我大概花了一天才定位了该bug并实现了修复，这让我对java中的深浅克隆有了更深刻的理解。

3.第三次作业

第三次作业的内容是读入一系列自定义函数的定义以及一个包含幂函数、指数函数、自定义函数调用、求导算子的表达式，并支持函数在调用时的嵌套定义，输出恒等变形展开所有括号后的表达式。

最开始我对于求导没有思路，但是想清楚之后便发现很容易。下图是我在hw3中设置的类。

架构

我在架构上相较于hw2没有新增任何类，一切迭代均在原有类上进行修改。由于我在hw2中对函数实参的解析过程中直接使用Parse类进行解析，所以对于hw3中的函数嵌套定义和调用先天支持，无需额外拓展。而对于hw3的重中之重——求导，我的思路是将dx()括号内的内容先使用Parse类解析，将dx()括号中的内容转换为Expr，然后再将其通过Expr.toPoly()方法将其转换为一个个mono单项式组成的poly多项式，我在Mono中新增了一个方法toDx()，与Mono类先前的toString()类很像，将mono转换为求导后的形式。至此，hw3作业已经完成。我感觉hw3是第一单元三次作业中任务量最小的一次。

测试

hw3成功通过了强测和互测。因为hw3相较于hw2并没有结构上的改变，只是新增了一个求导功能，而程序中的大部分bug在hw2的强测和互测中都已修复，所以hw3的测试较为顺利。

总结

hw3的任务量不大，但是让我充分认识到拥有一个良好的程序架构以及迭代开放的空间是多么重要。以及不要重复造轮子，最大限度利用已有的方法解决问题。

如果在hw3的基础上新增三角函数等部分，我的程序不需要大规模重构，但是在某些部分肯定会面临大改，例如需要将Mono单项式的形式扩充为a*exp(b)*x^c*sin()*cos()，并修改相应的toString()和toPoly()以及toDx()方法。

4.hack策略

在三次作业中的互测环节中，我均采用了评测机对同房间的其它代码进行评测来寻找bug。此外，我在写作业的时候发现自己犯得一些错误也会记录，用于互测时的hack。

此外，我对于一些特定的数据进行hack，比如exp(0)-1，0，-1+1。

5.优化策略

本人在优化方面做的有限，并没有像有些同学做到了极致的优化。我在优化方面主要考虑了两点。

一是对poly中的mono进行合并同类项，然后以mono的系数从大到小进行排序，如果发现mono的系数为0则不进行输出。如果poly中的ArrayList<Mono>为空，则输出0。

二是对exp()的括号数量进行判定，因为如果exp()中如果是表达式则需要在表达式两侧添加一对括号，否则，则可以省略这一对括号，减小长度。

6.心得体会

经过第一单元的学习和作业，我再次加深了对于面向对象编程的了解，此外上千行的代码编写也使得我的编程能力进一步提高。同样我也认识到了自己的诸多不足，特别是在刚刚接触递归下降法的时候，不断的递归使我摸不着头脑。而且对于java语言的不熟悉，使我在深浅克隆上吃了不少苦头。

此外，我在一次次的迭代开发中我认识到了工程方法的重要性，尤其是不要重复造轮子，还有要保证代码的可拓展性和可读性。

7.未来方向

我认为OO第一单元的课程设计非常合理。（虽然任务量好大QWQ）