2024 BUAA OO Unit 1: 从 + - * ^ 到简易科学计算器

一、前言

在面向对象程序设计中，我认为带着问题去设计程序是一件很有必要的事情。因此在这篇博客中，我会在每一次迭代设计的架构叙述中根据要求提出几个关键问题，再通过解决这些关键问题来呈现我的思考。

二、背景

给定一个只含有 x 的单变量表达式，完成对该表达式的化简（展开）并输出。要求：

输出最简无多余括号
输出越短越好

三、架构设计、考虑、分析、优化和反思

由于我在每一次作业中都记录了自己的设计策略和反思，我决定将架构的量化分析分析、优化和反思分作业呈现出来。设计考虑在下面的内容中都有体现。由于时间原因，我使用了puml语言描述类图，并利用graphviz将其转化为类图。

第一次作业

题目描述

输入的表达式满足以下要求：

只有关于x的非负整数幂
指数永远是非负整数
只有一层括号
输出不能有括号

数据限制

保证系数有可能爆 int
但由题目可知指数不会爆 int ，因为只有一层括号，而指数最大不超过8。

解决方案

在叙述我的解决方案之前，我希望能通过解决七个关键问题描述我的思考。

问题 0：我们需要做什么？总共有哪几个步骤？

与C语言不同，java作为一款纯度极高的面向对象编程语言，对于抽象化、层次化、模块化的要求更高，相应地性能肯定不如C的高耦合度代码。在这次作业中，我们应该思考的是如何在题目中找到对象，找到方法，建立抽象层次。而这一切又是从功能和数据的角度出发的。所以我们先来分析一下题目的功能要求和可能需要的数据结构：

功能要求：读入字符串、解析成表达式后计算表达式。

然后我们将功能需求拆解成不同的步骤：

读入——建立读取读取字符串类—— Java 中已经提供了scanner类用于读取字符串。
解析——建立解析字符串类 —— 可以建立一个 Lexer 类。但是在第一次作业中似乎不需要？我们先把这个问题放一边，看看接下来要做什么？
存储——建立存储表达式类 —— 这当然是必要的，其本质就是用特定的数据结构将表达式存储起来，那为何不建立一个类来存储这种数据结构呢？
计算表达式——建立计算表达式类…吗？ —— 完全没问题，毕竟计算表达式还是挺折腾的。但是用其他类的方法来实现计算似乎也可行…而且似乎可以一边存储一遍计算…再看看还有什么功能先吧。
输出——输出字符串类…吗？ —— 似乎没必要。一个方法就行。

上面没有回答到的问题我们会在后续看到答案。现在先看一下我们需要用到的数据结构

存储表达式——表达式类` —— 这似乎是最自然的想法，但是这并没有回答我们需要使用到什么数据结构。我们先把它放一边。
存储多项式——多项式类 —— 多项式和表达式有什么不同呢？多项式指输出结果前的数据结构，但是表达式指输入解析后的数据结构。两者当然可以使用同一个类，但接下来我们会看到，使用多项式类有它自己的好处。

我们的分析已经基本完成了。接下来我们进一步关注实现的细节。比如说我们在上面的分析中提到的第一个问题——需不需要Lexer？

问题 1：需不需要输入预处理？（Lexer）

这似乎是不必要的。因为加减号、正负号、乘号(asterisk)、指数符号(caret)会在表达式读入中才能处理，而括号和自变量需要暂时保留直到表达式用到他们。所以我们能做的就是把常数因子稍微处理一下。

但是从可扩展性的角度出发，进行预处理是好的。预处理能够将函数名称识别出来，将特定符号识别出来；我们可以用特定字符的符号属性来判断这个字符的类型，而不是用字符串比对的原始方法。而这一切都能使代码的结构更加清洗，使可读性更高，同时这也是更符合面向对象编程思想的方式。

下一步。

问题 2：如何分析表达式？如何存储表达式？

结合这次作业的抽象语法树已经数据结构课上学的内容，我们现在学了三个方式来处理表达式：

维护一个变量栈和一个符号栈，新符号的优先级不高于前面的符号时，就计算前面的式子。
转化为后缀表达式，再利用后缀表达式构建表达式树
抽象语法树 + 递归下降
第一种方式是我第一次接触到的计算表达式的方式。这固然好，但问题是不太方便从中分理处对象。第二种方式是我在数据结构课上接触到的方式，也是和抽象语法树非常相似的方式。问题是树太深了——毕竟是一个二叉树。理论上来说，同一优先级的不同操作数可以放在数的同一层。因此就有了我们的抽象语法树（AST）——其实可以把它理解成一种表达式树。

有了AST，我们就需要有构建AST的方法，遍历AST的方法和计算AST的方法。这三个功能需求虽然目的各不相同，但是他们的本质都是遍历AST。因此

问题 3：如何递归下降？如何保证递归的正确性？

题目是按照AST的思路给出表达式的定义。

表达式空白项 [加减空白项] 项空白项 | 表达式加减空白项项空白项
项 [加减空白项] 因子 | 项空白项 '*’ 空白项因子
因子变量因子 | 常数因子 | 表达式因子
变量因子幂函数
常数因子带符号的整数
表达式因子 ‘(‘ 表达式 ‘)’ [空白项指数]
幂函数 ‘x’ [空白项指数]
指数 ‘^’ 空白项 [‘+’] 允许前导零的整数 (注：指数一定不是负数)
带符号的整数 [加减] 允许前导零的整数
允许前导零的整数 (‘0’|’1’|’2’|…|’9’){‘0’|’1’|’2’|…|’9’}
空白项 {空白字符}
空白字符（空格） | \t
加减 ‘+’ | ‘-‘

递归下降的对象是AST，而AST是一棵树，因此递归下降的本质其实就是利用递归的方法遍历一棵树。而根据输入顺序进行递归意味着对这棵树的遍历是一次深度优先搜索。而递归的结束标志就是没有更多的表达式因子。

如何递归呢？很简单。表达式就是很多个项，遍历一个表达式就要先遍历全部的项；遍历全部的项就是遍历全部的因子；如果因子是表达式，那就遍历这个表达式。与之前我们接触到的递归不同的是，并不是一个递归函数并不是调用自己本身递归，而是几个函数相互调用递归。

graph TD
A(表达式)--> A1( - )
A(表达式)--> B1( 项1 )
    B1 --> C11[ -1 ]  
A(表达式)--> A2( + )
A(表达式)--> B2( 项2 )
    B2 --> C21(表达式^6)
        C21 --> D1( 项4 )
            D1 --> E1( x^+02 )
        C21 --> C211( - )
        C21 --> D2( 项5 )
            D2 --> E2( -00128 )
A(表达式)--> A3( - )
A(表达式)--> B3( 项3 )
    B3 --> C31[ x^2 ]
    B3 --> C32[ * ]
    B3 --> C33[ 2 ]

问题 4：如何得到答案？

我的实现方式是参考四则运算的方式来实现的。在只有四则运算的AST中，我们只需要递归调用getValue()方法，并且把每一个getValue()得到的数值在这一级进行运行然后将结果返回给上一级。

比方说，表达式的值是什么呢？是每一个项的值按照项之间的加减号运算后的结果。而我们怎么知道每一个项的值是多少呢？在表达式层，我们假设每一个项都能调用一个getValue()方法，这个方法返回的值都是化简后的一个唯一的数。我们再将求出来的这个表达式的值返回给自己的getValue()方法。这样子表达式的值就是int result = <表达式对象>.getValue()。

但是一个项的值是多少呢？我们也可以假设一个项是每一个因子的值相乘的结果。而每一个因子的值就是因子自身调用getValue()方法得到的。而因子的值是多少呢？在只有数字的四则运算中，因子只有可能是数字和表达式，如果是数字就直接返回数字，如果是表达式就返回表达式的getValue()方法进行递归就行。说白了，就是一个深度优先搜索，不过是通过递归的形式进行遍历的。这样子带来的好处就是编程难度被简化了——有时候如果不明说我们可能都意识不到自己用的是复杂的深度优先搜索算法。

但是在多项式的计算中，并没有一个直观的getValue()方法——毕竟得到的答案并不是一个数字，而是一个多项式。这就引出了第五个问题。

问题 5：如何存储结果（多项式）？如何输出结果？

其实在第四个问题中，我们已经有思路了，递归调用getValue()方法就行。我们假设每次返回的不是一个最简的数，而是一个最简的多项式。接下来，我们写几个方法用来计算最简多项式返回最简多项式。然后剩下的就交给递归和可靠的JVM就行。似乎也没有想象的那么难？

存储多项式更简单。每个多项式是由若干个单项式构成的。而单项式只有两个属性：系数和指数。这么简单的结构，写几个add, sub, mul, pow方法肯定也是轻轻松松信手拈来啦。

需要注意的是，在多项式的计算中要注意合并同类项，而合并同类项意味着查找同类项，意味着查找，意味着搜索。因此可以用一个指数到系数的HashMap来存储单项式，加速查找过程。

输出嘛…就输出呗。都写到这了还不会输出？

问题 6：有无优化空间？结构能否再清晰？

正的第一个输出可以不输出符号
快速幂？输入最高八次方，快速幂快不了多少…
一次方别输出，系数为1的正整数幂不用输出系数。
建立因子接口
建立多项式类和单项式类（可扩展性）

最终设计

类说明

类名	类型	功能
Main	类	主函数，功能不必多说
Token	类	表示将表达式预处理后的基本单位，如括号，常数等
Lexer	类	分词类。其主要属性为一个 `Token` 的 `ArrayList`
Parser	类	根据 `Lexer` 解析表达式
Expr	类	表示表达式（因子）
Term	类	表示项
Factor	接口	表示因子
VarFactor	类	表示变量因子
NumFactor	类	表示常量因子
Simple	类	表示多项式

UML类图

复杂度分析

方法复杂度

（方法很多，我只选取了其中比较复杂的几个方法。下同）

可以看到复杂度最高的是Lexer，因为Lexer中需要用到大量的 if-else 语句来判断 Token 的类型。 parseFactor 同理。单项式的乘法对于0的特判多一点。在本次作业中固然不需要这么多的0特判，但是我希望如果单独把单项式的乘法方法拎出来放到Junit Test中进行测试，这个方法也能符合我的预期要求。toString方法复杂的原因是需要寻找第一个正数进行优化。但是实际上我应该写一个方法来完成这个任务的。

类复杂度

Parser类复杂度高很大程度上是因为方法的内部聚合度太高。我在第二次作业中成功降低了Parser的复杂度。Simple的复杂度高是一件没有办法的事。Simple类表示最简多项式，其内部有几个算术运算方法，复杂度自然高。

性能分析

很快，但是还能更快。我加了多变量处理，所以慢一点点。但这为可扩展性留了条路。

互测经验

hw1 还算比较轻松，由正好被分到了零房，所以几乎没有遇到什么bug。说一下舍友的bug。

(2)^32 错误在于把 BigInteger 转成了 Integer 再与零比较，如果是零就表明这个 BigInteger 是零。想必错误的人没有怎么看过 BigInteger 的库函数。错误输出为 0 ，因为强转为 Integer 后确实等于0。
第二个错误原因太呆了。简单来说就是 HashMap 的迭代器是不保证有序的，尽管它在很多时候看起来是有序的。错误的同学把它当成有序的了，导致在一些奇怪的样例上得到了错误的输出。

第二次作业

题目描述

题目进行了小改动，未改动的地方没有列出来。自定义函数也没有列出来。

变量因子幂函数 | 指数函数 | 自定义函数调用
指数函数 ‘exp’ 空白项 ‘(‘ 空白项因子空白项 ‘)’ [空白项指数]
自定义函数调用自定义函数名空白项 ‘(‘ 空白项因子空白项 [‘,’ 空白项因子空白项 [‘,’ 空白项因子空白项]] ‘)’
输出要求：exp函数内必须是项，但是必须无多余括号

数据限制

指数不能超过8，但是可以不断嵌套。不保证指数不会爆 int （事实上它确实爆了）
保证自定义函数的定义表达式中没有其他自定义函数在内。

解决方案

问题 7：有哪些改动？

进行迭代的第一步设计就是考虑项目的哪些地方需要进行改动。按照我的实现，在第二次作业中需要大改的地方大概有：

变更单项式的数据结构，因此需要变更多项式的数据结构，重构多项式属性方法，引入单项式类使设计模块化层次化。
引入自定义函数类，可能由多个类共同实现自定义函数功能需求。
引入读取自定义函数的相关模块代码。
小改的地方有：
扩展Token 和 Token.Type 。
扩展Lexer 。
扩展Parser 使之能够解析自定义函数和指数函数。

我在实现第二次作业的要求的过程中进行了一次小迭代开发——先处理对 exp 函数的表达式的计算化简，再进行了自定义函数的读入。这样做有两个好处：

可以通过对第一个部分debug保证一部分已经正确，再处理第二部分。而不需要在全部内容写完后对着庞大的项目debug
第一次作业和第二次作业的输入格式不同。先处理 exp 还可以小改一下第一次作业的评测机接着用，而不用新写一个评测机。
先看引入 exp 后的单项式和多项式怎么存储。

问题 8：如何存储单项式和多项式？需要注意什么？

多项式的实现是简单的——多项式就是很多的单项式。如果需要的话，还可以往多项式中引入单项式之间的运算关系。我个人觉得不必要，因此省略。

单项式的实现也是简单的，单项式只有三个属性：系数，指数和 exp 函数中的多项式。

注意，这里面有一个小问题：循环定义。

问题 9：多项式属性包括单项式，单项式属性有多项式，这种循环定义如何结束？

我们之所以这样定义，是因为我们有需要这样定义的需求。因此得到循环定义的边界，就要回到这种看似无法停止循环的奇怪需求中。我们之所以这样定义，是因为 exp 中确实有多项式，但是这个多项式中并不一定有 exp 的因子。所以解决循环定义实际上很简单：让没有 exp 项的单项式中的多项式属性为空就行——这个空不一定是 null ，也可以是一个没有单项式的多项式对象。（但一定不能是零单项式，否则这种定义就停不下来了！）

定义解决了，下面分析多项式和单项式的计算。计算方法和第一次作业没有太大区别，但是需要着重注意的是判断同类项变复杂了。简单来说，需要递归判断同类项。

问题 9：判断同类项？判断多项式相等？

判断同类项是多项式和单项式运算的关键——指数由乘法实现，乘法由加法实现，而加法除了拷贝以外就是合并同类项了。可见判断同类项是多项式运算的基础。

解决方法不难。我们需要给单项式类定义两个方法：similarTo() 和 equalTo() ，在给多项式定义一个 equalTo() 方法。然后把它们全部写完就好。基本上只要自己写一遍就知道怎么办了。

此外， Z boy 等同学还提出了一个方法用来检查多项式和单项式是否相等，即判断相减之后是否为零。这在后续评测过程中有大作用，因为判断两个多项式是否相等的方法并不是带入数值——这样很容易TLE判断不出来——而是将两个多项式用数学运算的方式对扣，如果结果为0就说明正确。

此外多项式和单项式还需要注意的一点是需要及时把系数为零的单项式剔除掉——不剔除掉也可以，但是特判的地方会更多，冗余的数据也更多。

问题 10：自定义函数处理？

自定义函数处理是第二次作业的关键所在。调用自定义函数就是用实际参数（arguments）替换形式参数（parameters）。但是究竟如何实现替换？一般来说有两种实现方法：

字符串替换
对象替换

前者视函数为字符串，认为形式参数就是字符，调用只需要用实参的字符串取代形参的字符就行；后者视函数为表达式对象，认为形参是一个变量因子，调用只需要用解析好的实参因子取代变量因子就行。

虽然没有调查，但是我相信多数人使用的是字符串替换。我个人没有采用字符串替换，但是个人认为字符串替换需要注意两点：

先换 x ，或者一次把多个参数替换掉。
函数嵌套需要循环以下步骤：
1. parse
2. 获取实参的String
3. 替换
4. 检查实参有没有嵌套函数。有则重复以上步骤。
  我没有使用字符串替换，主要原因是觉得这个方法太奇怪了。试想如果别人问你你的项目中是怎么存储函数这个对象的，回答居然是用字符串存储？！我接受不了，我也不认为这是写一个多项式展开的项目应该有的思想。因此我使用了第二种方法，将实参作为因子对象替换函数表达式中的变量因子。

对象替换有几点需要注意：

替换时需要深拷贝一遍函数定义表达式，不然函数定义的表达式就被污染了。
如果后续处理的时候会对实际参数进行修改，那么实际参数也需要深拷贝。

从复杂度上来说，两种方法应该是差不多的。前者循环遍历建立表达式，后者递归深拷贝建立表达式。都把函数表达式遍历了一遍。

解决了自定义函数的大致处理思路，接下来需要关注的是自定义函数的具体实现。

问题 11：如何存储函数？如何调用函数？

在我的实现中，我写了两个类去管理函数。第一个是函数定义类（FuncDef）。这个类的核心属性是一个表达式对象，也就是一棵AST。第二个函数类是用来管理所有函数的（FuncCall），因此我引入了单例模式保证它只需要被实例化一次。 FuncCall 类最主要的功能是传入函数名称和实际参数，返回一个表达式，表示实参代入函数之后的结果。你看，我在描述 FuncCall 更多是注重描述它的功能——也就是这个类从外部去观测时是个什么样子。我个人认为这样新增函数比较方便，调用起来也十分舒适。

问题 12：浅拷贝？深拷贝？

深拷贝和浅拷贝是一个让我很头疼的问题，我也并没有实现的非常完美。但是经过第二次作业后，在多项式和单项式中，我对深拷贝和浅拷贝有一点思考。

我的多项式和单项式参照了 BigInteger 类的相关方法，但是由于我的单项式对象在创建后可以被修改，我放弃了。我认为在单项式和多项式对象中，一经构造，就不应当修改对象的值。每一次调用 add 等方法应当构造一个新的对象返回。

一切都解决了，剩下就看优化了。

问题 13：输出优化？

我为单项式类写了一个 optimize() 方法，返回一个新的输出更短的单项式。之所以这么写，有几种原因：

我只需要将所有出现过单项式的 mono.toString() 方法改成 mono.optimize().toString() 就可以正确完成优化后的输出了，而在我的设计里 mono.toString() 只出现过一次。因此改动起来比较简单。
如果设计时间真的赶不上第二次作业的DDL，我可以不调用 optimize() 方法，相当于把优化前和优化后的输出分离开了。

关于能否得到最优输出这件事上，原本以为还是像第一次作业一样可以轻松拿满。但是看到了 J boy 在群里的发言，发现事情似乎不简单。经过与舍友的讨论，个人认为将长度为n的表达式输出成最短多项式是一个NP问题。得到最短输出并不困难，但是当系数增大时验证最短输出，我认为是一件非常困难的事情。

举例：

$$
\begin{align*}
&exp((2xexp(x^2) + 2exp(x) + 2x^2 + 2exp(xexp(x)) + 3x)) \nonumber \
=&exp((xexp(x^2) + exp(x) + x^2 + exp(xexp(x)) + x))^2 * exp(x)
\end{align}
$$

另外一个例子，本质是拆成 0 和 4 ，只不过 0 和后面的相加消掉了。

$$
\begin{align*}
&exp((4+100000+200000x+300000x^2+400000exp(1))) \nonumber \
=&exp(4)exp((1+2x+3x^2+4exp(1)))^{100000}
\end{align}
$$

当系数增大的时候，不难想象还有更离谱的。系数分解的可能数太多了。据说 L Boy 完成了最离谱的优化并据说拿了满分。

具体来说，我做的优化大概有这么几点：

如果 exp 只有一个单项式且这个单项式不是一个常数，那么提出常数的绝对值这个因子到外边一定不会更糟糕。
如果有多个单项式并且这些单项式系数（的绝对值）的最大公因数（记为 gcd ）还不小，我们可以遍历 gcd 的所有因数来验证提出公因数后的新的输出会不会更优。
实际上，第二步只需要遍历 (gcd/1), (gcd/2), (gcd/3)...(gcd/9) 这最多九个因数就行。因为第二步一定会有不止一个单项式，除以 10 或者更大的数就亏了。
此外还加上了第一次作业的优化，即正数要放在最前面不加正号。

问题 14：反思？更好的设计？

单项式类和多项式类高度耦合，这样做并不好，只是我想不到更好的方法了。
优化时方法写得太乱了，没有贯彻 java 的模块化层次化的思想。
深拷贝用的太多了。正确的方式是让多项式和单项式一经实例化就不可更改，使之成为不可变对象。过多深拷贝导致运算速率大大降低，目测在第一次作业性能的到。这是一件很糟糕的事情。之后绝对不应该轻易改变一个类的属性。

最终设计

类说明

类名	类型	功能
Main	类	主函数，功能不必多说
Token	类	表示将表达式预处理后的基本单位，如括号，常数等
Lexer	类	分词类。其主要属性为一个 `Token` 的 `ArrayList`
Parser	类	根据 `Lexer` 解析表达式
Expr	类	表示表达式（因子）
Term	类	表示项
Factor	接口	表示因子
VarFactor	类	表示变量因子
NumFactor	类	表示常量因子
ExpFactor	类	指数函数因子
Poly	类	表示多项式
Mono	类	表示单项式
FuncCall	类	表示函数调用类。其主要属性为函数名到函数定义类的 `HashMap`
FuncDef	类	表示函数定义

UML类图

复杂度分析

方法复杂度分析

可以看到，复杂度最高的方法是寻找最优公因子的优化方法和单项式的 toString 方法，其认知复杂度最高。当时一个小时出头飞速写完，再花了一个小时 debug ，思路都想好了，但是代码结构方面属实没有怎么构思。但是两个方法以外有大量的方法的圈复杂度太高。说白了就是特判的 if 语句太多，应该把接口做得更好，少一点 if 多一点 for 。

类复杂度分析

可以看到单项式和多项式类的方法复杂度几乎要爆炸了，毕竟我为它们实现了很多的运算方法，并尽可能参考 BigInteger 标准库为他们写基本方法。而 Lexer 和 Parser 的复杂度是我感到惊讶的。我特地将 Lexer 和 Parser 的方法中case类似的语句中的内容进行拆解以提高可读性，因此我认为 Lexer 和 Parser 的复杂度应该不是大问题。

下面着重分析一下多项式类和单项式类的复杂度：

先是看看多项式类的80的WMC是怎么出来的。在这80点WMC中，有近40点是四个方法：多项式加减（add sub）、多项式是否是因子（isFactor ）和多项式的最佳公因数是多少（ bestCommonDivisor ）。学习了别人的架构之后，我认为多项式加减的复杂度主要来源于零单项式的特判；在判断多项式是否是因子的时候需要进行大量特判，在这方面我不认为可以化简；在求解最佳公因子时，使用单个方法完成多个情况的优化会使得这个方法的复杂度爆炸。可以将不同情况的处理转化为私有方法，增强代码可读性。

再观测单项式类的WMC复杂度。令我头疼的一点是：单项式类的复杂度并不是因为某几个方法过于复杂，而是单纯因为方法太多了。其中圈复杂度大于5的只有两个方法：判断同类项方法（ similarTo）和 toString 方法。后者可以直接将特殊情况封装为私有方法解决，但是前者的高复杂度来源于单项式和多项式数据结构的缺陷：零多项式的特判导致代码冗余。

性能分析

深拷贝太多导致性能太差，不过相比房间里其他同学，个人感觉自己的性能还不算太差，估计是因为深拷贝和情况特判导致时间复杂度的常数因子过大，导致运行时间长。但是复杂度的量级应该还是正常的。

互测经验

目测有这么几种错误：

0; exp(4294967297) 用 Integer.parseInt() 读入再转 BigInteger 。估计也是没怎么了解 BigInteger 库，或者是迭代着迭代着忘记自己以前写的东西了。
0; 1-1 第一次作业弱测第三个点，应当输出 0 ，实际输出空串，第二次作业弱测没有这种简单的点了。错得有点呆。
exp((-x)) 错误输出为 exp(-x) ，估计是当系数绝对值为1并且后面只有一个 x 或者一个 exp 时默认不输出括号。
exp(1)^2 * exp(2) 非常非常奇怪的错误。他会先把单项式加入一个 HashMap ，然后再遍历 HashMap 相乘。错在 exp(1)^2 和 exp(2) 在单项式上是相等的，标准库默认 HashMap 已经有一个项之后就不会再放一个相同的项了。所以错误输出成了 exp(2)
exp(2000000014*x + 5000000035) 出错的人找出了最大公因数 1000000007 ，然后线性遍历了它的所有的因子找出所有的因数用来验证提出来后是否会更短。线性遍历了所有因子……这是一个十位数的质数啊……出错原因 TLE

第三次作业

题目描述

加入求导因子。现在可以导了！
自定义函数可以由已定义的自定义函数定义。

数据限制

保证自定义函数中不会出现求导因子。

问题 15：有哪些改动？

准确来说，这次作业几乎没有改动。

求导方面，我为单项式类和多项式类各添加了一个 diff 方法，返回自身求导之后的结果就行。
自定义函数方面，由于我在读入函数的过程中就对函数进行了解析，而解析的过程中会顺带着把已经定义的函数一块解析了，所以自定义函数几乎没有任何改动。
优化方面，已经摆烂了。在我自己的设计中，如果要优化就得动手术，不甚好。

问题 16：有无优化？

其实第二次作业 J boy 就已经想出逆天优化了。他们真的把 exp 中的数拆开提公因子了，导致强测第13个数据点长了一个字符。阅读 L Boy 的帖子之后，思路大概是这样的。

首先一般只会多提一个 exp 出来，提两个 exp 说明里面缩短的长度至少 10，而这在一般情况下不太可能发生。
如果只提一个 exp 出来，就只需要拆解一项即可。而且拆解出来的两项中的一项应该是原本算出的 gcd 的倍数（如果可以的话应该还可以把另外几个数的 gcd 算出来）。如果拆成了，那就更新表达式。如果被拆成就继续拆，只要设置一个优化上限（一个全局变量不断递增或者设置时间）就能保证不会超时了。

最终设计

类说明

类名	类型	功能
Main	类	主函数，功能不必多说
Token	类	表示将表达式预处理后的基本单位，如括号，常数等
Lexer	类	分词类。其主要属性为一个 `Token` 的 `ArrayList`
Parser	类	根据 `Lexer` 解析表达式
Expr	类	表示表达式（因子）
Term	类	表示项
Factor	接口	表示因子
VarFactor	类	表示变量因子
NumFactor	类	表示常量因子
ExpFactor	类	指数函数因子
DiffFactor	类	表示微分因子
Poly	类	表示多项式
Mono	类	表示单项式
FuncCall	类	表示函数调用类。其主要属性为函数名到函数定义类的 `HashMap`
FuncDef	类	表示函数定义

UML类图

复杂度分析

方法复杂度分析

第三次作业的复杂度相较第二次作业并没有明显的改动。这里不多赘述。

类复杂度分析

第三次作业的类复杂度相较第二次作业几乎完全没有改动，这里不再赘述。

性能分析

和第二次作业一样，还是过度深拷贝和过度0特判导致程序性能大打折扣。虽然在第二次作业已经遇到这类问题了，但是还是不想给程序动手术重构。多项式和单项式两个文件就占了总代码量的一半。

互测经验

第三次互测有点难顶，愣是一个都没有测出来。bug大概有两种：

exp(-exp(x)) 输出格式错误。 和 exp(-x) 错的差不多吧。DPO居然没测出来。”看来核心技术（测评技术）还是要掌握在自己手里。“（by 第二位 L Boy ）许多同学的评测机都没法评测输出结果，因为大家都懒。卡格式错误很容易刀到别人。
第二种bug就难顶了。在拿到别人的代码进行测试的时候我就知道肯定有因为算法太差导致运行时间太慢进而导致出现超时的错误，但是有一说一真的构造不出低 Cost 的数据使得运行时间超过 2 秒。看了一下房间里其他人的hack数据，他们构造了

组里的一些同学 TLE 了。
甚至还有更离谱的：
1
2
3
4
2
g(z)=exp(exp(exp(exp(z))))
f(y)=exp(exp(exp(exp(g(y)))))
f(x)*g(x)-f(x)*f(exp(exp(exp(exp(x^8)))))
水群里更有甚者：
1
2
3
4
5
3
g(z)=exp(exp(exp(z)))
f(y)=exp(exp(exp(g(y))))
h(x)=exp(exp(exp(f(x))))
h(f(g(exp(exp(exp(exp(x^8)))))))
展开后有22层exp。 Cost 目测不超过1000。本人运行时间不超过一秒。组内一些代码运行时间不低于十分钟。我研究了一下这个问题。

看了一下被hack的天权星，设计者保留了太多不必要的因子（比如一个exp(x)会被拆成四个因子： x^0 1 exp(0) exp(x) ，而且有意思的是 1 和 exp(0) 会反复横跳相互转换），而这些因子会被保留到表达式计算的最后一步才被化简（调用一个名为 drop 的方法将不必要的因子或项丢掉）。虽然没有细看代码，但是根据运行结果看来也是指数级的了。

另外一个 bug 是第三位 L Boy 分享的。在他的设计中，每一个 exp 的 toString 方法都包括调用两次 exp 自身里面因子的 toString 方法（尽管调用一次后存下来然后下次需要用的时候再用也可以，但是他并没有这么做。毕竟如果有一个八个字母组成的方法名称能解决的问题，何必在存一个临时变量呢）。每一层的两次调用导致顶层的 toString 变成了一个完美的二叉树，也就是一个完美的的时间复杂度，导致超时。这真的并不容易发现。

估计房间里的天衡星也犯了类似的错误。此外他和 L Boy 都是通过调用 exp 内部因子的 toString 方法来判断该 exp 内部的因子是否等于0（如果内部因子的字符串长度为0就说明内部因子等于0）。这是应该是为了 exp(0)=1 的优化而设计的算法。

这倒是给我了一个启示：想调用 toString 方法就别再 toString 方法里面化简表达式。如果不化简的话，哪需要判断是否为0呢？如果建立了抽象层次的话就不会想着在一个 toString 方法里面完成表达式的计算和输出两件事情了。

四、Debug策略

本次迭代开发没有出现大bug，一些小bug已经忘得差不多了。因此我暂时省略了出现的bug。

整体Debug策略大概如下：

有简单数据就按照简单的数据进行debug。这个应该不用多说，简单的数据往往能最直接地暴露问题。
没有简单的数据就把数据变简单，剥离出其中核心的让你出错的地方。
没有数据就捏造数据，需要构建评测机。但是考虑到个人搭建评测机实在是过于困难和费时，可以参考大佬的评测机进行魔改。

debug注意事项：

debug一般情况下与运行结果一致，但是在一些特殊情况下不一致。目测导致这项改变的唯一原因是toString方法对debug的内容进行了修改。在IDEA中把toString方法关掉就行。一般来说如果 toString 方法对对象进行了修改，IDEA会在调试的过程中报一个Warning。
debug 可以采用由浅入深，类似二分搜索的方式进行debug。二分搜索的精髓之一在于先确定大范围，再一步步缩小包围圈，最终定位目标。由于Java的方法调用关系与二分查找的思想比较吻合，我们可以先找MainClass 的哪一步出现了问题，再查找 MainClass 中出问题的步骤中是哪一步出现了错误，层层深入，最终确定目标位置。利用步入和步过，仔细观察IDEA的堆栈，可以定位问题发生的位置、深度等信息；观察下方变量，可以确定当前位置的状态，判断当前是否异常。总的来说IDEA的调试能力还是很强大的。
多交流！！！ 自己犯的问题在很多情况下别人都犯过，只不过自己意识不到自己犯的错误就是别人犯的错误。
永远不要依赖数据点！永远要尝试自己构造数据！构造数据不是课程组的要求，却也是 OO 锻炼的能力之一。正所谓“核心技术还是要掌握在自己的手里”。
在修复暴露的问题之前，先仔细想想是不是有类似的问题还没有暴露出来。 比如说这次迭代开发中，我曾经发现我的多项式相加写的有问题，但是却没有想起来多项式相减的代码是几乎照抄相加的代码的。导致同一个问题de了两次bug，浪费了不少时间。

五、心得体会

设计建议

自顶向下进行设计。先构思需要用到的类（从数据出发（比如多项式的数据结构）或者从功能出发（比如函数调用）），再进一步构思类需要用到的方法，再进一步构思方法需要处理的各种情况。具体理由虽然我说不上来，但是从数据结构和行为需求构建整体代码框架再深入细节在整体设计把握上真的有大好处。
虽然说先构思再动笔，但是实际情况可能是：
1. 完全没有思路；
2. 构思了一大半，发现行不通；
3. 完成构思，发现不会写代码；
4. 写了一大半代码，发现行不通…
  个人认为这是非常非常常见的。比如在这第二次作业中，让我十分崩溃的事情是完成了多项式和单项式类的构思和基本代码，却发现单项式类有多项式对象作为属性，多项式类有单项式对象作为属性，循环定义直接把我整崩了。在遇到这种情况的时候，强烈建议多和同学交流架构设计，说不定你遇到的问题别人正好遇到了，说不定你眼中的难题在别人看来根本就不是事。
不要依赖中测数据点。

迭代感想

这次迭代开发还有许多不完美的地方，一方面真的很想看一看大佬们的设计细节，另一方面自己已经开摆了www。

总的来说吧，这次的迭代开发真的非常非常地好。在上学期的先导课中，我一直在用自己熟悉的面向过程编程完成各个任务。但是经过了第一单元的迭代开发训练，我慢慢开始接受面向对象的编程思想了。在我拿到新一轮的迭代任务的时候，我会试着思考我需要扩展那些架构，实现哪些功能，试着去思考程序中的不同模块在外界看来应该满足什么样的要求。这是我认为我学到的最有价值的事情。

六、课程建议

首先，真心感谢用心的吴际老师和面向对象结构与设计的助教们！经过多年的完善，面向对象结构与设计课程在我看来是最能锻炼代码能力的一门课。课程的代码量不是越多越好，但是CS需要有代码量的课程！

在今年的OO课程中，我觉得有一个小的改进建议：在 OO 迭代开发中，一直很难找到一份比较好的代码示例：实验的代码虽然规范，但是实现的功能太简单了；研讨课的同学往往只会分析思路，而不会给出代码（毕竟这是课程组要求）。但是这样子就带来一个问题：究竟什么样的代码才是真正规范，真正好的代码呢？课程组固然给出了通过面向对象的量化分析手段来分析，但却并没有指导同学们如何系统地利用这种量化分析手段。我觉得可以抽个时间讲讲这些量化分析手段，比如一节研讨课的十五分钟时间。

为什么我对源码这么执着呢？因为即便实现思路相同，程序运行效果仍然可能大相径庭！我和某位 Z Boy 的实现思路大致相同，但是在执行 (x+1)^1000 时，我的程序的运行时间却是他的三倍！能解决这个问题只有看具体代码，因此规范代码是一件我认为很重要的事情，而且如果能让同学们在进厂打工之前接触到一些厂里的规范——哪怕只是毛皮——也是工程能力提升的很重要的一环。规范的代码不容易得到，一种我认为比较可行的办法是学习现有的规范的开源的代码。或是让同学们去阅读简单的规范的代码，或是将复杂的代码进行缩减和抽象。

但不过无法实现也没有关系。现在的 OO 课程已经非常非常良心了！

Squirrel7ang's Blog

「BUAA OO」Unit-1 表达式计算

2024 BUAA OO Unit 1: 从 + - * ^ 到简易科学计算器

一、前言

二、背景

三、架构设计、考虑、分析、优化和反思

第一次作业

题目描述

数据限制

解决方案

最终设计

类说明

UML类图

复杂度分析

方法复杂度

类复杂度

性能分析

互测经验

第二次作业

题目描述

数据限制

解决方案

最终设计

类说明

UML类图

复杂度分析

方法复杂度分析

类复杂度分析

性能分析

互测经验

第三次作业

题目描述

数据限制

最终设计

类说明

UML类图

复杂度分析

方法复杂度分析

类复杂度分析

性能分析

互测经验

四、Debug策略

五、心得体会

设计建议

迭代感想

六、课程建议