OO_Unit1
架构 && 迭代
应用最显著的是递归下降的设计思路。
我的代码分为三块儿大陆：Parser 负责解析，ast 负责整理，algebra 负责输出。三块儿大陆各司其职，立志于不做重复的工作。Parser 里的 Expr 类是它们的交通枢纽。
定义两个数据结构：ast 语法树（以递归下降的形式存储表达式），和 algebra 多项式（以标准输出结构的形式存储表达式）。
如图：尾缀带 Factor 都是继承 Factor 类的（这里无疑用接口更好，但问题不大就懒得改），其中 NumFactor 和 VarFactor 是叶子Factor，别的都是非叶 Factor。Expr 很特殊，它既包含非叶 Factor 的方法，又包含根节点的方法。
Factor 需要实现的方法，最初只有一个：toPoly。
algebra 的标准输出形式最初是 num*x^exponent。
对于输入的表达式字符串，我首先通过 Parser 将它转化成 ast 的形式来存储。ast 是一棵树，它会自动把表达式整理成递归下降的结构，可以通过根节点 Expr 访问。在 Expr 实现 toPoly 方法，把整理好的语法树导出成多项式的形式，此时已经到达了 algebra 大陆的 Poly 类。在 Poly 实现合并同类项方法和 toString 方法，将结果导出成字符串并输出。
以上是我的基本思路，具体实现在三次迭代中逐渐填充。
在迭代中要求实现的功能可以 按实现路径 分为 2 类，函数定义 和 函数调用。前者包括 HW2 中自定义函数的定义和 HW3 中递归函数的定义，实现方式均为通过与之前无异的方法存储一棵语法树作为模板。后者包括 HW2 中 自定义函数、指数函数、选择表达式（函数）的调用，和 HW3 中递归函数，求导（函数）的调用，实现路径为 识别输入字符串中的特定字符 -> 用解析出的实参（因子或者表达式）替换模板中的自变量 -> 把生成的子树挂在目标表达式树中的对应位置，从这个角度想，那个复杂的自定义函数语法树，与 ExpFactor 类没有任何实质上的区别，只是一棵大树一棵小树罢了。
第一次迭代
就是那个骨架。
第二次迭代
功能一：自定义函数的 定义 与 调用。
功能二：指数函数的 调用。
功能三：选择表达式的 调用。
需要注意深拷贝的问题，因为函数可以多次被调用，使用浅拷贝会得到几棵纠缠在一起的树。
第三次迭代
功能一：递归函数的 定义。
功能二：递归函数地 调用。
功能三：添加 y
功能四：求导函数的 调用
有关用来求导的数据结构：
我的第一反应就是在 ast 里递归下降求导，研讨课时发现多数人采用的在 Poly 里求导，这样对于 dx(x-x) 等情况会更快。
其实我有一个异想天开的想法，既然给这个项目加功能的路径就那么两条，那能不能实现一个 “加功能 功能” 呢？统一功能接口，然后在加功能的时候写回调函数。当然，这个纯属异想天开。
| Method | CogC | ev(G) | iv(G) | v(G) |
|---|---|---|---|---|
| Main.main(String[]) | 2 | 1 | 3 | 3 |
| algebra.MonoKey.MonoKey(BigInteger, BigInteger, Poly) | 0 | 1 | 1 | 1 |
| algebra.MonoKey.equals(Object) | 3 | 3 | 3 | 5 |
| algebra.MonoKey.getExpArg() | 0 | 1 | 1 | 1 |
| algebra.MonoKey.getXexponent() | 0 | 1 | 1 | 1 |
| algebra.MonoKey.getYexponent() | 0 | 1 | 1 | 1 |
| algebra.MonoKey.hashCode() | 0 | 1 | 1 | 1 |
| algebra.MonoKey.mulMonoKey(MonoKey) | 0 | 1 | 1 | 1 |
| algebra.Poly.Poly() | 0 | 1 | 1 | 1 |
| algebra.Poly.add(Poly) | 4 | 1 | 3 | 3 |
| algebra.Poly.addToSelf(MonoKey, BigInteger) | 3 | 2 | 2 | 3 |
| algebra.Poly.appendMonoBody(StringBuilder, MonoKey, BigInteger) | 17 | 2 | 12 | 14 |
| algebra.Poly.appendSign(StringBuilder, BigInteger, boolean) | 6 | 1 | 3 | 4 |
| algebra.Poly.buildExpText(Poly) | 2 | 2 | 1 | 2 |
| algebra.Poly.constant(BigInteger) | 1 | 1 | 2 | 2 |
| algebra.Poly.equals(Object) | 3 | 3 | 3 | 4 |
| algebra.Poly.hashCode() | 0 | 1 | 1 | 1 |
| algebra.Poly.isFollower(BigInteger, boolean, boolean) | 1 | 1 | 3 | 3 |
| algebra.Poly.isPureExpFactorLike() | 6 | 2 | 2 | 7 |
| algebra.Poly.isZero() | 0 | 1 | 1 | 1 |
| algebra.Poly.liftMono(Unit) | 1 | 1 | 2 | 2 |
| algebra.Poly.multiply(Poly) | 3 | 1 | 3 | 3 |
| algebra.Poly.negate() | 1 | 1 | 2 | 2 |
| algebra.Poly.packExp(StringBuilder, Poly) | 0 | 1 | 1 | 1 |
| algebra.Poly.positiveToFront(ArrayList |
3 | 3 | 3 | 3 |
| algebra.Poly.pow(BigInteger) | 5 | 1 | 4 | 4 |
| algebra.Poly.toString() | 4 | 4 | 2 | 4 |
| algebra.Poly.zero() | 0 | 1 | 1 | 1 |
| algebra.Unit.Unit(MonoKey, BigInteger) | 0 | 1 | 1 | 1 |
| parser.Lexer.getNumber() | 2 | 1 | 3 | 3 |
| parser.Lexer.getTokenType(char) | 1 | 18 | 1 | 20 |
| parser.Lexer.next() | 6 | 2 | 4 | 6 |
| parser.Lexer.peek() | 0 | 1 | 1 | 1 |
| parser.Parser.Parser(Lexer, Definer, DeepDefiner) | 0 | 1 | 1 | 1 |
| parser.Parser.parseExpr() | 17 | 1 | 8 | 11 |
| parser.Parser.parseFactor() | 19 | 11 | 13 | 15 |
| parser.Parser.parseTerm(int) | 12 | 1 | 7 | 9 |
我的 ast 类都写得很干净，这里就不贴出来了，主要是看 Poly 和 Parser。方法圈复杂度还勉强能看，我把 toString 拆分成几个功能模块之后就没有太恶心的东西了，但 Parser 还是让我很难受，这当然可以通过添加预处理类、降低 ParseFactor 内部的耦合度来解决，但我一直懒于修改。
不过好在这几个复杂度惊人的方法没给我招来 bug。
优化
- 这优化可以拿去出国赛了。
- HW1 只有一个正号提前……吧。
- HW2 和 HW3 的优化点相同，都是
exp内的 gcd 提取和exp拆分。- 我在 HW2 引入了 gcd 提取，提取思路是从 gcd 向下枚举因子，记录每个位数下的最大因子，得到一个不超过 10 个元素的候选集，然后暴力。这个方法有点笨，效果也很一般，但也是我想了挺久才想出来的，我最终找到一个性能最好而且在互测中不可能被 hack 的临界点，超过这个临界点就不记录、仅尝试
gcd、gcd/2……gcd/100。我后来知道其实最优解一定出在gcd~gcd/0之间，可惜数学能力不够，完全没往这个方向想。 - 我在 HW3 引入了
exp拆分，这个拆东墙南墙补西墙北墙的最优化问题，我想到的唯一一个解法是动态规划，实现的……还算可以，能看到效果。但是由于处理不完整造成了 bug，这个后面再说。
- 我在 HW2 引入了 gcd 提取，提取思路是从 gcd 向下枚举因子，记录每个位数下的最大因子，得到一个不超过 10 个元素的候选集，然后暴力。这个方法有点笨，效果也很一般，但也是我想了挺久才想出来的，我最终找到一个性能最好而且在互测中不可能被 hack 的临界点，超过这个临界点就不记录、仅尝试
几个显著的问题
- 组合优于继承，但我一开始就用了抽象类而非接口，后来懒得改。
- 没有预处理方法，事实证明
PreProcesser的存在可以省下很大功夫，前两次还看不太出来，第三次就很闹心了。直接导致Lexer爆复杂度和DeepDefiner又丑又长。如果再有类似的东西我一定要写预处理。 exp类没有指数字段，也没有什么灵活的修改空间，间接导致我 HW3 优化出锅（因为优化完的东西没法存）。
自动化评测方法
我纯古法的数据生成器。采用递归下降+模块式生成的方法。写生成器的过程中遇到了很多问题：递归以及递归下降层数限制、Expr 一类两用、是否允许 y、是否允许选择式……我最终给模块式生成整理出一套参数：(depth, isFactor, allowFunc=True, allowChoose=True, allowDeri=True, allowRec=True, allowY=True)，以更好地复用函数。
这个评测机在 HW1 中找出了自己的一个 bug，在 HW2 中找出了两位同学的 bug。但它有诸多不足，他没能测出 HW2 强测我的 bug，也没能测出 HW2 中我室友的 bug，前者是由于那个 bug 就是不好用自动化方法测出来，后者是因为我的数据生成器生成的选择表达式 == 两边只有同类型数据。
bugs && 互测
在 HW2 强测中出现 1 个 bug。在 HW3 互测中优化出 2 个 bug 被刀了 4 次。HW2 有效 hack 9 次，HW3 有效 hack 3 次。
HW2
强测 WA 了一个点，WA 进 b 房了😿：实在有点愚蠢，我把 PowFactor 里的指数改成了 BigInteger，但 Poly 里还是 int，面对 (((((((((x^8)^8)^8)^8)^8)^8)^8)^8)^8) 理所当然的溢出了。
我需要反思一下，为什么我的评测机没有查到这个点呢？其实是我的数据生成器太随机了，我只按照题目的要求写了格式规范，至于它具体生成什么全权交给 random 决定了。当然，我也有通过改变权重、改变常数范围的方式加强我的评测机，但幂次足够高的数据往往伴随着爆代价导致的 TLE，因此我 Poly 里使用 int 的 bug 完全被 TLE 掩盖了。
其实也怪我懒于手动构造数据，但我清晰地记得我刚进 HW2 就把 PowFactor 里的数据类型给改了，所以根本没想过自己会在这里出问题。还有，这种 “不对称” 问题 AI 应该是很好查的，我下次要交之前让 AI 给我盯一盯。
互测：像 (((((((((x^8)^8)^8)^8)^8)^8)^8)^8)^8) 这种点在互测是非法的，所以我没有在互测期间发现自己的 bug，也没被刀。
有个一穿 3 的点是：
1 | 1 |
简单粗暴有效。制裁使用字符串替换（除了能写明白这个的大佬之外）/随意实例化的人。
另有一个一穿 4 的点是：
1 | 0 |
这个 cost 计算很阴啊，我自己能过是幸运的，因为我到互测才知道这个问题。
还有一位代码处理不了连续符号的同学，他无法通过我的评测机的任何一个数据点，结果误伤了他好几次，私密马赛。
总之这个房间很欢乐。
HW3
强测没事儿。互测被 hack 惨了。
一个 bug 是很多人都中招了的，乘开优化少括号的问题。在 HW2 中，为了判断 exp 需不需要套一层括号，我写了一个 isPureFactor 方法，判断一个 Term 是否只是 Factor，判断方法为 constExit + xExit + yExit + ExpExit <= 1。显然，对于 exp -> exp*exp 的情况，这里会少一个括号。
另一个 bug 是类似 exp((2*exp((2*exp((2*exp(x))))))) 加函数嵌套。我在做优化的时候有考虑 TLE 的问题，所以我加了限制：项数增加到一定程度就不做优化了，可我没有考虑多层嵌套超时的问题。
不过没关系，优化开关一关，都是同质 bug😉。
心得体会
我习惯于先设计架构，再把所有的类和空方法都建出来，最后再填充具体实现，这样看着自己设计的骨架一点点长出血肉，当然每次都会经历断骨再生就是了。虽然后续的迭代过程很小心，但还是眼睁睁看着我的代码变得奇形怪状。
我认为本次设计最大的优点是功能清晰，没有出现 oopre 中出现的 “不知道有什么用的类”、“走错类的方法” 和 “互抢生意的兄弟类（甚至父子类）”。最大的缺点在于方法内部存在大量冗余逻辑，导致一些方法（特指 parseFactor 和 toString）又丑又长，甚至 checkstyle 不过、被迫拆分。
这个月的 oo 命途多舛，听说下个月的电梯更阴间，还是在清明假期……要带着 oo 爬山吗。
