BUAA_OO_2021_第⼀单元总结
BUAA_OO_2021_第⼀单元总结
第⼀单元的作业是对表达式进⾏求导，从第⼀次作业的简单幂函数，到第三次的三⾓函数和嵌套规则，难度逐渐递增。但都应当分解成五个⼦步骤分别进⾏编程：解析表达式、存⼊数据结构、递归求导、化简、递归打印。如果这第⼀步的分解都没有做好，⽐如有些同学写出了“⾯向字符串求导”、“⾯向字符串化简”的代码，就会使代码逻辑耦合过强，不易debug，⽽且很容易出现情况考虑不周到导致bug⼀⽚。
第⼀次作业
作业思路
数据结构
第⼀次作业是针对幂函数进⾏求导，写程序要先从数据结构下⼿，任何幂函数都具有⼀般形式
a 1x i 1+a 2x i 2+⋯+a n x i n  (其中a k ≠0，1≤k ≤n )
，因此可以⽤⼀个List<；幂函数单项式>来表⽰⼀个幂函数多项式，幂函数单项式则表⽰为Tuple<；系数, 指数>
的⼆元组。据此我确认了我的类结构：
为了优化化简合并同类项的效率，多项式中采⽤了TreeMap<；指数, 多项式>的容器。表达式解析
然后考虑解析表达式的⽅法。解析⼯作表⾯上是编程，实际上更像是在做数学证明，如何保证针对每⼀个合法的字符串都能正确解析为结构化数据需要⼤量理性的思考，出⼀条简洁且保证正确的路。我的思路是先根据加减号将多项式分割成单项式，再根据乘号将单项式分割成因⼦，为此我到了两个简洁的⽤于分割字符串的正则表达式（另外：考虑到空⽩字符完全没有⽤就在预处理时删掉了）[x\d](?=[+-]) 紧跟在数字或x 后⾯的加减号⼀定⽤于分割单项式(?<!\*)\*(?!\*) 单个*⽽不是两个连续的**⼀定是⽤于分割因⼦的乘号这样我就完成了解析⼯作，后续的求导和输出步骤都不难，关键在化简。优化⽅法
化简的⽅法不外乎以下3种：
已经化为⼀般形式
尽可能令第⼀项为系数为正，省去⾸项的正号x**2输出为 x*x 的形式可以省去⼀个字符可以证明这就是最优的化简思路
代码结构分析根据数据可以看出代码复杂度和类的耦合度都⽐较低，其中StringNoSign()涉及到了较为复杂的化简输出逻辑，需要针对单项式系数和指数进⾏⼆维的分类讨论，并不能进⾏进⼀步的降低复杂度。
测试⽅法
我利⽤python实现了全⾃动出题+判答案的测评机，进⾏⼤量的随机测试和部分⼿搓极限数据测试出题机构造⽅法
关于出题机，我的⽬标是：凡是合法的数据，均存在被⽣成的可能性。如果符合了这条⽬标，只需要测试时间⾜够长，测试的覆盖率就会逐渐接近100%。
⽽为实现上述⽬标，只需要翻译题⽬中提供的形式化表达，表达式中的可选项以⼀定的概率出现，以⼀定的概率不出现。
Class Cons CSA CSO CSOA LCOM OCavg OCmax OSavg WMC MainClass 0013131  3.00310.003Monomial 2227291  1.877  3.4728Polynomial 1117181
4.60
10
11.8023
Total    3.0  3.057.060.054.0Average    1.0
1.0
19.0
20.0  2.57
6.67
5.7618.0
1.0Method
CogC ev(G)iv(G)v(StringNoSign()13747Polynomial.parse(String)10349Monomial.parse(String)
9146Polynomial.addMonomial(String()6445……………Total 54364154Average
2.57
1.71
1.95
2.57
Loading [MathJax]/jax/output/HTML-CSS/jax.js
在尝试使⽤xeger⽣成数据时，发现项和表达式的⾃调⽤式定义并不能直接翻译成正则表达式，虽然勉强可以通过转换写出⼀个来，但是这并不是长久之计。
于是我直接⽤python进⾏编程，来实现递归和随机，事实证明这个做法是具有前瞻性的。在后⾯的作业中xeger的⽅法会完全失效或⽆法⽣成⾜够强⼒的数据，⽽我的这个⽅法只需要稍加补充就可以实
现⽣成新的数据。
另外不得不提到的是对同质测试数据的理解，举例来说对于数字，如果输⼊中出现5没有问题，那么把5换成6也显然不会有问题，这就说明5和6是同质的，在⽣成测试数据是不应该让⼤量同质数据出现。于是可以使⽤常数池这样的概念，如果需要⽣成⼀个常数，仅需从常数池⾥任意选取⼀个数就代表了所有的⾃然数，常数池应该包括以下数字：
边界值：如0、1、2、3
⼀般值（恶臭值）：如114514、1145141919810
超⼤值（应⼤于264）：如31415926535897932384626
格式奇异值：如00、00800、0008008000、0000114514
答案⾃动评判
感谢sympy的存在，判答案是⽆⽐简单的⼀件事，只需要预处理掉前导0、使⽤sympify转换然后调⽤equals⽅法就可以很快的判断正误。
关于测评
本次作业没有在中测、强测和互测中出现bug。
在互测时，鉴于⼿上有着不错的评测机，我将同房间同学的代码直接打包成jar放⼊评测机进⾏批量⿊盒测试，很快就发现了组内存在的所有bug，效率极⾼。
互测共发现了三个bug
第⼀个同学会将-1*x**-2输出为x**2，具体⼀看，原来是使⽤了⼀个将符号和绝对值分别保存，判断时把绝对值当数⽤了，这也难怪，他管常数类中绝对值的命名叫做num，管系数叫base，管指数叫index，命名望⽂失意，亟待改正。
第⼆位同学会错误识别-+-为负号，他的正则表达式⼗分复杂，完全看不懂逻辑，这可能是他考虑不全的原因。
第三位同学会对+x**+a+x**+b产⽣问题，也可能是因为正则表达式很复杂没有考虑全。
第⼆次作业
作业思路
数据结构
第⼆次作业中出现了三⾓函数因⼦和表达式因⼦，意味着表达式允许进⾏多级嵌套，数据结构需要进⾏⽐较⼤的改变，表达式的解析⼯作也因为括号的出现不能延续第⼀次作业的⽅式。于是我直接进⾏
了全⾯的重构。
主要的类包括表达式类Expression（⽤加法连接存储的各个项），项类Term（⽤乘法连接储存的各个因⼦）以及因⼦抽象类Factor（代表因⼦）。所有的类均实现了Derivable接⼝，实现了derivative()⽅法返回对象⾃⾝数学意义的导数。
表达式解析
因为这次作业出现了括号，没法到⼀个简洁的⽅式直接将表达式分割成项，如果⾮要这么做的话，则需要维护⼀个括
号匹配栈，写起来⼗分复杂，将项分割成因⼦时也同样需要使⽤括号匹配栈，让代
码的复杂量翻倍。同时，这样的解析⽅法将会具有O(N2)的时间复杂度，可能会被卡TLE。
于是我决定尝试⼤佬们在第⼀次作业时常常提起的递归下降。我参考了⽹上的理解的递归下降的思想，⽽在实现的时候，我不想在每个类中都写复杂的字符串扫描⽅法，于是我实现了⼀个⼯具
类StringTool，只需要在构造这个⼯具的时候喂给它⼀个字符串，就可以问它能否扫描到符合条件的字符，如果有则⾃动将其消耗。（实际上，我曾尝试使⽤Scanner， Pattern这两个类，但是都不能满
⾜我的需求，于是才选择了⾃⼰创造）
于是，我的每⼀个类都存在⼀个参数为StringTool的构造⽅法，从其中读取⾃⾝所需要的字符并返回该类的对象，抽象类Factor则有⼀个⼯⼚⽅法make()来制造⼀个因⼦ 。
递归下降既可以将时间复杂度优化到O(N)，⼜可以⾮常简单清晰的表达逻辑，还有就是递归下降针对第三次作业对于错误格式的判断是⽔到渠成的。
优化思路
⾸先我认为将所有括号全部展开是不利的，第⼀是时间复杂度和空间复杂度都很⾼，第⼆是写起来⿇烦，所以我选择只拆那些拆了不会有影响的括号，然后带着括号直接进⾏求导。⾄于三⾓函数化简，
我认为这并不重要，所以就没有去做。以下是我做了的优化：
A+0=AA×1=AA×0=0A×B0=AA+(B+C)=A+B+CA−(B+C)=A−B−CA×(B×C)=A×B×CαA+βB+γA=(α+γ)×A+βBx2=x×x−A+B=B−A
除了最后两⾏的化简是在输出的时候考虑的，其余的化简都在读⼊的时候顺便实现，读到这⾥，你可能会认为读⼊和化简⼀起进⾏会导致耦合性变⾼，但其实不是这样的。我为函数的构造⽅法提供了很
多辅助函数，⽐如Expression类中的private add⽅法和Term类中的private mul⽅法，这些⽅法使⽤多种不同类型变量进⾏重载，⽅法的含义是使得当前类的数学意义加上(add)和乘上(mul)参数的数学意义。这些辅助函数会尝试解包，如果解包成功则会调⽤其他辅助函数，如果解包不成功才直接放到列表⾥，最终递归实现构造。这样的实现使得⽅法意义⼗分明确，代码结构不复杂，⽽化简的逻辑可以
⽅便的同时应⽤于解析和求导，使得时间复杂度也⼤⼤降低（相对于解析后不化简直接求导）。
代码结构分析
Class Cons CSA CSO CSOA LCOM OCavg OCmax OSavg WMC main.Expression5126271  2.316  4.3830 main.Factor0014141  5.00510.005 main.MainClass0013131  3.00312.003 main.Term4328311  3.73139.8756 main.factor.Constant1219212  1.333  1.838 main.factor.ExprFactor2221231  1.253  1.7510 main.factor.Function0016163n/a n/a n/a0 main.function.Cos2325282  1.783  4.4416 main.function.Power2225272  1.783  3.4416
main.function.Sin2325282  1.783  4.l.StringTool1819271  1.432  3.1410 Method CogC ev(G)iv(G)v(G)
main.Term.mul(Factor)18.0  5.07.012.0
main.Expression.add(Term)13.0  5.0  5.0  6.0
String()13.0  3.09.010.0
main.Term.derivative()11.0  5.0  4.0  6.0
String()9.0  3.0  6.07.0
main.Expression.Expression(StringTool)  6.0  1.0  4.0  4.0
With(Term)  5.0  4.0  3.0  6.0
main.Factor.make(StringTool)  4.0  5.0  1.0  5.0
actToExpression()  4.0  4.0  4.0  5.0
……………
Total138.00130.00142.00179.00 Average  1.77  1.67  1.82  2.29
从类的关系来看，各指标都基本低于阈值，符合⾼内聚低耦合的原则。
从代码复杂度分析数据可以看出Term.mul(Factor)⽅法复杂度超标了，原因是在⾥⾯对Factor进⾏判类并直接包办了所有乘法逻辑，这⾥的确应该将创建更多⽅法来分别办理不同种类Factor的乘法操作，不应该让该⽅法这样臃肿。
测试⽅法
本次作业延续使⽤了第⼀次作业的评测机，对于答案错误格式的判断主要依靠于sympy的sympify来判断，同时额外判断表达式因⼦是否后⾯跟了指数，这并不是完美的格式判定⽅式，也为第三次作业出错埋下伏笔
关于测评
本次作业没有在中测、强测和互测中出现bug。
互测时发现了两⼈共三个bug，其中两个是在优化时出现的错误，⽐较可惜
将相乘的表达式因⼦合并，没有注意到表达式因⼦不能有指数的格式规定
做了三⾓优化sin2(x)+cos2(x)=1但是如果仅有上式没有输出0⽽是输出了空串
没能解析(x+1)*(x+1)*(x+1)正则匹配递增写法
第三次作业
第三次作业我做的相当滑⽔，借助于第⼆次作业的良好架构，我只进⾏了少量的修改就完成了功能。⽽优化⽅⾯，合并同类项这件事变得⽐较复杂，我也没有追求完美的习惯，所以选择⾃暴⾃弃地放弃了所有合并化简。
测试⽅法
测试机仍然只需针对上⼀版本评测机进⾏少量的修改就可以完成针对所有Legal Format数据的⽣成。⽽在答案判断格式上，我仅采⽤了sympify的正确解析来评判格式，之所以没有在评判格式上下功夫是因为我对⾃⼰的输出模块很有信⼼，它在上⼀次作业中表现良好并且在这次作业中没有修改。最终我也因为⾃⼰的⾃信⽽付出了代价。
在互测开始之后，为了检测别⼈的程序输出是否有错误，我为评测机配备了输出格式检查，实现的⽅法其实很简单，只
需要对⾃⼰的Java作业进⾏魔改，保留输⼊模块即可。现在也会后悔为什么⾃⼰没有对⾃⼰的程序做输出格式检查，如果做的了话是可以轻易的查出⾃⼰的错误的。
关于测评
本次作业在强测出现bug，原因是出现了答案中sin(x*x)的格式错误。
互测发现了两个⼈的bug
题⽬描述是指数不得超过50，有位同学认为指数50也是错的
对-sin(x)**2求导时会多乘⼀个负号导致符号错误
⼼得体会
⾃动评测机应当先服务于⾃⼰的程序bug，不应该作为杀⼈的⼯具。本来想做⼀匹狼⼈，结果却被猎⼈带⾛，真是后悔莫及。
写软件最忌讳的就是拍着胸脯说没问题放⼼⽤，那⼀定有问题。只有严谨的思考，⾼覆盖率的测试才是程序没问题的保证。
OO课让我第⼀次接触到设计模式这个概念，让我眼前⼀亮，这应该是程序员技能飞跃的⼀个阶段，从掌握各种复杂逻辑的写法，能够完成各种任务，到可以设计架构，做到⾼效开发，写出清楚明⽩的代码这样的飞跃。这真的是能让我稍稍提起兴趣了呢。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。