面向对象课程 HW1

前言

本次 OO 作业经历过一次重构，而且重构的完成时间是在提交截止之后（哭）。所以强测寄的很惨，呜呜呜。（不过在房里刀的也很爽）

不过这份重构我个人是十分满意的。

特别感谢 sheep 和 toby 的帮助！

整体结构

类图如下所示：

Expr：表达式
Term：项
Var：原子项
Lexer：词法分析器
Parser：语法分析器
Tool：工具类

注：图中省略了若干构造函数和获取类属性的接口。

对各类的分析

Lexer

本类作为词法解析器。peek() 方法可以取得当前解析得到的词汇。next() 方法会继续取得下一个词汇。当读取到句末时，继续使用 next() 将会读取到一个空格。

评价：中规中矩的词法解释器，基本是抄课程组的。

Expr

本类是表达式。我对表达式的定义如下：

表达式由至少一个项连接而成。
表达式本身不含符号，由各个项决定各自的符号。

只有一个属性：ArrayList\，存储表达式内部的各个项。

具有 toString() 方法将表达式转换为字符串。

评价：或许应该将表达式乘法添加到其中。不过这样在运算过程中会涉及到一层额外的包装，可能有损性能。此外可以对表达式内部项进行排序，但是考虑到递归时可能带来的性能开销也作罢。

Term

本类是项。我对项的定义如下：

项由至少一个原子项相乘得到。
项本身默认的符号为正。在化简过程中符号根据项内部原子项符号改变。
输出项时会输出项本身的符号。

项包含两个属性：ArrayList\ 和 symbol。arraylist 内存储实际的内容，symbol 内存储项本身的符号。

具有化简方法、设置符号方法、深拷贝方法、取得常数方法、判断是否相似方法。

评价：项的方法普遍比较复杂，这个类也是逻辑上最复杂的类。项的化简方法的复杂度相对也比较高。

Var

本类是原子项。我对原子项的定义如下：

原子项要么是常数，要么是变量。
原子项含有幂次和符号。

原子项包含的属性：type 用于决定原子项的类型（常数或变量），num 存储常数，character 存储变量，index 存储幂次，symbol 存储符号。

原子项具有加减的方法。（仅限于常数运算）

评价：写的时候脑子一抽写了很多不必要的重载构造方法。实际上第一次作业中只需要两个构造方法就够用了。本类在第一次作业中复杂度较低。

Parser

本类是语法分析类。进行语法分析工作。

parseExpr：对表达式进行语法分析。
parseTerm：对项进行语法分析。括号的解析也将在这一层中进行。
parseVar：分析原子项。

其中对表达式和项的语法分析都会返回一个项的集合。对表达式的分析返回项的集合的原因不言而喻。对项的语法分析返回一个项的集合的原因如下：

对括号的解析处在项这一级。
解析到括号时，由于括号内部是表达式，解析项会将这个括号展开，于是会得到一个项的集合。
在解析项的过程中各个项之间都是相乘的关系。

评价：核心解析、化简流程皆在本类中进行。对括号的解析和对基本项的解析都可以新增方法以降低原有方法的复杂度。

Tool

本类是工具类。包含了一些通用的工具：

包含预处理和事后处理。
包含对乘法方法的重载。
包含表达式的化简方法。

之所以将乘法的重载和表达式的化简方法置于 Tool 内部是考虑到在 Parser 类中主要通过 ArrayList\ 的形式计算化简，所以需要在工具类中定义静态方法操作数组。

其中表达式化简的时机是在已经解析了表达式，返回表达式之前时。

评价：本类的方法全部是静态方法，供全局调用。重载了表达式与表达式、表达式与项之间的乘法。还做了必要的预处理和事后处理。预处理也可以说是化简流程中的一个精髓了。经过预处理后，无需考虑空格、连续符号的问题，对括号的解析流程也符合我自己定义的标准。

化简流程

预处理

预处理的流程：

去除所有空字符
将 “(” 替换成 “1*(”
将所有连续的正负号化简成一个符号
将 “*+” 化简成 “*”
将 “**” 化简成 “^”

经过预处理后，我们得到的字符串中没有任何的空白与连续的符号，并且乘方使用 “^” 表示后更加易于处理。

将括号前面添加 1* 是为了保证解析到括号时处于项的解析流程中。

使用 replaceAll() 正则替换就可以实现预处理。

解析

将表达式视作 表达式->项->原子项 的结构。即：

Expr = Term + Term
Term = Var * Var

对于符号，解析时首先将符号读取至原子项中，在化简过程中将符号归一到其所属的项中。

对于括号，整个解析过程是边解析边化简的。具体而言，在读取到括号时我会将括号内部视作一个表达式进行解析，返回经过化简后的 ArrayList\（ArrayList\ 与表达式在逻辑上是等价的）。

由于 ArrayList\ 与表达式在逻辑上是等价的，故 parseExpr() 与 parseTerm() 的返回值都是 ArrayList\。后者之所以返回数组是为了支持括号的解析。

处理括号

遇到括号时，在 praseTerm() 中递归调用 praseExpr()。在 praseExpr() 中将括号内的表达式分析、化简完毕再回溯到 praseTerm()（此时 parseTerm() 就会返回多个 Term）。

举例而言：对于 1+(x**2-1)*3，经过预处理后：1+1*(x**2-1)*3，在读取到 “(” 时处于 parseTerm() 的调用中。经调用 parseExpr() 后得到一个 ArrayList\。之后接着读取处理后面的 *3，最后返回的 Term 数组中包含 3*x**2，-3。

处理乘方

“^” 可能出现在 “xyz)” 的后面。于是在 praseVar() 中和 praseTerm() 中相应的位置直接进行分析、展开（暴力循环即可）。我使用 Var 中的一个属性 index 来存储原子项（xyz 与数字，不过数字的乘方采取直接计算的方法）的乘方。

事后处理

事后处理（ afterTreat ）的时候使用正则替换进行简单的优化。包括：

将 “^” 展开为 “**”
将 “+1*” 化简为 “+”
将 “-1*” 化简为 “-”
去除首位的正号

复杂度分析

method	CogC	ev(G)	iv(G)	v(G)
Expr.addTerm(Term)	0.0	1.0	1.0	1.0
Expr.addTerms(ArrayList\)	1.0	1.0	2.0	2.0
Expr.Expr()	0.0	1.0	1.0	1.0
Expr.Expr(ArrayList\)	1.0	1.0	2.0	2.0
Expr.toString()	1.0	1.0	2.0	2.0
Lexer.getNumber()	2.0	1.0	3.0	3.0
Lexer.Lexer(String)	0.0	1.0	1.0	1.0
Lexer.next()	3.0	2.0	3.0	4.0
Lexer.peek()	0.0	1.0	1.0	1.0
MainClass.main(String[])	0.0	1.0	1.0	1.0
Parser.parseExpr()	2.0	1.0	3.0	3.0
Parser.Parser(Lexer)	0.0	1.0	1.0	1.0
Parser.parseTerm()	19.0	1.0	9.0	9.0
Parser.parseVar()	8.0	3.0	7.0	7.0
Term.add(Term)	7.0	1.0	4.0	5.0
Term.addVar(Var)	1.0	1.0	2.0	2.0
Term.addVars(ArrayList\)	2.0	2.0	2.0	3.0
Term.addVars(Term)	1.0	1.0	2.0	2.0
Term.copy()	0.0	1.0	1.0	1.0
Term.getConstant()	3.0	3.0	3.0	3.0
Term.getSymbol()	0.0	1.0	1.0	1.0
Term.setSymbol()	1.0	1.0	2.0	2.0
Term.setSymbol(int)	0.0	1.0	1.0	1.0
Term.similar(Term)	9.0	3.0	5.0	7.0
Term.simplify()	8.0	2.0	5.0	6.0
Term.Term()	0.0	1.0	1.0	1.0
Term.Term(int)	0.0	1.0	1.0	1.0
Term.Term(Var)	0.0	1.0	1.0	1.0
Term.toString()	3.0	2.0	2.0	4.0
Tool.afterTreat(String)	1.0	1.0	2.0	2.0
Tool.exprSimplify(ArrayList\)	7.0	2.0	4.0	5.0
Tool.mul(ArrayList\, ArrayList\)	3.0	1.0	3.0	3.0
Tool.mul(Term, Term)	0.0	1.0	1.0	1.0
Tool.preTreat(String)	2.0	1.0	5.0	5.0
Var.addAbs(Var)	2.0	2.0	1.0	3.0
Var.copy()	0.0	1.0	1.0	1.0
Var.equals(Var)	3.0	2.0	3.0	5.0
Var.getCharacter()	0.0	1.0	1.0	1.0
Var.getIndex()	0.0	1.0	1.0	1.0
Var.getNum()	1.0	1.0	2.0	2.0
Var.getSymbol()	0.0	1.0	1.0	1.0
Var.getType()	0.0	1.0	1.0	1.0
Var.setSymbol(int)	0.0	1.0	1.0	1.0
Var.similar(Var)	1.0	1.0	2.0	2.0
Var.simplify()	6.0	4.0	4.0	6.0
Var.subAbs(Var)	2.0	2.0	1.0	3.0
Var.toString()	7.0	3.0	4.0	5.0
Var.Var(int)	1.0	1.0	1.0	2.0
Var.Var(int, BigInteger, Character, int)	0.0	1.0	1.0	1.0
Var.Var(int, BigInteger, Character, int, int)	0.0	1.0	1.0	1.0
Var.Var(int, BigInteger, int, int)	0.0	1.0	1.0	1.0
Var.Var(int, Character, int, int)	0.0	1.0	1.0	1.0
Total	108.0	71.0	113.0	132.0
Average	2.076923076923077	1.3653846153846154	2.173076923076923	2.5384615384615383