【OO】BUAA OO U1--表达式计算
BUAA OO U1 单元总结
本模块以表达式这一结构清晰分明的语言作为载体，通过递归下降的方法解析出具有明显层次的语法树，这对于本次作业的架构设计有着十分重要的指导和提示作用：如何设计类？如何设计方法？如何实现？在思考并解决这些问题的过程中，我对于常说的“高内聚低耦合”、“封装与抽象”有了切身具体的理解。我认为可以用“层次”来总结这一单元：表达式语法的层次，解析的层次，类与方法设计的层次，封装的层次。我想在本课程解决“如何面向对象编程”这一问题的开始，理解并掌握“层次”这一重要思想是一个良好的开始！
程序结构分析
设计考虑
本次作业架构中设计的类可以分为主类，解析类，工具类，结构类，运算类。
主类是程序的入口，是抽象层次的最高层，负责输入输出的交互和其他类与方法的调用。每次迭代根据新的要求在主类中都会做出相应的更改，但是仍要遵循保持主类的高度抽象和简洁的原则。
解析类包括 Parser 和 Lexer 两部分，通过递归下降的方法将 Lexer 扫描到的 token 解析为表达式的组成成分。Parser 根据 Lexer 中当前 token 的不同，采取不同层次的解析方法。
工具类中包含预处理类 PreProcessor和函数相关的处理类。PreProcessor是对输入的内容进行简化和处理，使处理后的结果更简洁并且更符合直觉，如去除空白字符，去除前导零，合并连续的加减运算符号，从而简化输出。函数相关的处理方法包括对递推函数的解析类 RecursiveFunctionHelper，递推函数的实例化类 RecursiveFunction和对自定义函数的解析类 CommonFunctionHelper和自定义函数实例化类CommonFunction。预处理类的设计考虑在于将所有可能用到的字符串处理静态方法提取出来，作为一个静态工具类。函数处理类的设计考虑，以递推函数为例，递推函数的解析类 Helper，第一负责对递推函数的关键信息进行解析，如 形参列表是什么，实参列表是什么，系数是多少，跟随的表达式是什么；第二负责实现递推函数的计算，也就是让递推函数能够递推下去，我的考虑是，字符串是无法运算的，想进行递推运算应该将字符串转化为结构类，进一步转化为运算类进行运算得到结果。我的具体实现是将形参替换为实参再将替换后得到的函数对应的字符串替换掉递推中的函数，然后将替换完成后的字符串再进行解析，得到解析并运算后的函数表达式，将这一过程封装成的 callFunc()方法实现了让递推函数计算递推下去的设计。而递推函数的实例化类 Function 则是通过调用 Helper 中的 callFunc()方法得到该函数的表达式，并作为属性储存下来，实现了递推函数的实例化 。
结构类由解析类通过递归下降法解析出，由 Expr、Term、Factor 组成层次结构。其中 Factor 作为最底层结构具有统一的行为，通过 toPoly()方法转化为运算类，运算还需要其实现深克隆方法和求导方法，因此将 Factor 设计为接口，由各种具体因子类实现。具体因子类的设计中将其内容设计为属性储存。
运算类为实现表达式的计算而设计，包括 Mono 和 Poly 类。Mono 的具体形式为 ax^by^c*sin(i)*cos(j)。其中三角函数因子以 Hashmap 的形式储存，key 为其内部因子转化成的 Poly ，value 为其次数。Mono 中的主要方法有字符串转化方法和求导方法、深克隆方法，在设计字符串转化方法时我选择将其组成部分分别转化为字符串后再进行连接，从而降低其耦合度。Poly 由诸多 Mono 组成，主要方法为加、乘、乘方、取反、求导等方法，在进行计算时进行合并同类项等简化操作。
度量分析
| Class | OCavg | OCmax | WMC | LCOM |
|---|---|---|---|---|
| CommonFuncFactor | 1 | 1 | 7 | 0.42857142857142855 |
| CommonFuncHelper | 2.5 | 4 | 5 | 0 |
| CommonFunction | 1.71 | 4 | 12 | 0.5714285714285714 |
| DerivationFactor | 1 | 1 | 4 | 0.5 |
| Expr | 2 | 3 | 8 | 0 |
| FuncFactor | 1 | 1 | 7 | 0.42857142857142855 |
| Lexer | 2.4 | 8 | 12 | 0 |
| MainClass | 4 | 4 | 4 | -1 |
| Mono | 3 | 9 | 60 | 0.2 |
| Num | 1 | 1 | 6 | 0.3333333333333333 |
| Parser | 3.82 | 11 | 42 | 0 |
| Poly | 3.82 | 11 | 42 | 0.36363636363636365 |
| PreProcessor | 4.33 | 12 | 26 | -1 |
| RecursiveFuncHelper | 3.5 | 9 | 21 | 0.3333333333333333 |
| RecursiveFunction | 3.08 | 9 | 40 | 0.5384615384615384 |
| SubExpr | 1 | 1 | 4 | 0.75 |
| Term | 1.67 | 2 | 5 | 0 |
| Trigonometric | 1.5 | 5 | 15 | 0 |
| Var | 1.86 | 6 | 13 | 0 |
| Average | 2.485074626865672 | 5.368421052631579 | 17.526315789473685 |
由以上度量分析可见，圈复杂度（OC）较高的类有MainClass， Parser，Poly，PreProcessor ，RecursiveFuncHelper等，这些类中，Parser为对表达式不同层次进行解析，不得不存在大量分支，Poly，PreProcessor ，RecursiveFuncHelper等在设计中为保持连贯性我并没有选择对一些操作单独提取方法出来，导致OC较高。从LCOM（Lack of Cohesion in Methods） 来看，代码内聚程度整体表现我个人觉得还可以，个别如SubExpr类由于要调用父类方法导致LCOM较高也可以理解。
架构设计体验
第一次迭代
第一次迭代主要重点在于语法的解析，存在两种方法：递归下降法和正则解析法。为了保证后续迭代的可扩展性，我选择用层次更加清晰的递归下降法，这样可以建立起层次分明的语法树，也有助于指导类与方法的设计，后续根据新的迭代要求可以在语法树的某个层次结构上逐步添加代码，而不需要推倒重来。就像画一棵大树一样，我选择先把树枝高低错落地画出，后续画叶子的工作就可以在各自的树枝上进行，树叶枯萎也不会导致整棵树的倒塌。
第二次迭代
第二次迭代任务量较大，可以分为两大部分：三角函数和递推函数。对于三角函数，由于其引入导致Mono的统一形式不再是简单的a*x^b，因此我需要对Mono类进行调整，我选择用HashMap储存三角函数中的因子和其指数，由于在Poly类中计算时会对Mono进行合并同类项，而自定义类型作为键时就不得不重写hashcode和equals方法，对是否为同类项进行判断。同时为保证运算过程的正确性，要对Mono进行深克隆也需要重新实现clone方法。但是好在由于第一次的设计过程中对Poly及Mono的方法封装较好，因此只需要在方法内部修改即可，在更高层次看上去结构依然没有发生变化，这也让明显体会到了合适的封装和抽象的重要性。对于递推函数，我选择将其功能实现分为两部分进行，一部分告诉我递推函数是怎么算的（解析出关键信息如系数，参数等），另一部分帮助我算递推函数（转化为运算类进行计算）。实践证明这样确实可以减少内聚，更容易发现程序的漏洞。
第三次迭代
第三次迭代相较于第二次简单了许多，亦可以分为两部分：自定义函数和求导。对于自定义函数，其实现基本上可以认为是递推函数的子集，但是不能完全使用相同的方法，只是处理思路是相似的。我做的不太好的地方是没有将原有方法进一步结构，提取出可以共用的方法，导致这部分结构看上去显得臃肿。对于求导，我的思路非常简单，将需要求导的类型全部转化到运算类，定义基础因子的求导方法之后递归调用即可。还是得益于递归下降方法的使用和层次化设计，求导这一原本就具有明显层次的操作在此次迭代中非常轻松。
自定义迭代场景
如果把变量因子改为矩阵，即将原来的x看作一个1 * 1的矩阵，而后续迭代支持 n * n矩阵，同时增加求逆，求正则等运算，那么需要寻找合适的容器储存矩阵，并且对计算类Mono和Poly进行更新，使其计算能够支持矩阵运算。由于封装和层次化设计，只需要对部分类更新即可，其余类仍然不会有太大影响，就像在树枝上画上新的叶子，只是让这棵树更加丰满，不会改变这是一棵树。
Bug分析
第一次作业
第一次作业的Bug出在我没有仔细阅读形式化表述，表达式、项前都可以有一个正负号，再加上因子自带的正负号，可以有多个符号连续的情况，我仅以为只会有两个连续符号的情况，导致了Bug的出现
第二次作业
第二次作业的Bug有多个原因：
- 必要括号的添加逻辑错误，以为三角函数内的多项式只有一项的时候不需要添加括号，导致如sin((2*x))这样的情况处理错误，归根到底还是形式化表述理解不到位。
- 递推函数实例化时替换逻辑的错误，在进行形参替换时，我是按顺序遍历形参列表，用replaceAll()方法将式子中的形参替换为实参，这就会出现我替换进入的实参被误以为是下一个形参而被错误替换
- 由于递推函数的加入，在预处理部分去掉不必要正号时忘记了添加等号，逗号后的正号也是非必要正号的判断逻辑。
- 如sin(x)*sin((-x))的化简逻辑错误，忘记考虑指数为偶数时合并时不需要将系数取反。
- 在解析递推函数时，不需要把0-5所有的递推函数定义式全部存储下来，可以将已经用到过的存储下来，为复用做准备。
第三次作业
第三次作业的Bug出现在两处：
- 读取递推函数的实参列表时由于实参可以是多变量的自定义函数，不能再根据逗号划分实参。
- sin(0)^0化简逻辑错误，忘记考虑指数为0的情况。
分析
这些Bug的出现我觉得可以分为对形式化表述理解的不到位，迭代后出现的新的情况考虑不周，化简逻辑考虑不周等类型。尤其是第二点让我明白了，尽管架构具有层次性，但是新的规则和要求的引入可能需要对原有的功能实现进行修改，而不只是新的功能的添加，迭代一定要对原有的代码进行一次仔细检查，防止考虑不周或遗忘。
Hack策略
首先是摸奖环节，构造0，1-1，x-x等这样的数据进行边界检测和构造x^8*x^8此类数据进行压力。
然后是随机构造数据，通过评测机生成数据点，并和自己的输出进行对拍。
在代码量较少的时期，如第一次作业，可以通过检查他人代码发现其中的错误，但是随着代码量的增大，检查代码发现漏洞逐渐变得不太现实，通过评测机进行的黑盒测试就显得更加重要。因此搭建评测机是十分重要的，我本人因为太懒前两次作业都没有搭建和使用评测机，追悔莫及。
优化策略
优化与实现
我主要是针对乘法过程中三角函数的化简进行优化，因为加法化简需要比较的东西太多，虽然也可以做到，但我有点太懒了，下次作业一定改正。我的优化有sin(x)*sin((-x))^2这样的优化和二倍角sin的化简及特殊值的化简。二倍角的化简在Poly进行乘法时，先计算出所有的sin存储在HashMap中，再计算cos，在系数是偶数的情况下，在计算cos的过程中先寻找有没有可以合并的sin，如果有那么将合并后新的sin放回sinMap，这样做的好处是相比与先算cos再算sin，减少了化简后的sin还能继续和cos结合产生的递归过程。其他两个化简都比较容易。
反思
优化是给我的正确性造成不少问题的，优化一定要考虑全面，思维不能太局限，一定要谨慎再谨慎。同时此次作业我的化简都是在计算过程中进行的，我想其实可以将化简提取出一个工具类，这样能更清晰地观察化简过程，同时降低计算过程的圈复杂度。这一点我做的不够好。
心得体会
写在前面了，这里cv一下：
本模块以表达式这一结构清晰分明的语言作为载体，通过递归下降的方法解析出具有明显层次的语法树，这对于本次作业的架构设计有着十分重要的指导和提示作用：如何设计类？如何设计方法？如何实现？在思考并解决这些问题的过程中，我对于常说的“高内聚低耦合”、“封装与抽象”有了切身具体的理解。我认为可以用“层次”来总结这一单元：表达式语法的层次，解析的层次，类与方法设计的层次，封装的层次。我想在本课程解决“如何面向对象编程”这一问题的开始，理解并掌握“层次”这一重要思想是一个良好的开始！
未来方向
我觉得第一单元表达式这一设计相当的好，可以从细节上进行优化。如互测环节对于不能提交的数据给出具体原因，cost超出范围还是其他原因，能提供cost计算工具就更好了。我个人觉得这并不是拿来主义，一是计算cost不是本次作业的重点，二是既然有这个规定那么课程组肯定已经制作了相关的工具，重复造轮子没什么意义，不如让同学们把造轮子的时间和精力更多地放到设计和测试方面。最后，感谢课程组为我们提供如此精心设计的训练和付出的努力！