23年春面向对象第一单元分析与总结
目录
前言
架构
解析方法
数据结构
类图分析
基于度量的程序结构分析
BUG分析
互测相关
总结
前言
OO第一单元的作业主要围绕着表达式的解析，简化与运算展开。笔者在此简要的介绍一下任务背景：
1. HW1: 使用递归下降等方法对于符合一定文法要求的算式进行解析，要求展开括号并进行同类项合并
2. HW2: 新增了三角函数因子，并实现了不多于三个的不可相互调用的函数
3. HW3: 新增了求导因子，并且允许函数间的相互调用
总体上来说，第一单元的任务并不轻松，即使是上个学期修过OOpre的笔者在突然面对第一单元时仍然惴惴不安，手忙脚乱。在第一次作业时写出了bad smell code，并在第二次作业时推倒重来的。但是，在结束时回望，第一单元的任务虽然是完成了，但是实现的细节却不可以说是美观，具体的分析放在下面，各位一看便知（笑
架构
从总的架构上来说，第一单元的任务与其说是面向对象的设计，不如说是一个包装了面向对象外壳，实质是递归练习的面向过程编程。首先，我采用了递归下降的解析方法。由这种解析方法，自然而然形成了多叉树的数据结构，随后由于因子与表达式、三角函数与表达式、函数与表达式等相互嵌套的调用，使得我的程序变成了一个递归练习的集合：递归地解析，递归的展开，递归的化简，递归的输出......
解析方法
本单元作业中，我主要采用了递归下降的解析方法。按照我个人的理解，递归下降解析方法的精髓就在于，为每一个层次建立一个解析方法，当读入表征该层次开始的符号时进入专门解析该层次的方法，并在读入不属于该层次的符号时返回。更加正式的说法是：每一个非终结符（即语法规则中每个位于产生式左侧的符号）编写一个可递归调用的方法，通过方法之间的相互调用来处理嵌套的语法层次关系。 递归下降的解析方式是有固定套路的，其主要由两部分构成：词法解析器与文法解析器
//词法解析器
public class Lexer() {
private String str;
private int pos = 0;
private String curToken;
public Lexer(String str) {
this.str = str;
this.next(); //用于获取下一个有效符号的方法
}
public void next() {
if (pos == str.length) {
return;
}
char c = str.charAt(pos);
/* if (c 是一个满足文法的符号) {
pos++;
curtoken = c;
}
else {
做其他的判断
}*/
}
public String peek() {
return this.curToken;
}
}
//文法解析器，以本单元作业为例
public class Parser {
private Lexer lexer;
public Parser(Lexer lexer) {
this.lexer = lexer;
}
public Expr parseExpr() {
Expr expr = new Expr();
expr.addTerm(parseTerm());
while (lexer.peek().equals("+") || lexer.peek().equals("-")) {
expr.addTerm(parseTerm());
}
return expr;
}
public Term parseTerm() {
Term term = new Term();
term.addFactor(parseFactor());
while (lexer.peek().equals("*")) {
term.addFactor(parseFactor());
}
return term;
}
public Factor parseFactor() {
//此处就需要对各种因子进行解析：常数，幂函数，三角函数，自定义函数，求导因子
}
}
递归下降的解法逻辑清晰，易于扩展，出现bug的可能性也比较小，是比较适合第一单元作业的解析方式。同时，在解析过程中，善用抛出异常，可以检测到不合语法的输入以及程序中可能存在的bug。
数据结构
展开与化简的实现严重依赖于数据的组织方式。在第一次作业中，我是这样定义Term类的：
public class Term {
private ArrayList<Factor> factors;
}
可以想象，由于所有具体的因子都继承至Factor这个抽象类，在Term中对其进行统一管理的时候，不可避免的就会出现：
if (object instanof Constant) {}
else if (object instanof Power) {}
else if (object instanof TriFunction) {}
......
大量冗杂的判断巨量增加了方法的长度，使得程序运行低效且很容易出现bug。第一次作业中挂掉的强测点大多也都是因为这种复杂判断大量出现，在修改了的时候顾了这头丢了那头导致的错误。在第二次作业时，我推翻了第一次作业的代码，主要在数据的组织方式上面进行的重构：
public class Term {
private ArrayList<Constant> constants;
private ArrayList<Power> powers;
private ArrayList<TriFunction> triFunctions;
private ArrayList<Expr> exprs;
......
}
由于修改了数据存储的方式，使他们分类存放，不必要的判断大量减少，展开括号的方法瘦身到只有20行，第二次和第三次作业强测和互测均未再出现bug。尽管在研讨课中我注意到，使用HashMap容器可能更加便于简化和运算，但是由于改变数据结构是牵一发而动全身的关键要素，再在第二次作业的基础上进行重构，工作量巨大，令人望而生畏。故本单元的重构也就仅限于此。
展开与化简
笔者的展开与化简，在前言部分已经提到过了，是使用递归的方式进行的。具体来说，在Expr层调用Term的化简办法，在Term层调用Factor的化简办法，如果有作为Factor的Expr存在，则递归进入化简。这样做的好处就在于上层接口简单，可以在非常轻松的进行调用。缺点则在于嵌套结构过深，难以寻找bug具体位置。
类图分析
类图如上。笔者项目的主要结构都由该类图显示出来，为了方便理解，我将所有的类拆分为了两个部分，一个部分是controlling parts, 这一部分主要负责输入输出的控制，构建起了递归下降解法的基本框架。而另一个部分，框架当中作为组成部分的类和简化计算方法，我将其归在了data parts部分。在这种结构下，main方法相对来说会很简单，其只需要调用Expr一层的方法即可递归实现所有功能。实际上，我的main方法大概是这样的：
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
Parser parser = new Parser(new Lexer(""));
parser.parseFunctions(scanner);
String input = scanner.nextLine().replaceAll("\\s","");
Lexer lexer = new Lexer(input);
parser.setLexer(lexer);
Expr expr = parser.parseExpr();
expr.expandBracket();
expr.simplify();
System.out.print(expr.toString());
return;
}
大量的细节（1200行代码）隐藏在了宏观接口的背后。我也并不清楚这样的做法是否符合设计理念，但就笔者自己感觉来说，这样的设计还是挺优美的（笑。
基于基于度量的程序结构分析
使用metricsReloaded插件生成的对整个项目的分析如上。其中：
- OCavg : 每个类中所有非抽象方法的平均圈复杂度(继承的方法不计算在内)。代表类的方法的平均循环复杂度。
- OCmax : 每个类中非抽象方法的最大圈复杂度(继承的方法不计算在内)。代表类的方法的最高循环复杂度。
- WMC : 每个类中方法的总圈复杂度。代表类的总循环复杂度。
可以看到，由于递归调用的存在，Expr,Term中存在着大量名字相同、功能依次细化的方法。随着三次任务不断迭代，Expr与Term成为了不折不扣的巨类，大量新增的功能往其中添加，使得代码复杂度不断增长。Parser为文法解析器，大量的判断结构倒是无法避免的。递归下降的结构也使得文法解析器的逻辑相当清晰且易于调试bug。因此虽然其复杂度略高，可扩展性和可维护性却几乎是本项目中最好的。Functions主要实现的对自定义函数的替换和解析。在此处笔者原本希望借用java强大的正则表达式功能实现对于函数的替换。但是作业中可能出现的嵌套情况可谓花样百出，防不胜防，最后不得不手动匹配左右括号实现对函数的替换。此处也许有更加巧妙的解决办法，但笔者是在实力有限，难以优化。
当然，高内聚，低耦合是一个优秀面向对象程序的基本要求。我们或许可以在本单元作业中学会一些降低代码复杂度，提高可读性和可维护性的方法- 采用HashMap等更加高效的容器
- 采用更加高效的算法，减少循环嵌套次数
- 将功能相对独立的方法独立出来，形成可反复调用的模块。比如：匹配括号，替换自定义函数
BUG分析
在第一单元中，笔者出现的BUG主要集中在第一次作业，主要原因是因为在分类判断Factor的类型中时漏判Expr类型的RE错误。在重构之后，错误根源被修复，第二次和第三次作业当中均未再出现bug。当然，这种正确性上的保证是以牺牲性能分作为代价的。如果对三角函数的化简，正负号等做更多的优化，也许还会揭露出现有代码中隐藏的bug。
互测相关
互测是OO课程当中的重要一环，也通常是最令人血压飙升的环节。相信每个经历过OO课程的人都久久不能忘怀。从第一次hack成功的欣喜，到第一次被hack的会心大笑，都是在OO课程中成长的一部分。
对于互测，我也尝试过使用测评机进行自动化“轰炸”，但令人遗憾的是，大多数情况下，测评机即使可以找到有效数据，也不能通过课程组对于互测数据的限制。因此，在第一单元的作业中，我只在第一次作业成功hack三次，在第二次和第三次作业中均未成功hack。据我观察，成功hack的数据大多也是通过手造出来的，这也从另一方面提醒了我比较缺乏对于数据的敏感度，对于逻辑测试，压力测试，边界测试等理解还不够深入。
总结
第一单元的作业有磕绊，但总体上来讲还是顺利的结束了。单纯就面向对象的思想和方法上来讲，OOpre带给笔者的那种醍醐灌顶的通透感远超OO第一单元。但笔者认为，OO这门课的性质本来就更偏向于实践，对于面向对象的理论缺少系统的的讲解并非过错。笔者也理应反省，面向对象的精髓不是说，而是做。与其讨论多做优化会不会导致更多不可预料的bug，倒不如先动手去做。与其积重难返不愿重构，不如学会先架构，后工程。笔者也期待着，在经历过OO的磨练过后，回望这篇博客，还能从中拾遗，学到更多现在没能领悟到的东西。
标签：Term,解析,递归,作业,面向对象,2023,年春,方法,public From： https://www.cnblogs.com/topady/p/17229725.html