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具体位置。
类图分析
![类图](/i/l/?n=23&i=blog/3141594/202303/3141594-20230318212043042-1997519279.jpg)
类图如上。笔者项目的主要结构都由该类图显示出来,为了方便理解,我将所有的类拆分为了两个部分,一个部分是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行代码)隐藏在了宏观接口的背后。我也并不清楚这样的做法是否符合设计理念,但就笔者自己感觉来说,这样的设计还是挺优美的(笑。
基于基于度量的程序结构分析
![class metrics](/i/l/?n=23&i=blog/3141594/202303/3141594-20230318212920910-1441887583.png)
使用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