第一单元总结

一、程序结构分析

第一次作业

统计数据：//TODO

• 类个数：3个

	Main	Term	Expression
属性个数	0	3+2	2+1
方法个数	1	15	7
最大规模方法	main:7	toString:27	Expression:33
总控制流规模	0	13	19
总代码行数	11	132	147

（均未包含静态属性）

• 圈复杂度：

相较而言，Expression的复杂度是最高的，而这是因为解析、求导与化简均放在其中进行，导致复杂度陡增，可以说是没有分摊好复杂度，没有很好的遵循面向对象原则。

从复杂度上来看，基本上没有什么太大的问题，就是少数方法，比如Term的toString方法，就是特判优化太多，而导致复杂度较高。

• 类图

Main类的设计思路是只负责字符串的读入与输出与表达式处理类的调用，全部在main方法内实现。

Expression类的设计思路是负责整个表达式字符串的预处理，分割与分析，项的生成与存储，返回求导表达式。其中字符串的分割与分析全在Expression构造方法中完成，利用全局静态的正则模式来完成；项的生成与存储（存在原始表达式的ArrayList中）就在每次分析出一个项的要素时进行，并在生成项后立即进行求导，存入求导表达式的ArrayList中。返回求导表达式依赖的是getDerivedExpStr()方法，按照一定的规律进行。

Term类的设计思路是负责本项系数，指数，系数符号的存储，并能够返回本项求导表达式。通过设置sgn,coe,exp三个属性来分别存储系数符号，系数，指数。获得求导表达式则按照sgn + coe + x + "**" + exp结合特判节省长度。

• 设计思路

本次作业的思路比较简单，由于没有WF判断，解析式子采用的是去空白符+正则+split()方法，存储模式采用的是ArrayList+Term两层多叉树结构，且求导式与原始式分别用两个ArrayList存储，使用字符串构造与拼接，字符串构造方法为特判与求导标准格式。

在这个基础上，再来实现基本的合并幂次，合并同类项，去0去1去符号。这些可以通过判断指数与系数在加入ArrayList时进行合并。

第二次作业

• 类个数：11个

	Main	Expression	Term	Factor
属性个数	0	3	4	0
方法个数	2	8	9	8
最大规模方法	main:17	origin:26	origin:34	0
总控制流规模	2	10	24	0
总代码行数	31	108	195	21

	Constant	Power	Trig	Exp
属性个数	6	4	5	4
方法个数	15	9	9	9
最大规模方法	origin:17	origin:22	derive:20	getOriginString:12
总控制流规模	5	9	8	4
总代码行数	102	86	89	77

	Operator	Key	Recognition
属性个数	0	2	0
方法个数	0	5	3
最大规模方法	0	equals:6	getFactor:60
总控制流规模	0	2	18
总代码行数	5	46	127

（均未包含静态属性）

• 圈复杂度

可见，当我将解析功能放在Recognition类中后，主要的复杂度都集中于此，但是降低了其他类的复杂度，使得其他类能够更加专心地完成各自的存储求导输出功能，可谓是有利有弊。

复杂的的地方集中在Recognition，Expression类中。两个get方法自不必说，解析需要循环前进，且进行大量判断，圈复杂度难以减少。但是origin方法只是将所存储的对象还原成表达式，可能是由于化简特判仍然较多，因而复杂度上升，但这不是必要的圈复杂度，应当被优化。

• 类图

与第一次作业相同，Main类同样是主打输入输出，只不过此处笔者再添加了一道程序，使用handle方法对字符串进行预处理，比如去空格，换**为^等，这样方便进行处理。而Expression和Term类与第一次作业类似，仍采用多叉树结构，只不过数据结构改为了TreeMap，分别托管表达式与项这两个抽象层级结构，只是我将分离生成这两个类的实例的方法转移到了Recognition类当中，使得Expression和Term两个项的功能更集中。

而在接口Factor中，我设置了几个重要的方法，用来访问共同所有的要素，比如指数（尽管常数与表达式因子没有显式指数），key等。四个具体实现因子类则不必多说，主要就是存储各属性以及根据各属性拼出原始式与求导式，值得一提的是，我在设计时规定只有常数存储系数（也即其本身就是系数），而其他的因子均无coe这一属性。这既方便了我的处理，又带来了隐患（后表）。此外，Exp类是Expression的子类，其实是为了方便加删括号而引入的包装，具体工作仍然在Expression内完成。

Recognition类呢，则专门负责解析与产生各类的实例，细节暂且不表。Operator接口，在设计完后发现并没有什么用（。。。），可能只是起到了对Expression与Term分类的作用，实在是一败笔。

Key类则其实只是为了配合TreeMap才设计出来的，以类别和指数作为关键字排序依据。其留下的最重要的“遗产”便是提供了几个类别常量，对我的分类与判断起到了很大的作用。

• 设计思路

第二次作业由于加入了嵌套表达式，三角等其他的因子，许多第一单元还能够使用的方法失灵了。大正则表达式，高耦合方法都很被这次作业拒之门外。为了降低在原来的结构上强行迭代的难度，笔者结合研讨课的内容，直接舍弃原来的方法，对代码进行了重构。我将层级划分为三层，分别为Expression，Term和Factor，这样可以各尽其职而又互相联系。为了拓展Factor的功能与泛用性，我将Factor设置为接口，再设计四个类来实现它：分别是Constant（常数）、Power（幂）、Trig（三角）和Exp（表达式）。到了这里，只要这颗表达式树构建起来了，求导就是一个递归访问树的过程。但是Parser呢？为此我考虑了耦合性，将解析器单独用一个类Recognition来实现，在内部使用正则将各个原子解析出来并装配好，返回组装好的实例，大概可以算是一个变异工厂了吧（。剩下的就是组织树的问题了。由于TreeMap需要键值，我便只得设计出一个Key类，用来编排各同层级元素的顺序。整个思路大概就是这样。

在解析的过程中，会出现分层解析的情况，那么上层解析器需要知道下层解析器在解析后到达的位置。考虑到解析器是返回实例，那么可以设计一个end属性，用来携带返回位置。尽管这样可能会提高耦合度，但是end只在解析阶段使用，而不会在其他位置使用，因而还是有一定的安全性保障。类似的，如果是返回字符串，可以使用不会出现的分隔符连接待返回字符串与结束位置，之后再进行解析。

除了基础功能外，还有优化的设计考虑。但我为了提高正确性，只涉及了简单的因子合并和去1去0去符号化简，并未进行同类项合并。

去0化简是通过判定用来拼接的乘式中是否有"0"来确定全式是否该为"0"，以及用来拼接的加式中是否有"0"以进行省略。去1化简则很简单，根据项所含因子数量来确定是否该省去1。去符号则是在读取组织项时进行的，无需进行过多处理。

但即使这样也有一个麻烦，就是返回的时候很难协调各因子之间的求导表达式，比如求导后，诸如三角这些函数可能又会带有系数，但我不能直接对表达式再进行合并了，因此我采取了一招铤而走险的方法，就是保证我的输出式负责格式，然后再吞入一回，反复如此直到表达式不缩短为止。这招非常容易TLE，所幸我的程序能够做到一次很快解析（PS：怎么不是数据结构竞速呢），因而侥幸逃过一劫。

第三次作业

• 类个数：11个

	Main	Expression	Term	Factor
属性个数	0	4	4	0
方法个数	4	11	13	7
最大规模方法	main:40	origin:24	derive:31	0
总控制流规模	5	12	21	0
总代码行数	31	115	188	21

	Constant	Power	Trig	FormatException
属性个数	4	4	6	4
方法个数	12	11	12	2
最大规模方法	origin:18	origin:20	derive:20	FormatException:3
总控制流规模	4	9	16	0
总代码行数	98	93	126	15

	Operator	Key	Recognition
属性个数	0	5（final）	0
方法个数	0	0	9
最大规模方法	0	0	getSin/getCos:59
总控制流规模	0	0	82
总代码行数	5	45	356

（均未包含静态属性）

• 圈复杂度

可见，最复杂的Recognition类平均圈复杂度达到了8，主要是就是解析器*造得太猛了，有限状态机和递归下降贡献了不少的复杂度。其他的类则比较中规中矩，平均而言都不算太复杂，算是比较好地分摊了代码复杂度与代码数量。

可以发现，主要的几个复杂度较高的方法都聚集在Recognition类中，而且是几个获得因子的方法，这几个方法都使用了有限状态机，因而圈复杂度较高。但总体而言，其他的方法都比较简单，没有出现太多的复杂的地方，这可能是递归下降将复杂度集中的特性？Maybe吧

• 类图

由于本次作业重构主要在于Parser，因此大部分类的作用都相同，我在这里只说一下更改的类更改的地方。

Main类去掉了预处理，因为有WF，只起到输入输出与宏观控制表达式的作用。

Recognition类则经过了较大的更改。首先，正则不再使用，而是使用递归下降和有限状态机，这样可以很自然的同时处理表达式与探测错误。getFactor方法被拆分成几个部分，分别去对应几种因子的解析，再由getFactor统一判断与调用。此外，还引入了单独的封装函数getBlank和getNum来进行复用，以简化代码复杂度。

Trig类新增一个Factor引用变量用来携带其所含的因子，并且更改求原与求导方法。

Key类被去掉几乎所有的属性与方法，只保留五个常数，相当于一本字典。

Exp类被去掉，直接将Expression暴露给外界调用。Expression也因此需要实现Factor接口。

FormatException为新引入的类，其用来在表达式多叉树中携带WRONG FORMAT!信息，逐级向上传递。

• 设计思路

设计思路基本类似于第二次作业，只需新增WF判断和嵌套三角函数及对应优化即可。

针对WF，笔者索性将小正则直接去掉，重构为递归下降，在因子层面读取时，采用switch-case形式的有限状态机对因子进行逐个字符的判断，以真正做到各层的事情各层干，各层的错误各层找，降低了耦合度。只要当前字符不符合期望字符，就给出错误信息。而异常的传递，则引入了新类FormatException，采用try-catch-throw-throws逐层向上传递，最终在Main类中捕获并处理。

其他地方也进行了修改，各个类中的TreeMap被改为ArrayList，简化掉不必要的排序功能，选择手动添加很少的调换正负项顺序函数。

为了让新添加的要求（指数绝对值不得超过50）与我原来多次读取处理的方式兼容，在Main类main方法中，对所捕捉的异常有不同的处理方式。第一次读入是判定错误，而之后的化简则不再识别该错误，而具体实现上则是通过设定一个静态status来表示main方法所处的状态，通过判断status来选择是否抛出错误。

另一个问题是字符串的边界问题，如果每次更改索引后都要判断字符串是否越界，则实在是过于复杂。在参考讨论区之后，我选择加上一对括号，并在最后加上不可能出现的字符（此次作业是!）。这样如果是正确的表达式，在读到错误字符前的右括号时，解析就将停止，而如果出现括号不匹配，就会读到那个不可能出现的字符，而这个字符必将在字符串结束前读到然后抛出异常，因而不用操心是否越界。而针对样例x)，则可以加上判断，结束时是否为倒数第二个字符，即可判断是否为正确的式子。

其余的优化大同小异，此处不再赘述。

二、bug分析

第一次作业

第一次作业是第一单元三次作业中最简单的一次作业，但是笔者在第一次作业上犯了一个较为低级的错误。

触发bug样例：0*x**19260817-0*x**19260816

错误输出：（输出空串）

错误原因：合并值为0的项时，采用的是忽略值为0的项，未考虑完所有情况，出现了指数不同但系数均为0的项无法合并，造成完全忽略所有的0项的情况的出现，又未对空串特判。

仔细设置断点检查后，笔者将bug锁定在了上述错误原因指向的位置：Expression类的getDerivedExpStr()方法返回值处。

bug修复：在设置了特判空串的语句if (str.equals("")) { return "0"; }后。bug得以解决。

除此之外，值得一谈的是优化问题。第一单元比较简单，优化是可以做到极致的。优化的方向在于合并同类项，优化系数1、项0、表达式前符号，调整项的顺序以及x**2->x*x。

第二次作业

第二次作业正确性较好，是三次作业中正确性最高的一次。在强测与互测中均未出现bug。

第三次作业

第三次作业正确性较为不好，出现了两种原因不一样的bug，分别被，尽管二者可以通过四句修改进行修复。

• bug1

触发bug样例：(x+x)*(1+1)

错误输出：WRONG FORMAT!

错误类型：WA

此错误一出，一开始肯定是令人大为费解的。一个WRONG FORMAT唯一能提供的信息就是我把本来正确的样例给判断错误了，可给不出其他有效的信息。

不过还好，由于我独（mi）特（huo）的化简方法是将式子反复读入，分析再输出来进行化简。在每次重输出之后加上输出语句，我便可以得到每次重输出的结果。结果如下：

((0)*(x+x)+1*((0)*x+1*1+(0)*x+1*1))*(1+1)+1*(x+x)*(0+0)
((1+1))*(1+1)+(x+x)*(0)
(1+1)*(1+1)
1+1)*(1+1
WRONG FORMAT!

十分的滑稽，居然出现了两边非同层括号被配对去除的情况。很显然，这个式子再被吞入后，就会被认为是错误格式的式子。面对这一bug，我几乎是瞬间就知道是哪里出错了，一时也不知道是喜还是悲。

定位到错误：

if (str.charAt(0) == '(' && str.charAt(str.length() - 1) == ')') {
            return str.substring(1, str.length() - 1);
        }

其逻辑为，当两侧均为括号时，即选择去括号。这在当时居然没有想清楚，实在是不应该。

将其改为

if (str.charAt(0) == '(' && str.charAt(str.length() - 1) == ')') {
            return str;//.substring(1, str.length() - 1);
        }

问题变得已解决，但是的确，有时表达式又有会套上括号了，这可以算是设计时没有注意到细节上的考虑，值得注意与反思。

• bug2

触发bug样例：x**192608171145141919810

错误输出：

错误类型：RE

Exception in thread "main" java.lang.NumberFormatException: For input string: "192608171145141919810"
    at java.lang.NumberFormatException.forInputString(NumberFormatException.java:65)
    at java.lang.Integer.parseInt(Integer.java:583)
    at java.lang.Integer.parseInt(Integer.java:615)
    at Recognition.getPower(Recognition.java:281)
    at Recognition.getFactor(Recognition.java:118)
    at Recognition.getTerm(Recognition.java:90)
    at Recognition.getExpression(Recognition.java:28)
    at Recognition.getFactor(Recognition.java:121)
    at Recognition.getCos(Recognition.java:208)
    at Recognition.getFactor(Recognition.java:115)
    at Recognition.getTerm(Recognition.java:90)
    at Recognition.getExpression(Recognition.java:28)
    at Main.main(Main.java:12)

很显然，错误已经被精确的指出来了。找到出现错误的行附近，如下：

if (Math.abs(Integer.parseInt(exp)) > 50 && Main.getStatus() == 0) {
    throw new FormatException("-51");
}

根据样例，错误信息，指定行的写法，bug原因呼之欲出，就是因为对指数的处理没有考虑到超大数出现的情况。我大意了啊，题目说明出现的指数不得超过50，就给忽略了超过int能够处理的数的出现可能。

而在将上述错误代码改为

if (new BigInteger(exp).abs().compareTo(new BigInteger("50")) > 0 && Main.getStatus() == 0) { 
    throw new FormatException("-51"); 
}

后，错误迎刃而解。

总之，这两个bug一个来自互测，一个来自强测，从两方面分别锁定了我的两个错误。尽管只是细微实现上的差异，但就是带来了相当大的影响，可谓是一招不慎，满盘皆输。因而我今后要重点关注细节，仔细思考其完备性，写出更加健壮的代码。

关于出现了bug的方法和未出现bug的方法在代码行和圈复杂度上的差异，我可以说没有什么差异，因为bug只是在个别的语句上出现的，而不是出现了系统性的bug。这也从另一方面提醒我需要多加小心，不被毫微之处绊倒。

三、Hack方法

第一次作业

第一次作业比较简单，因而出错误的点集中出现在两个方面：优化过头导致未顾及正确性，基础正确性不足。因而hack可以针对这两个点出数据。

具体来说，其一为构造一些合并同类项后为0的项，然后交替安插在表达式的不同位置，并选择是否插入与插入多少不为0的项，以测试优化与正确性是否兼顾。能够合并同类项得到0的项可以分为系数相反指数相同且不为0，系数不相同但指数均为0，系数相同且指数均为0，相反常数与连续0五种情况。然后观察是否过度简化而出现需要出现0的地方出现了空串。我自己的程序就是出现了这种bug，所以深有体会。其二是构造连续乘的幂，在各幂间再插入常数，以测试合并不同x幂次是否成功。

而针对基础正确性不足，则要么针对具体代码去推理出问题，要么暴力堆砌数据进行轰炸。由于笔者没有编写测评机，因此后一条路走不通，因而hack主要利用的还是前一方面的漏洞来进行设计。

第二次作业

第二次作业基本原理类似于第一次作业，笔者利用的也是针对某些可能出现的错误设计样例然后逐个试探。只是需要设计的样例种类变得繁多起来，想要穷尽是很困难的。因而我参考最危险的地方就是最安全的地方这一条准则，试探性地测试了一些基础样例。果不其然，一些简单的原子式可以测出bug来，而复杂的式子往往可以被逃过。这一条准则，说不定日后还可以再应用。

第三次作业

到了第三次作业，bug可以说会在任何意想不到的地方出现，即使强测也无法完全覆盖所有可能的错误（比如我的互测bug强测没能测出）。因此没有搭测评机的我很惭愧，这次只是靠侥幸碰上了别人的bug，而没有系统有效的方法。因而我唯一可以说的是体会到了数据生成器与测评机是相当高效的hack方法，而观看代码比较耗时，更加适合于有目的性的针对优良表现的代码进行学习而不是hack。

四、重构分析

在做作业的过程中，我早就听说了第一单元是重构重灾区。果不其然，第一单元我也进行了相当一部分的重构，尤以第二次作业重构为最多。

说起第二次作业重构，原因自然是第一次作业相对简单，用各种奇门遁甲都能够应付，而第二次作业所增加的需求迅速收紧了口袋。在听了第一次研讨课同学的分享后，我按照层次化的思路将Expression，Term，各种Factor类设置出来，并且准备了Operator与Factor接口用来抽象调用。但是在进一步设计逻辑后，我发现题目所给的Hint是二叉树结构，这样会造成树的可能层数过深而TLE。除此之外，也不是太好优化。于是我选择了层数浅的多叉树来进行组织，具体实现上又选择了TreeMap来实现每一层的引用组织，以保证顺序。为此Key对象被引入来进行关键字的比较。而在Parser上，我仍然选择了先去括号改乘方等预处理与因子解析正则的结合方式来进行解析。

重构之后，我认为，第二次作业在组织上更类似于面向对象的处理方式了，一颗逻辑多叉树以各种类的实例为结点，各个节点各司其职。但是有些地方我认为还需待下一次重构，比如Key类的设计有点鸡肋，TreeMap徒增复杂度却没有带来重大收益等等。

第三次作业重构，主要重心在于Parser的重构，关键是怎样设计一个既能判断错误又能解析式子的解析器。经过权衡抉择，最终我选择使用完全版的递归下降法，这样可以逐字符进行读取判断，并且只要设计正确，读到非期望的字符即可判断错误。而且写起来很有章法，没有太多需要顾虑的地方。唯一麻烦的可能就是长度，因为完全由自己来处理，可能需要耗费较多的时间。

第三次作业重构，并没有结构上的改变，主要是减少了Exp这种累赘的包装类，其继承与重写容易导致数据被错误修改，此外还减少了Key的功能，放弃了TreeMap的使用。以及一个重要的改变是将getFactor在逻辑上拆散，使得功能更加集中，这一个改动算是我认为最有成效的改动了。

PS：重构都是在签一次作业的基础上进行的，因此可以前翻到结构分析部分查找类图哦。

五、心得体会

作为OO的第一单元兼难度不低的作业，这三次作业从各个方面都让我深有体会。

首先是着手设计。第一单元第一次作业给人的感觉不会很难，因为式子没有嵌套，原子式简单，模式固定，只需要解决基本的识别与基本的拼接优化就可以算是完成了。但是，万万没想到，第一次作业该摔跤还得摔跤，并不是想象的那么简单，真正的应证了大意失荆州这句话的含义。除此之外，本次优化说起来是比较固定的，在乎情理之中，但是仍然让人感觉到意料之外。事实上，还是有包括我在内的很多同学没有优化到这两个点。还能怎么说呢，只是还需细致，细致，再细致了。

后两次作业才是真正的设计上就有了相当的难度。如果想着一次性搞定这样一个嵌套、多原子的表达式，那铁定是要吃苦头的。面向对象设计方法则正是解决这个的。尽管现在还只是入门阶段，但我认为面向对象通过把表达式有逻辑地拆分为相互独立但又互相联系的对象，可以减少耦合程度，降低代码复杂度，同时在分别编写各个类时可以各写各的，只要提前约定好了通信策略，则可以很方便快捷的构建起一个类组成的系统，最终化整为零，解决看起来十分复杂的问题。

其次是其他方面的保驾护航。写oo真的不只是在完成oo作业本身，还要让自己更有把握更舒畅的完成，而这就有赖于我们去学习许多新的知识来进行辅助。无论是测评机的编写，随机数据样例的生成，还是oo作业编写过程中各种方便工具的使用，都需要一定的知识储备。例如python方便的进行程序间通信，C简洁控制随机数据生成，各种容器的熟练使用，乃至多线程并行测试等。

最后，交流也是很重要的，交流可以让我们少走一些弯路，获取别人的经验，提高自己的效率，毕竟人多力量大。公司的职员也不是都是单刀匹马的干项目，更多的是互相帮助。只不过有一点，还是要杜绝抄袭，要用自己的手将自己所理解的思路表达出来，这样才能达到训练的效果。