BUAA-OO-Unit1 表达式展开

作业背景

在北航的面向对象课程第一单元作业中，我们需要在三周内的三次作业中分别完成下述任务：
第一次作业：实现支持加、减、乘、乘方、单层括号的表达式的化简与展开；
第二次作业：在第一次作业的基础上增加括号嵌套（无层数限制）、三角函数与自定义函数；
第三次作业：在前两次作业的基础上增加函数调用其他已定义函数、求导因子。
得到的分数取决于正确性（80%）与表达式的最终化简长度（20%）。

第一次作业

架构设计

在第一周，我虽然明白递归下降算法可以方便作业的后续迭代，但由于对递归下降算法并没有完全掌握，因此最终采用了一种自己构思的方法，我形象地将其总结为“没有递归，只有下降”方法。
“没有递归，只有下降”方法的核心是利用expr = term + ... + term和term = factor * ... * factor的原则，将表达式通过加减号拆分成一个个有符号项的和，将项按有无括号分别分为单项式和多项式，最终将多项式化简为单项式，统一成单项式的和，进行输出。
设计类图

本次作业的设计类图如下所示。（写这次作业分析的时候，还没有接触StarUML orz）
hw1

优点：设计逻辑好理解
缺点：面向对象的思想不太明显，更像是在玩字符串游戏；方法类比较混乱。

代码思路

代码流程大概如下：

将输入的字符串过一遍Processor类的simplify方法，将空白符、连续的加减号、乘方后的正号删除或化简；将括号内的+、-、*替换为p、n和m（为什么要这么做？见下文），将表示乘方的连续两个乘号替换为一个^，从而将乘方和乘号区别开（事实证明这一步并没有什么必要）。
用Lexer类的lexer方法处理第一步操作得到的字符串，以加减号为界，将表达式分解为一个个项；问题来了，括号内的加减号不应该参与此步操作的分解，因此在上一步中对括号内的加减号进行了替换，避免影响此次操作；将得到的一个个项放入FirstSplit类的一个ArrayList容器中，将项的内容计入str，项的符号写进signal。这样我们实现了对表达式的第一步下降操作。
将得到的FirstSplit容器用Processor类的extract方法处理，得到一个一个单项式FinalTerm；具体是怎么得到的呢？我通过遍历FirstSplit容器中的元素，如果元素的str部分不包含括号，说明其已经是一个单项式，则通过calcuExp方法解析这一项的系数coefficient和三个变量xyz的指数，并将其写入FinalTerm容器中；如果包含括号，则需要先将括号后面可能存在的乘方号处理掉，乘方后的数字为n，就将括号内的内容多乘n-1次，最后去掉乘方；再通过括号外部的乘号（亦即第一步操作中处理后的*)将str再次拆分为一个个因子，最终通过乘法分配律将所有因子乘起来，得到一个不含括号的多项式，再利用 lexer将其拆分为一个个单项式，此时这些单项式已经不含括号，用calcuExp方法对每一项进行处理，得到系数和指数，并一起放入FinalTerm容器中。如果新放入的FinalTerm在原先的容器中出现过三个指数均相同的情况，那么只需对这两项的系数求和，不需要放入新的FinalTerm，实现合并同类项。
最终得到的FinalTerm容器是化简后的所有单项式，因此最后通过toString方法将其按照标准格式输出。

出现的bug

在这次作业中我出现了两类bug，都是公测没有测出来，但是强测和互测被hack多刀的错误。

我忽略了乘号后面表示正负的加减号，未将其进行处理，导致其会影响到lexer方法中将表达式分解为项的操作。
我在括号的乘方化简为多个括号相乘时，未注意for循环中控制变量的变化规律，导致出现了化简的顺序错误。
这些出现的bug所在的代码均为比较冗余，写起来逻辑关系非常复杂的部分，我在写的过程中也是迷迷糊糊的，导致出现了一些错误。

方法复杂度

hw1
我的方法复杂度重灾区主要在Processor类里定义的几个化简方法里，这是因为我的方法并不美观，需要额外处理的细节很多，需要写多个if条件判断，以至于我的舍友说我像是在做大一上的程设题（乐）。

类复杂度

hw1
可见我的Processor类的复杂度极高，这也是因为我把几乎所有方法都杂揉进了这个类里，这也体现了我面向对象理念的不成熟。

第二次、第三次作业

架构设计

第二次作业在第一次作业的基础上引入了括号嵌套，三角函数和自定义函数，第三次作业在前两次的基础上引入了求导计算和函数调用已定义函数。由于我的第一次作业是基于括号内与括号外的加减乘号区别来实现的，而引入的三个因素都会导致新的括号产生；此外我的第一次作业代码十分复杂冗余，自己重读起来都比较费劲，因此我的第一次架构只能被抛弃。

不过，经过与舍友的交流，读互测房间内其他同学的代码，以及研讨课上的交流，我也已完全理解并掌握了递归下降算法。因此我也很快投入实践，开始重构。我的第三次作业也是在第二次的基础上迭代的，因此我将这两次作业一起来讲。
递归下降并不复杂，首先使用Lexer将表达式分解成一系列基本语法单元curToken，随后用Parser根据表达式的形式化定义，依靠Lexer分解出的语法单元，递归生成表达式、项和因子。

递归下降的优点是什么？优美，且完全支持嵌套括号，若有其他引入的因子，直接增添即可，方便后续迭代。

设计类图

本次作业的设计类图如下所示。
hw1

代码思路

整体框架使用了在第一次训练中课程组提供的advance递归下降代码，即用Lexer分析语法，用Parser进行解析。由于因子类型较多，共有常数因子、变量因子、表达式因子、三角函数因子、自定义函数因子、求导因子六种，并且他们并没有什么属性上的共性，因此我定义了Factor接口，而并没有使用继承的理念。

为了统一输出形式，我引入了单项式类Mono和多项式类Poly，并且为每一个类都写了一个change方法和toString方法，可以将每个类的对象转化为Poly形式，最终统一输出。

对于三角函数，直接增添三角函数因子类，在Mono类里增添三角函数的容器，再在Parser里写一个对于三角函数的解析即可。

对于自定义函数，我在Dealer类里定义了两个HashMap，分别为函数名到参数的映射和函数名到函数表达式字符串的映射，通过字符串操作将输入的函数分别解析。在调用函数时，用实参替换形参，将替换完得到的字符串存入表达式因子类里，并将其解析为表达式，最终也可以转变为解析表达式的问题。

求导因子看似复杂，但对于我的架构来说，显得十分简单，只需增添求导因子类，在Parser类里增添对于求导因子的解析，并在Mono和Poly里分别定义求导法则即可。

此外，由于题目规定对于自定义函数中的求导部分，是先求导再带入实参，因此需要在解析函数时直接进行一次求导因子的计算，这样才能得到正确的结果。