BUAA-OO-Unit1 表达式解析

程序结构分析

第一次作业

代码结构分析

第一次作业的主要任务是展开三种表达式因子：变量因子，常数因子，表达式因子。

分析题目发现，表达式由项组成，项又由三种因子组成。而三种因子需要实现的方法又高度相似，因此制作“因子”接口，并由三种因子实现。因此总的来说，代码架构应当为Factor -> Term -> Expr。我们使用ArrayList<Term>来存储Term，ArrayList<Factor>来存储Factor。

预处理

由于本次作业的表达式中可能含有：

• 空白项
• 连续加减号
• 前导符号
• 带符号指数

等情况，因此需要进行预处理以方便后面的解析工作。

解析

我们使用Parse类对表达式进行递归下降解析。递归下降的思想是利用不同的解析函数对不同的元素进行解析。因此在Parse类中，包含了parseExpression(), parseTerm(), parseFactor()三种方法。

由于最顶层为表达式，因此在Main函数中调用parseExpression()开启解析。

• 表达式由多个项加减而得，所以先调用一次parseTerm()，如果后面还有+ | -，那么继续调用parseTerm()解析项。解析完成后，将该表达式幂次记为1
• 项由多个因子相乘得到，因此在解析项时，先调用一次parseFactor()，之后如果还有*，那么继续调用parseFactor()。
• 由于因子有三种，所以我们需要通过当前解析器所访问的token确定我们到底在解析哪个因子，然后返回解析结果即可。

词法分析

在解析过程中，需要准确分析解析器当前读入的内容，因此设置一个词法分析器Lexer。其主任务为：遍历读入的字符串，遍历过程中每步获得一个parser可以理解的token。

展开

本次作业所读入的表达式最终可以展开为多个不同幂次的单项式的和，形如：

因此，我们的任务就是根据解析的结果构建多个单项式，最终将这些单项式求和。具体来说，三种因子作为表达式原子级别的元素，需要转换成单项式。项是由多个单项式相乘得到的多项式。表达式是多个项相加得到的多项式。

• Mono类，即单项式类，需要存储该单项式的系数coe，与幂次exp。
• Poly类，由于单项式存在正负性，因此该类只需要记录单项式的集合，而不需要考虑运算符。
• 由于需要进行加法与乘法，这两个类均需要实现add, multi等方法。

优化：为了减少Poly类中存储的Mono类对象数量，在每次向Poly类添加新的Mono对象时合并相同幂次的单项式。

在获得顶层表达式的Poly表示后，我们需要将其转换成字符串形式。在这一过程中也可以进行一些优化：

• 0 + 0 - 0 ... + 0 -> 0
• a*x^0 -> a
• a*x^1 -> a*x

复杂度分析

第一次作业的代码中，可以看到平均圈复杂度比较合理，但是Lexer类的最大圈复杂度较高，主要原因在于第一次作业将预处理方法放在了Lexer中，而预处理方法需要对多种情况（例如空格、连续符号、指数符号后接加号等）进行特判，因此导致圈复杂度较高。在第二次作业中，我单独设置了预处理类，来简化Lexer的复杂度。

第二次作业

代码结构分析

第二次作业引入三角函数和递推函数，其中对代码架构产生较大影响的是三角函数，因为递推函数本身具有递归的性质，在解析、计算过程中都可以复用hw1中的代码。但三角函数相较于普通幂函数有较大不同。

三角函数

为了适应三角函数，我们将hw1中定义的Mono形态进行迭代升级，成为以下数学表达式：

三角函数类具有type, factor, exp三个属性，分别记录三角函数种类、内部因子、指数。

三角函数依然使用Parser进行解析，由于其内部是一个因子，因此直接调用parseExpr()方法解析内部表达式即可。

三角函数有非常多的化简方法，因此专门设置TrigSimplify类用于化简三角函数，进行如二倍角合并、平方和为1等化简操作，缩短最终表达式长度。

递推函数

对于递推函数，我将其看成一个因子，设置专门的parseFuncExpr()方法对其进行递归解析，最终返回一个解析后的Expr类对象。递归解析具体来说有两个过程，一是调用callFunc()方法，它负责将n替换为正整数，并将调用表达式中的实参带入形参，二是设置新的Lexer和Parser，来递归解析完成替换的递推表达式。

复杂度分析

第二次作用中复杂度最高的依然是用于预处理的preProcess类，而由于三角函数的加入，特判的情况更加多了，因此圈复杂度不可避免的提升。ToString方法是一个工具方法，主要包含了Mono类和Poly类转换为字符串的方法，也是需要针对多种情况进行特判，复杂度高也是难以避免的。

TrigonometricFunction类，其实就是专门用于处理三角函数的类，其复杂度过高的主要原因在于我在toMono()方法中，对三角函数内部的因子进行了化简操作，本来打算在第三次作业将这部分内容转移至专门的三角函数化简类，但考虑到三角函数化简的难度与复杂度已经极高，最终放弃。

第三次作业

代码结构分析

第三次作业在第二次作业的基础上，新增对于自定义函数的解析与求导运算。

自定义函数

自定义函数在定义形式上与递推函数较为类似，因此自定义函数类可以采用与递推函数类近似的结构与方法。

在解析过程中，将函数形参存储在ArrayList中，表达式与函数名存储在HashMap中，形成funcName -> Defination的映射关系，方便后续计算时进行调用。

计算自定义函数的展开式，需要将调用时的实参与形参进行替换。为避免形参与实参中的x的混淆情况，这里依然先将实参替换为a的表达式，后续再替换为x。替换完成后，使用parseExpression()递归解析其表达式，最终解析为Expression类。

导数

经过与其他同学的交流，我发现我计算导数的时机与其他同学不太一样。我选择在解析的过程中就将导数计算完成，并存储在Expression类的对象中。我的理由是，导数的计算过程与parse的过程有几分相似，同样需要递归的思想。因此我设计了dExpr()，dTerm()，dFactor()方法，为方便期间，返回值也分别是Expression，Term，Factor，来递归计算导数。需要注意的是，由于乘法导数规则的特殊性，Term的导数结果是加法形式，因此需要将整个结果看做一个表达式因子，然后返回一个包含该表达式因子的项。

另外，为了应对cos' = -sin的问题，我的Term也implements了Factor接口，而三角函数的导数方法返回值为Term。

复杂度分析

第三次作用相较于第二次作业而言，复杂度较高的类仅增加了Derivate类。该类复杂度高的主要原因是求导运算本身的数学性质所导致的。举例来说，假设一个Term中包含多个相乘的Factor，那么对该Term求导后，会产生一个较长的表达式。但是能够递归的调用求导方法，必须确保Term求导方法的返回值依然是一个Term，这就需要对求导产生的表达式进行“包装”，从而大大增加了复杂度。

架构设计体验

重构

通过观察前文的三篇类图其实可以发现，我的核心架构在第一次作业就已经确定下来，后面的作业仅在核心架构上进行功能的增加，并没有经历对于核心架构的重构。简单来说，之后两次迭代加入的类均继承了Factor接口，这样便可以服用Parser类进行解析，以及Mono, Poly类进行表达式计算。

但这并不意味着我们有进行重构。其中最大的一次重构是将预处理方法和ToString方法拆分出来，成为单独的一类。这样做的原因在前文也已经提到，就是与原来的类进行解耦，降低类的圈复杂度。

新的迭代？

• 多个递推函数：在我的设计中已经考虑到这种情况，只需要将不同函数的定义式按照funcName -> Definition的映射存储在HashMap中即可。
• 指数函数：往届似乎有这种形式的指数函数，那我认为它与其他因子并没有什么不同，设置一个指数函数类，包含一个expr属性，用来存储指数，在解析时，只需要调用parseExpr()方法对其进行解析即可。在计算时，调用专门用于处理乘方计算的polypow()方法进行计算。

总的来说，我认为我的程序可拓展性还是比较高的，毕竟我的二三次作业都是这么拓展来的嘛）

Bug分析

bugs

在强测与互测中，三次迭代作业共发现两个bug。

其一是第一次作业中，无法对进行正确计算，原因是我当时的指数是String类型的，而在判断指数时直接使用.equals()方法，这导致无法判断包含符号或前导0的指数。出现这样的问题是因为在写第一次作业时对BigInteger类还不熟悉，因此使用字符串直接存储数字，但完全忘记数字可以是有前导0的。

其二是在第二次作业中，形如f{n}(y,x)的递推函数在实参替换阶段发生了bug。我的实参替换是按照函数的形参顺序替换的，因此上面这个函数就需要先将y替换为含x的表达式，然而我的替换方法是字符串替换，即将函数表达式中所有的x均换为对应的实参，这导致“实参形参混淆”的bug。为了避免这样的bug，我将所有形参替换为含a的表达式而非含x，最终再将所有的a替换为x。

复杂度？

Method	CogC	ev(G)	iv(G)	v(G)
Expression.toPoly	6	1	4	4
RecursiveFunc.callFunc	3	1	3	3

其实通过我的描述也可以发现，这两个bug完全不是由于方法过于复杂或是if-else分支过多而导致的，只是在具体实现上有一些疏忽，因此有bug的方法和其他方法相比，各项复杂度均没有差别。

互测

我的互测流程基本上是：先用评测机跑复杂数据，在发现他人程序存在bug之后，通过分析代码或分析数据的方式，尝试用符合互测代价限制的数据进行hack。

评测机并不会根据被测程序的具体结构来调整评测数据，但我会在评测机发现问题后，尝试根据他人代码手搓能够复现bug的数据。

优化

其实上面已经提到了，这里再总结一下吧。我的优化点共4个，分别是：

• 将系数为正的项提到表达式最前

  具体实现方法是，更改Poly的getMonos()方法，返回一个经过排序了的ArrayList类型的monos。为什么要在getMonos的时候才排序呢，因为我的Poly中存储Mono的数据结构是个HashSet

• 正弦函数相加时，考虑是否能利用正弦函数的奇函数性质，即

  我为Mono类设计了negate()方法，用来为当前mono产生一个系数相反但其他内容均相同的ngMono，在涉及到三角函数相加时，不仅判断两个三角函数内的mono是否相同，同时也判断mono和ngMono是否相同。

• 二倍角在通常情况下也可以缩短表达式长度

  我专门设计了Math类，用于计算系数是否为三角函数幂次的2的n次倍，以确保化简更多的二倍角。

• 平方和=1

  这是最麻烦的一个优化，因为涉及到不同Mono之间的加法。我在三角函数化简类中设计了专门用于计算“能否进行平方和化简”的工具类方法，具体是通过比较两个mono的系数、单项式、除平方项以外的其他三角函数项是否相等，已经平方项是否具有相同的三角函数内因子，来综合判断的。

优化确实会对代码的简洁性与正确性产生不小的挑战。为了尽量保持简介性，我将所有三角函数的有关优化与三角函数类进行解耦，专门设计TrigSimpify类，但这依然无法避免代码复杂度的增加。主要原因是平方和的判断逻辑本身确实比较复杂，这并非是面向对象思想能够解决的问题。

心得体会 & 未来方向

从好的方面讲，本次作业让我对递归下降有了更深的理解（确实够深），对于课上学习的面向对象思想以及设计理念也有了一个实践、实验的机会，这些都是有益的。不过我认为这次作业的难度并不在于代码架构的设计，即面向对象思想的运用上，反而在于优化，即面向过程编程上。我发现对于三角函数的化简，其工作量大多在于”计算“，”判断“，而非”设计“，这似乎与本课程的目标有所背离。希望之后的课程能够弱化所谓”性能分“，而是将评判重点更多的聚焦于代码架构的设计上面，包括但不限于对于运行时长的评定、对于运存占用的评定等方面。