OO第一单元总结
BUAA-OO第一单元作业
第一次作业
训练目标
借助对数学意义上的表达式结构进行建模，完成单变量多项式的括号展开，体会层次化设计的思想应用和工程实现。
题面
读入一个包含+、-、*、^、()（至多一层括号）的单变量表达式，输出恒等变形展开所有括号后的表达式，即最终表达式中并不含括号。
代码UML图
如UML图所示，除了MainClass主类外，还定义了Lexer词法分析器类、Parser语法分析器类、Expr表达式类、Term项类、Token类、Const常量因子类、Var变量因子类和Factor因子接口等，其中Token类中采用了Type枚举输入input中的一些不同的Token(可以理解为作为运算或符号的 “单元” )(例如ADD(+)、SUB(-)、MUL(*)、LPAREN(()、RPAREN())、POW(^)、NUM、VAR(x)、BLANK( || \t)等)。因此Lexer初始化时做的就是将输入字符串进行词法分析得到相应的Token类别分布并装入动态数组中，此外在lexer类中设置当前语法分析到的位置index和获取当前位置的Token、移动到下一个位置和判断当前是否到Token数组末尾的方法, 便于后续Parser进行语法分析。
基本定义
为了更好的叙述Parser类的功能，此处先给出此次作业的主要文法形式：
Expr-》{BLANK}[+|-]{BLANK}Term{BLANK}{(+|-){BLANK}Term{BLANK}}……
Term-》{BLANK}[+|-]{BLANK}Factor{BLANK}{(*){BLANK}Factor{BLANK}……}
Factor-》ExprFactor|Var|Const
ExprFactor-》(Expr){{BLANK}(^){BLANK}[+]NUM}
Var-》x{{BLANK}(^){BLANK}[+]NUM}
Const-》[+|-]NUM
其中，
{}：表示匹配任意个括号中的Token。[]：表示匹配0或一个Token。|：表示或。()：只是将其括起来，除了表达式因子外的那一层括号，这个是一定要存在的。
回到Parser
根据oop和课上学习到的递归下降的思想，在Parser类中定义三个假设已经实现好的方法(parseExpr()、parseTerm()、parseFactor()，其实其中最后一个是落到最后的，也就是 “叶方法” ，是需要实际实现的。
根据文法形式，观察到可能需要匹配很多的BLANK，因此设计了一个排除当前位置为BLANK的方法omitBlank()此外也经常需要进行对是否+或-符号进行判断，因此设计了isToken()方法，用来判断Expr、Term或Const的前置符号。
多项式相关
关于如何将多项式的信息通过递归至底向上的传到Expr层面，我是采用Expr、Term、实现Factor接口的三个类中是以指数为键，系数为值来构建HashMap<>，(例如，对于Const类来说构建的容器其实就是只有以0为指数，传入的参数为系数的HashMap<>，其他同理)因此Expr加Term或Term加Factor时并不是简单的加入容器中。对于前者来说，我先判断Term的HashMap<>中的多项式的系数是否已经存在于Expr的HashMap中( 这步非常重要！！！)，没存在的话当然是直接放入就可以了，否则根据Term的的符号将其HashMap中的值或+或-入Expr的HashMap中。后者同理，不过是从+或-变为*，不过由于ExprFactor可以带有指数的存在，这里的处理或许跟前者一样的话会有些许的麻烦，尤其在指数还是0的情况，因此我采取先对因子进行处理(注意这里只是处理并没有加到Term的HashMap中)，再通过subExpPow()方法判断Factor因子后可能的指数(这里对于ExprFactor因子指的就是它可能跟的指数，但是对于Var因子并非x后跟的指数，我这里将其与Const因子的处理方法一致——设为1，也就是让指数部分*1罢了)，这样一来，parseExpr()和parseTerm()方法只要根据文法进行相应的分析即可得到的正确的答案，注意文法一定要严格遵守，谨防漏或多，比如这里有可能出现BLANK那就要吃点它，再比如对于Const判断完符号后一定是NUM，不容置喙。
而parseFactor()其实本质上可以看成是三个文法的叠合，注意到三个因子的开头Token不同，区分开后根据文法进行相应的分析即可。
化简方法
此外，由于Term开头可能有符号，但将符号下传到每个Factor有可能会导致意想不到的错误，例：符号是负号，且Term只有偶数个Factor，最后Term可能会是正的(负负得正)，因此，为了避免上述情况，在对Term进行解析时，先用一个变量存储符号Token，然后最后再利用一个setZero()方法对HashMap<>进行符号设置。而因为最后返回的是Expr，因此需要根据需求设计print()方法，这里有两个性能分小技巧：
- 一开始先不着急遍历输出，要先找是否有正数，把它放第一个输出(
这样可以节省一个可能的负号，这也是我为啥会有一个)，然后再输出余下的数，printLg()方法，因为它专门用来输出正数 - 注意：系数为0的数就不要输出了，
多个0和负号多不值啊！当然要谨防只有0，那这时候可就要是输出0了(总不能一个输出都没有吧，否则连弱测都过不了，你猜我为什么知道)，其实在打印的时候用一个标记记录一下是否有打印就可以，只要有打印0就可以全部省略掉，否则就是没有输出也就是打印把0给忽略了，因此要额外输出一个0。
代码复杂度分析
方法复杂度分析图：
其中：
- 图中的
CogC代表代码的认知复杂度，即理解和维护代码的难易程度，主要考虑了代码中控制流结构的嵌套深度、循环结构。 - 图中的
ev(G)代表本质圈复杂度，衡量方法的可测试性，主要考虑方法中哪些控制流是由于方法本身的逻辑而不由嵌套或其他外部因素导致。 - 图中的
iv(G)代表内部设计复杂度，用来衡量类之间的耦合度，衡量一个类与其他类的交互、依赖数量及类内元素之间的关系。 - 图中的
v(G)代表圈复杂度，衡量代码线性独立路径数量，即表示为了测试代码所有分支所需测试用例的个数，其越高，代码控制流程越复杂，越难以理解，超过一定阈值，建议重构。
从代码复杂度分析数据可以看出，大多数方法的复杂度都在合理范围内，只有三个方法的复杂度超标：
Expr类中的print()函数，自认为是将太多的特判导致的，没有很好的利用类似于递归下降的方式进行最终的输出，导致输出这一复杂的工作堆积在Expr的一个print()方法中，使复杂度陡增。Lexer类中初始化方法，也就是词法解析的时候，因为对于输入的解析采用的是简单的if-else if-else的特判形式，使得结构十分冗杂，代码量暴增。- 在
Parser类中的parserFactor()方法中，由于我是直接在该方法内实现了对于因子类型的判断与解析，导致了代码复杂度较高，在下一次作业中，我为每一种因子都封装了一种方法，在parserFactor()中只需要调用相应方法即可，如此一来就降低了该方法的复杂度。
收获
加深对于递归下降的理解，对于一些Java语法和容器相关用法也有了更深的认识。
不足
1.可能的扩展性差：嵌套括号、多变量表达式、不同的因子，这些都可能造成相当大的影响，总归还是要不断打磨代码架构。
2.代码可能存在一些地方过于冗余或耦合度过高，需要多加排查，尽可能达到高内聚低耦合的要求。
3.由于处理输入时并没有将冗余的空白符从Token数组中去除，导致在omitBlank()函数中，没有充分考虑输入最后几个字符是空白符的情况，导致Token数组访问越界，已在互测中被人测出(QWQ)。改进：直接在处理输入时如果碰到空白符，直接不用输入进Token数组，直接省略掉空白符，实现好冗余处理。
第二次作业
新增迭代
支持嵌套多层括号
新增三角函数因子，三角函数内含任意因子，三角函数因子本身属于变量因子的一部分，与幂函数类似，由
sin(<因子>)或cos(<因子>)、^和指数组成，指数还是非负整数，指数为1可省。新增自定义递推函数因子，其也属于变量因子的一部分，定义方式为：
$fn(x, y) = 递推式(n > 1)$
$f0(x, y) = 函数式$
$f1(x, y) = 函数式$
其中，递推式是$常数因子 * f(n-1)(因子[,因子]?) +|- 常数因子 * f(n - 2)(因子[,因子]?)$，函数式是只含有形参的表达式，明确要求不含有自定义函数的因子。形式自定义函数的形参个数为1到2个，且只会是
x、y，且不会出现两种一个的形参，如$fn(x, x)$不合法。
新增形式化表示
Var-》PowFun | TriFun | RecFun
TriFun-》SIN | COS{BLANK}({BLANK} FACTOR {BLANK}) [{BLANK}^ {BLANK}[+]?NUM]
RecFun相关定义：
每次测试只有0种或1种形式自定义递推函数，由第一行输入告知。
若有，则接下来的三行可以任意一行是递推式，另两行自然为序号为0和1的初始定义。
其中，
一开始的朴素且愚蠢的想法
对于三角函数，由于三角函数内含的是因子，那Unit中存储三角函数的HashMap就以因子为键吧(乍一看十分合理，但是与我的架构是严重不相符的)。因为这样一来在后续的合并化简时，由最开始的初始Expr转化到的Poly向下递归处理经过Unit，有可能再经过Factor这一层回到表达式、项和因子这些只进行存储的类中，这样一来，不仅可能导致每经过一个表达式、项和因子都需要进行toPoly()方式得到Poly再进行处理使得有的已经Poly化的结果并没有很好的存储下来，还可能导致本来并不进行合并化简的类也需要给予equals()方法来进行判断，很显然，上述这些劣势会导致时间复杂度的提高同时也提高了类与类之间的耦合度，并不符合**”高内聚低耦合”**的需求，那么应该怎么办呢？ 重构即答。
对于递推自定义递推函数因子，因为我的Unit并未采取双变量的设计，但PowVar类中有变量类别这个属性来区别x和y，这样一来，其实我就将Expr、Term和Factor这些类归为存储输入表达式的存储类，而Poly和Unit这些类划为合并和化简的处理类，但是一开始比较错误的使用了字符串替换的方式来实现形参向形参的替换，但是这不仅会增加后续调用时解析成Expr的复杂度，还极有可能导致不合法的字符串，例如：对于f{1}(x) = x^2，f{1}(0)替换后的字符串应该是(0)^2而不是0^2，对，后者是并不合法的。这种陋习给我带来了许多意想不到的bug，比如一开始在进行自定义函数展开的时候我并没有充分考虑把常量因子乘入括号内可能带来的问题，其中我使用一个变量siganl来存储n-1调用和n-2调用函数之间的连接符(后来发现这根本就是画蛇添足），但其实只要存储一个的常量因子就可以了，也是将连接符也作为后一个常量因子的符号，这样一来会方便许多，直接调用parser.parserConst()方法即可，而两个调用函数之间当然是以+号连接。
此外，在强测中还出现了自引用问题，即自定义函数类中的myEquals方法比较的时候仍是将自身同输入的Factor因子进行比较，因此，当表达式中有两个自定义函数的类进行运算的时候，其中进行比较的myEquals方法会一直调用自定义函数的myEquals方法，导致爆栈，其实也就是没有落到实际能解决判断相等的类中，改成比较该类中已经替换好的Expr类的变量进行比较即可。还有对于拷贝运用的不熟练导致了些许奇妙的问题。因此，在强测的惨烈分数下，我最终还是尝试了重构。
重构
UML图
新增Token
SIN、COS、FUN和END，鉴于第一次作业的冗余处理不到位导致的互测被刀，这次并没有纳入BLANK这个Token，也就是不将其纳入Token数组中，当读到Token数组末尾时，使用END这个新的Token来标记。此外函数形参间的逗号也被纳入这个END中，用来表示第一个形参或实参的读入完毕。
新增类
将变量因子类Var去除并拆分成幂函数类PowFun、三角函数类TriFun、递推函数类RecFun(本来这样想的，后来直接将全部接收定义以及函数参数替换和调用都交给Definer类了)三个类分别实现Factor因子接口。
用Definer类替换RecFun类，大致想法就是用Definer类中的HashMap<Integer, Factor>来存储包括初始定义(0、1)在内的不同序号的递推函数，用num来表征参数个数，用var1、var2表征形参的字符(x、y)，用Const类型的num1和num2存储递推式中序号为n-1和n-2的递推函数的常量因子系数，用funN11、funN12和funN21、funN22分别表征递推式中序号为n-1和n-2的递推函数的实参，用funN来存储递推式中可能存在的最后一个表达式。
Unit最小单元类，代表最小单元，由于最后只有x一个变量，所以最小单元需要存储的只有系数、x的指数、sin函数的内部多项式和外部指数、cos函数的内部多项式和外部指数。
Poly多项式类，其中将多项式中的每个Unit用动态数组管理起来。
新增容器
由于对于sin和cos函数的加入，因此最终表达式的最小单位应该是$ax^n∏sin(factor)^i∏cos(factor)^i$的形式，因此在Unit类中应该增加x的指数和系数属性，以及sin内的Poly和指数之间组成的HashMap容器，对cos也同理。
此处的HashMap不同于一开始以Factor作为键，直接将Factor进行Poly化后的Poly作为键，这样一来可以很好的避免多个类之间的耦合，可以很好的降低复杂度。
对于Poly类，为了管理多个Unit相加减，需要维护一个存储Unit的ArrayList容器。这样一来，Expr、Term和Factor类只需要进行存储的工作就可以了，不用去考虑合并和化简的事。而Poly和Unit类则专注于处理合并和化简以及最后的输出即可。这样就可以很好的将存储和合并化简输出两种复杂的事分别处理，达到了各司其职的效果，而且对于第三次作业的自定义普通函数和求导因子也有很好的扩展性。
同时为了便于管理，在表达式类Expr中只管理组成它的项，由一个动态数组维护，项Term同样使用一个动态数组来维护组成它的因子Factor。
此外，在表达式类、项类和因子类都实现一个转换为多项式的方法toPoly()，用于最终的化简，相当于Expr、Term和Factor三个类共同维护一棵表达式树，而Poly和Unit类则负责这棵树的化简合并和输出。
而对于字符串替换的陋习，我也将其修改为因子替换的策略。因为我的架构本质上是Expr、Term和Factor一起组成一颗表达式树，而每个树节点提供一个toPoly()方法转化为Poly直接相应的合并化简，因此这里在遇到自定义递推函数时，自然的应该是把它当作一棵树，那么其中需要替换的就只有叶节点或者叶因子了，也就是PowVar类，这样一来就可以规避掉很多字符串替换带来的奇怪的bug。
代码复杂度分析
方法复杂度分析图：
由于方法过多，这里只展示一些复杂度超标的方法，其余方法均在合理范围内。可以看出此次，复杂度重灾区主要集中在Lexer、Poly和Unit类的方法上，其中Lexer类中的方法还是第一次作业的原因，但是并未想到什么好方法来解决，因为感觉使用正则表达式，一旦失误粉身碎骨。而Poly和Unit类中的超标方法主要集中在合并与化简得运算以及最终的输出上以及对于sin和cos函数的优化上，其中最严重的甚至认知复杂度达到了37！！！
此外，还有一些出乎意料的超标方法，比如对字符串进行预处理的去除多余的getOutMoreSign()方法的认知复杂度竟有16之高，是需要简化一下逻辑判断了。
优化策略
- 二倍角公式，$2*sin(x)cos(x) == sin((2x))$，具体操作就是遍历一遍因子的两个三角函数
HashMap看是否有内部Poly相等(包括相反数)的并且Unit的系数是2的倍数，这里只要sin和cos内的因子相等或者互为相反数，都应该以sin内的因子为最终化简的因子，因为对于偶函数cos来说，加个负号简直是轻而易举的事，一定要注意，你猜我为什么知道。 sin(0) =0、cos(0)= 1，分别遍历两个三角函数HashMap看是否有因子结果为0的，再根据三角函数类型转化为相应的常量因子。sin函数和cos函数的奇偶性，这里因为考虑到不是全负提出负号对于长度减少，所以这里只考虑sin和cos内的Poly的Unit全为负数的情况，对于sin函数来说将负号提到系数因子上，对于cos函数来说，就给Poly的每一个Unit置负。
第三次作业
新增内容
新增自定义普通函数(
g、h两种函数)，其中形参只有x、y两种，求导因子并不会出现在函数表达式中，函数表达式中允许调用自定义普通函数，但不会出现递归调用情况，不允许先调用函数，再进行声明，但是是与允许先声明再调用函数的。形式化表示同自定义递推函数类似。新增求导算子(
dx())，其并不会出现在自定义函数的函数表达式和递推表达式中。形式化表示如下- 求导因子-》
dx{BLANK}({BLANK} Expr {BLANK})
- 求导因子-》
对于自定义递推函数而言，允许调用自定义普通函数
UML图
架构修改
架构整体并不需要很大的修改，主要是针对两个新增内容进行相对应的修饰。
其一，对于自定义普通函数，需要在接收函数的类中，增加一个以自定义函数名字为键、函数形参列表为值的HashMap来方便不同函数调用时的实参替换。同时还需要添加存储两种自定义普通函数的函数式的HashMap<String, Factor>，方便按照函数名替换调用。
其二，对于求导因子的实现，目前有两个思路：其一，按照第二次实验提供的框架在Expr、Term和Factor的存储类中进行求导的化简；其二是遇到求导因子时，保留原始的Expr，在Poly化时，对其进行Poly和Unit层面上的求导，直接返回求导后的Poly。斟酌了一下，我认为第二种方法或许能够降低部分时间复杂度，同时也能符合Expr、Term和Factor等存储类只进行存储工作，合并化简在Poly和Unit类中进行的低耦合思想，此外，这样写的方法也会少一点，降低了出现bug的找寻难度。因此在Poly和Unit类中多了Derive()方法进行求导。
其三，多了一个Derive因子类来实现Factor接口，实际上存储的是一个Expr，也就是求导前的表达式，因此在其toPoly()方法中，是先将求导前的表达式先Poly化，先合并化简，再求导，这样的方式比先求导再合并化简会简单许多。
其四，Token需要多一个求导因子DER。
其五，将去除多余的空白符和去除多余的连续加减号的对于字符串层面上操作的方法单独出来放到一个Process类中，类似于Definer类直接使用类名来调用其方法，或许也可以称之为单例模式？
强测bug
强测出现了四个错误点，其中三个是CTLE，一个是化简错误。
其中，针对CTLE，我发现很有可能是我每个Expr和Term，以及在Poly在进行加乘运算时，使用了过多的deepCopy()方法，且对于这三种类的deepCopy()都是需要递归进行的，导致了过多的时间开销，去掉了些许不必要的deepCopy()果然都通过了，具体操作就是只在最底层的因子如Const和PowVar或Unit进行deepCopy()，其实也就是在进行toPoly()时底层的因子类和Unit类返回一个新的因子和Unit即可。
针对，化简错误，我认为很有可能是我进行的二倍角优化出了问题，我的处理是遍历一遍因子的两个三角函数HashMap看是否有内部Poly相等(包括相反数)的并且Unit的系数是2的倍数，这里只要sin和cos内的因子相等或者互为相反数，都应该以sin内的因子为最终化简的因子，因为对于偶函数cos来说，加个负号简直是轻而易举的事。为数不多的优化还背刺了我QAQ。
总之，深拷贝不宜多，优化简需谨慎！！！
代码复杂度分析
果不其然，Poly和Unit类的合并化简以及优化方法仍然是复杂度的重灾区，这也是由于过多的特判导致的。我认为通过在正确的基础上简化逻辑以及增加对部分功能的函数封装的方式可以十分有效的降低方法的复杂度。
关于测试
我是采用编写评测机同同伴安全对拍的方式进行正确性检验，不过由于样例的不可枚举性，即使完全随机也无法实现覆盖式测试，导致我在在这一方面也吃了不少苦头，因此，还需要去手搓一些边界样例，同时正确清晰的逻辑编写以及扩展性强、简洁的框架更是减少bug存在的前提。
关于扩展
我自认为我的框架还是有挺高的扩展性的，如果引入指数函数exp的话，只需要修改最小单元的属性，然后增加一个相应的指数函数类来进行一些初始化、Poly化等的工作即可。
关于互测
我是采用“人机结合”的方式有针对性的对于互测房成员的检测，也就是先用评测机将互测房内代码暴力跑几千组数据找出潜在的bug，对于其中那些比较难以判断是否为同质bug的样例，我会用该数据去单步运行出bug代码进行debug，并在修正后继续使用评测机暴力跑。
关于优化
因为，第二次作业的正确性并不是很高，所以第三次作业着重处理正确性层面的事，结果为数不多的二倍角优化背刺了我QAQ！！！所以沿用了第二次做的优化，没有新的优化的策略，属于是错怕了。
心得体会
- 正确性至关重要，切勿为了性能而放弃正确性，
那可是整整85昏啊，一切的优化都应该以正确为前提。 - 随时关注checkstyle，虽然有些地方
过于死板，但是大部分时候例如：行数过长、类过长等，都是你需要警惕的时候。 - 切勿闭门造车，及时关注讨论区，往届学长学姐的博客也是学习的好地方，因为有了好的架构就已经成功一半了，这里尤其**建议每次都将讨论区中的关于指导书的帖子关注，因为里面随时都有可能有人提出你没发现的指导书的
盲点**。 - 一定要重视测试，推荐对拍人数越多越好，
每个人都想要看看自己的代码在别人的评测机上会不会跑出奇怪的bug，评测机越多越好，毕竟是人搭的，课程组的也偶尔会出bug，因此，总是会有小瑕疵的，覆盖面不广也在所难免。 - 注意代码的可扩展性，写代码的时候不仅要认真实现本次作业的要求，还有在一些可能进行拓展的地方”留白”，为下一次的开发做准备，这里可以去参考一些往届学长学姐的博客来了解大致扩展方向。
微信
