OO_Unit1: 表达式化简
前言
本单元OO作业主题是对给定表达式化简，第一次作业要求将含有一个x变量的表达式的所有括号展开。
解析输入的符合课程组给定文法的表达式，对表达式的结构进行解析后进行化简，我使用了递归下降的方法对表达式解析。事实上关于表达式的解析和化简都是基于逐层递归的思想进行的——首先，表达式的解析是从上到下进行解析，核心是parseExpr->parseTerm->parseFac，从而建起有这三个层次的表达式树；然后再进行表达式的化简计算，这一步就是从下往上计算，计算结果可以用Ploy存储，每一步计算返回一个Poly，首先计算合并用*连接的Factor，再合并用+/-连接的Term，最终得到了Poly进行输出就可以了。
我在完成本单元三次作业时的困难程度是递减的，第一次作业由于对递归下降思想完全没有概念，光是理解并思考完架构就花了两天时间，第二次作业增加了两大模块分别是exp因子和自定义函数，再加上由于我第一次作业的架构并没有很完善需要部分重构，工作量也蛮大的；至于第三次作业只有一个求导算子，在理解递归下降的思想的基础上很快就可以做完。
下面是我对三次作业的分析和总结。
homework1
第一次作业的任务是展开一个单变量多项式，输出拆好括号并化简的表达式。
设计思路
表达式的解析
解析工作由词法分析器Lexer和解析器Parser构成。Lexer负责将表达式解析为数字/符号+-*^()/字母x等基本元素(token)，为Parser的解析工作提供了next()函数来获取每一个元素。
接下来就是parser进行解析，最终的返回的是一个Expr。
我的Expr类中包含了只储存了一个Expr和一个Term，以及连接两者的符号op，在解析时以expr -> expr + term形式建立表达式树。这里有一些细节需要注意：
- 由于计算表达式是从左往右计算的，因此不能将表达式解析为
expr ->term+ expr的形式，否则会违反运算顺序。例如在计算1-1+1时若按上述方法解析就会变成1-(1+1)。 - 但如果按照
exp -> exp + term解析，就需要在调用parseExp()函数内直接再调用parseExp()，从而陷入无限递归，解决方法是先调用parseTerm解析出Term1，将其向上转换为Expr。如果其后还有+/-，则继续调用parseTerm解析出Term2，更新要返回的Expr=Expr+Term2；如果没有+/-，即为递归边界，直接返回Expr(Term1)。
public Expr parseExpr() {
Term term1 = parseTerm();
Exp expr = new Expr(term1);//向上转化为Expr，结构为Expr->Term
while (lexer.peak().equals("+") | lexer.peak().equals("-")) {
String op = lexer.peak();
lexer.next();
Term term2 = parseTerm();
expr = new Expr(expr, term2);//expr -> expr + term
expr.setOp(op);
}
return expr;
}Term的解析思路同上，我以Term -> Factor * Term对Term进行解析。由于乘法计算无需考虑从左到右的顺序，先解析Factor是没问题的。
public Term parseTerm() {
Term term = new Term();
term.setFactor(parseFactor());
if (lexer.peak().equals("*")) {
lexer.next();
term.setTerm(parseTerm());
}
return term;
}这样解析表达式后建立的树是一个类似于二叉树的结构。
关于符号的处理，我在expr -> expr + term这一步记录了符号，此外在每种Factor都添加了sign属性。事实上后者是没有必要的，由于只有在第一个因子/项之前，可以带一个正号或者负号，而预处理时我会将积压在每个项前连续的+-号处理掉，所以得到的表达式只需在以下两个位置加入符号判断：1.Factor乘积构成的Term前判断加减 2.至于因子前的符号，根据文法只需在NumFac前判断该数字的正负。
表达式的化简
化简是在解析建好的表达式树从底层逐层向上化简。
引入Mono类，里面只有一个exponent记录x的指数。
这一步封装我做的不好，当时的我写到这一步已经是周五了，没有引入Poly。我在Expr、Term和各种Factor类中都写了simplify()方法直接返回一个HashMap<BigInteger,Mono>（也就是之后的toPoly），从Factor开始向上化简，最终在main中调用expr.simplify()即可获得最终化简好的HashMap。
UML类图
Bug分析
第一次作业我在预处理时加上了一个去除前导零的操作，事实上不仅BigInteger会自动处理前导零，而且我还把这个函数写错了，结果是数字只要有0就会被我删去一部分，纯纯的多写了个bug。这是一个比较严重的错误了，让我没想到的是强测居然只挂了一个点，真是对这个无比致命的错误来说非常的友好了orz 于是我也在第一次oo作业就获得极致的互hack乱砍体验，我用一些随机生成的数据便收获了约30%的命中率，甚至最后不知道自己在砍谁（bushi
修复bug就是把我那几行预处理删掉，至今有时想到这个错误还是不知道自己当时是怎么想的。。
homework2
第二次作业增加了：1.自定义函数 2.指数函数因子。此外要求实现多层括号嵌套化简，这一点递归下降自然可以解决。
设计思路
多项式Poly类内用ArrayList<Mono>存储各个单项式，符号直接在coe中体现。
单项式Mono的结构调整如下：
public class Mono {
private BigInteger coe; //系数
private BigInteger exponent; //指数
private Poly poly = new Poly();//exp(Poly)
}自定义函数
$$
Define: f(x_1,x_2,x_3)= Expr，将x扩展为x_1，x_2，x_3
$$
$$
Call: f(Factor_1, Factor_2, Factor_3)，此处Factor_i只包含x
$$
第二次作业在定义函数的时候保证不出现其他函数，但第三次作业可以在定义中调用之前定义过的函数。我在第二次作业中就实现了这个功能。
引入FuncFac类
public class FuncFac implements Factor {
private String newFunc;
private Expr expr;
}为了保存和解析定义的函数，新建一个Define类来存储和解析自定义函数。
public class Define {
private static HashMap<String, String> defMap = new HashMap<>();
//储存读入的函数定义，Map：函数名->函数表达式，直接存储为String
private static HashMap<String, ArrayList<String>> paraMap = new HashMap<>();
//储存每个函数的形参列表：Map：函数名->[x1,x2,x3]
public static void addFunc(String in) {
// 构造defMap
}
public static String callFunc(String name, ArrayList<Factor> actualPara){
//返回用实参代替、形参之后的函数调用形式
}
}我让lexer在处理过程中将整个函数调用f(因子,因子,...)作为一个Token，交给parser中的parseFuncFac函数解析。我们建立ArrayList<Factor> actualPara作为该函数的实参表，只要将括号内的由,隔开的各个因子解析出来放到List中就可以了。考虑到因子内可能依然含有FuncFac，我将括号里各个因子内部的,替换为不会出现的其他符号，再在分别解析因子的时候替换回来。
public Factor parseFuncFac(){
ArrayList<Factor> actualPara = new ArrayList<>();
/*
* 将因子内的','换成其他字符
*/
for (String s : str.split(",")) {
//将因子s中原本的,恢复
//新建一个parser解析各个Factor
}
//解析name=f/g/h
return new FuncFac(name, actualPara);
}至此再调用FuncFac的构造函数，解析Define中的callFunc返回的字符串，这样就得到解析好的函数的Expr了。
表达式因子
格式是exp(因子)，注意这里的因子为不带指数的表达式因子时，该表达式因子两侧必要的一层括号。为此引入ExpoFac类。parser分别解析括号内的因子和括号外的指数即可。
public class ExpoFac implements Factor {
private Factor factor;
private BigInteger exp;//^a
}作为Factor转化为Poly时，直接将指数a乘进factor。
关于合并同类项
在计算的过程中Poly类中有一个addMono的方法，我直接遍历该poly的MonoList是否含有待加入mono的同类项，也就是需要重写mono的equals方法。
$$
Mono = Coe * x^{a} * exp (Poly)
$$
$$
Poly=\sum_{}^{}Mono
$$
要想判断两个mono是否可以合并，只需要比较x的指数a以及e指数上的Poly，这两者均相等就可以合并。作为BigInteger的a直接比较即可，而Poly的相等则需要我们再写相应的equals方法。
//Mono.java
public boolean myEqual(Mono mono) {
//第一次调用Mono的equal，不需要看coe
return exponent.equals(mono.exponent) && Objects.equals(poly, mono.poly);
}那么Poly相等该如何判断呢？显然所有Mono相等时才能算是相等。这里我遇到了两个问题：
对于
Poly的比较我们实际上需要比较两个List中的元素是否完全一样，而MonoList中的Mono由于被add进来时顺序是未知的，那么这两个List该如何比较？- 我们第一次调用
mono是否相等时是不需要比较Coe的。然而在比较exp指数上的内容时需要的是mono完全相等，系数也需要加入比较。否则如果按照最开始的mono比较策略就会出现将exp(x)和exp((3*x))合并的情况。
- 我们第一次调用
为了解决以上问题，我在Poly中重写了equals方法，返回的是同时比较coe，指数a和poly的结果。
@Override
public boolean equals(Object o) {
//...
return Mono.myEqual(monos, poly.monos);
}这需要我在Mono中写的另一个静态的用于比较的方法。
public static boolean myEqual(ArrayList<Mono> m1, ArrayList<Mono> m2) {
return m1.containsAll(m2) && m2.containsAll(m1);
}这里的containsAll会调用我重写的Mono的equals比较方法。
@Override
public boolean equals(Object o) {
//...
Mono mono = (Mono) o;
return exponent.equals(mono.exponent) && this.coe.equals(mono.coe)
&& Objects.equals(poly, mono.poly);
//此后调用的都是Poly的equals方法，需要比较系数
}这里还有两个细节要注意：
1.在比较Poly之前还需要removeZero()操作，以除去coe为0的项。
2.关于深克隆：需要在addMono这个函数中深克隆。如果不进行深克隆，会出现把Mono直接放到poly相乘的结果中，之后setCoe的时候会由于指针指向同一个Mono而导致本来想修改的是答案Poly的系数，但顺便也把原先作为乘数Poly中的Mono也改了。我和这个问题从早上决斗到下午才改好。
结合这样一个例子就可以说明：(exp(x)+1)^2。
//Poly.java
public void addMono(Mono mono) throws CloneNotSupportedException {
//计算Poly+Mono
Mono monoClone = (Mono) mono.myClone();
if(可以合并同类项){
m.setCoe(m.getCoe().add(mono.getCoe()));
return;
}
this.monos.add(monoClone);
}结果输出
我在Mono和Poly类中分别写了toString方法用于输出。
需要注意的是在toString的规范：只进行转换为字符串的操作。不要在toString里做一些改变对象内容的事请。如果在该函数中改变了对象中的内容可能会导致调试的时候结果正确而最后输出错误的情况。调试的时候对于对象会自动调用toString函数，如果没有写toString就会输出@(toHex)HashCode。
UML类图
homework3
设计思路
第三次作业增加了求导因子。第三次作业在我们之前的递归下降架构上很快就能写好。为此我加入DiffFac类。
public class DiffFac implements Factor {
private Expr expr;
}先把每个因子的toDiff()写了，全部返回Poly。至于求导因子的嵌套需要如下处理。
@Override
public Poly toDiffPoly() throws CloneNotSupportedException {
return expr.toDiffPoly().toDiffPoly();
}所以还要对Mono和Poly的求导，求导的过程也很直观。这里只要注意一下指数为0的时候返回0就可以了。
$$
Mono’ = (Coe*a) * x^{a-1} * exp (Poly)+Coe*x^{a}*exp(Poly)*Poly’
$$
$$
Poly’=\sum_{}^{}mono’
$$
UML类图
Bug分析
所幸后两次作业强测没有出现Bug，后两次发现的别人的Bug有：无法处理类似于f((x)^2)后面的指数，还有指数没改为BigInteger的，但由于cost我无法hack，以及一些tle。
复杂度分析
| method | CogC | ev(G) | iv(G) | v(G) |
|---|---|---|---|---|
| Change.dealComa(String) | 19.0 | 1.0 | 6.0 | 10.0 |
| Define.callFunc(String, ArrayList) | 18.0 | 3.0 | 7.0 | 13.0 |
| Lexer.next() | 8.0 | 2.0 | 6.0 | 9.0 |
| Poly.isSimple() | 8.0 | 4.0 | 6.0 | 6.0 |
| Mono.toString() | 7.0 | 2.0 | 4.0 | 6.0 |
| Parser.parseFactor() | 7.0 | 6.0 | 8.0 | 8.0 |
| Lexer.getFunc() | 6.0 | 1.0 | 3.0 | 5.0 |
| Parser.parseExpr() | 6.0 | 1.0 | 4.0 | 5.0 |
| Term.toDiffPoly() | 6.0 | 1.0 | 4.0 | 4.0 |
| Define.addFunc(String) | 4.0 | 1.0 | 3.0 | 5.0 |
| Poly.addPoly(Poly, int) | 4.0 | 1.0 | 3.0 | 3.0 |
| Mono.equals(Object) | 3.0 | 3.0 | 3.0 | 5.0 |
| Parser.parseNumFac() | 3.0 | 1.0 | 3.0 | 3.0 |
| Poly.addMono(Mono) | 3.0 | 3.0 | 3.0 | 3.0 |
| Poly.changeOrder() | 3.0 | 3.0 | 3.0 | 3.0 |
| Poly.mulPoly(Poly, Poly) | 3.0 | 1.0 | 3.0 | 3.0 |
| Poly.removeZero() | 3.0 | 1.0 | 3.0 | 3.0 |
| Poly.toString() | 3.0 | 2.0 | 3.0 | 4.0 |
| ExprFac.toDiffPoly() | 2.0 | 2.0 | 2.0 | 2.0 |
| Lexer.getNumber() | 2.0 | 1.0 | 3.0 | 3.0 |
| Mono.toDiffPoly() | 2.0 | 1.0 | 2.0 | 2.0 |
| Poly.addPolyNew(Poly, Poly) | 2.0 | 1.0 | 3.0 | 3.0 |
| Poly.equals(Object) | 2.0 | 3.0 | 1.0 | 3.0 |
| Poly.powPoly(Poly, BigInteger) | 2.0 | 2.0 | 3.0 | 3.0 |
| Term.toPoly() | 2.0 | 2.0 | 2.0 | 3.0 |
| VarFac.toDiffPoly() | 2.0 | 1.0 | 2.0 | 2.0 |
| ExpoFac.toPoly() | 1.0 | 2.0 | 2.0 | 2.0 |
| Expr.toDiffPoly() | 1.0 | 1.0 | 2.0 | 2.0 |
| Expr.toPoly() | 1.0 | 1.0 | 2.0 | 2.0 |
| Main.main(String[]) | 1.0 | 1.0 | 2.0 | 2.0 |
| Mono.isOnlyE() | 1.0 | 1.0 | 2.0 | 2.0 |
| Mono.isOnlyX() | 1.0 | 1.0 | 2.0 | 2.0 |
| Mono.myEqual(ArrayList, ArrayList) | 1.0 | 1.0 | 2.0 | 2.0 |
| Mono.myEqual(Mono) | 1.0 | 1.0 | 2.0 | 2.0 |
| Parser.parseExponent() | 1.0 | 1.0 | 2.0 | 2.0 |
| Parser.parseFuncFac() | 1.0 | 1.0 | 2.0 | 2.0 |
| Parser.parseTerm(int) | 1.0 | 1.0 | 2.0 | 2.0 |
| Poly.myClone() | 1.0 | 1.0 | 2.0 | 2.0 |
| Poly.toDiffPoly() | 1.0 | 1.0 | 2.0 | 2.0 |
| Change.process(String) | 0.0 | 1.0 | 1.0 | 1.0 |
| DiffFac.DiffFac(Expr) | 0.0 | 1.0 | 1.0 | 1.0 |
| DiffFac.toDiffPoly() | 0.0 | 1.0 | 1.0 | 1.0 |
| DiffFac.toPoly() | 0.0 | 1.0 | 1.0 | 1.0 |
| ExpoFac.ExpoFac(Factor, BigInteger) | 0.0 | 1.0 | 1.0 | 1.0 |
| ExpoFac.toDiffPoly() | 0.0 | 1.0 | 1.0 | 1.0 |
| Expr.Expr() | 0.0 | 1.0 | 1.0 | 1.0 |
| Expr.addTerm(Term) | 0.0 | 1.0 | 1.0 | 1.0 |
| ExprFac.ExprFac(Expr, BigInteger) | 0.0 | 1.0 | 1.0 | 1.0 |
| ExprFac.toPoly() | 0.0 | 1.0 | 1.0 | 1.0 |
| FuncFac.FuncFac(String, ArrayList) | 0.0 | 1.0 | 1.0 | 1.0 |
| FuncFac.toDiffPoly() | 0.0 | 1.0 | 1.0 | 1.0 |
| FuncFac.toPoly() | 0.0 | 1.0 | 1.0 | 1.0 |
| Lexer.Lexer(String) | 0.0 | 1.0 | 1.0 | 1.0 |
| Lexer.peak() | 0.0 | 1.0 | 1.0 | 1.0 |
| Mono.Mono(BigInteger, BigInteger) | 0.0 | 1.0 | 1.0 | 1.0 |
| Mono.Mono(BigInteger, BigInteger, Poly) | 0.0 | 1.0 | 1.0 | 1.0 |
| Mono.Mono(Poly) | 0.0 | 1.0 | 1.0 | 1.0 |
| Mono.getCoe() | 0.0 | 1.0 | 1.0 | 1.0 |
| Mono.getExponent() | 0.0 | 1.0 | 1.0 | 1.0 |
| Mono.getPoly() | 0.0 | 1.0 | 1.0 | 1.0 |
| Mono.mulMono(Mono, Mono) | 0.0 | 1.0 | 1.0 | 1.0 |
| Mono.myClone() | 0.0 | 1.0 | 1.0 | 1.0 |
| Mono.setCoe(BigInteger) | 0.0 | 1.0 | 1.0 | 1.0 |
| Mono.setExponent(BigInteger) | 0.0 | 1.0 | 1.0 | 1.0 |
| NumFac.NumFac(BigInteger) | 0.0 | 1.0 | 1.0 | 1.0 |
| NumFac.toDiffPoly() | 0.0 | 1.0 | 1.0 | 1.0 |
| NumFac.toPoly() | 0.0 | 1.0 | 1.0 | 1.0 |
| Parser.Parser(Lexer) | 0.0 | 1.0 | 1.0 | 1.0 |
| Parser.parseDiffFac() | 0.0 | 1.0 | 1.0 | 1.0 |
| Parser.parseExpoFac() | 0.0 | 1.0 | 1.0 | 1.0 |
| Parser.parseExprFac() | 0.0 | 1.0 | 1.0 | 1.0 |
| Parser.parseVarFac() | 0.0 | 1.0 | 1.0 | 1.0 |
| Poly.Poly() | 0.0 | 1.0 | 1.0 | 1.0 |
| Term.Term() | 0.0 | 1.0 | 1.0 | 1.0 |
| Term.addFactor(Factor) | 0.0 | 1.0 | 1.0 | 1.0 |
| Term.getSign() | 0.0 | 1.0 | 1.0 | 1.0 |
| Term.setSign(int) | 0.0 | 1.0 | 1.0 | 1.0 |
| VarFac.VarFac(BigInteger) | 0.0 | 1.0 | 1.0 | 1.0 |
| VarFac.toPoly() | 0.0 | 1.0 | 1.0 | 1.0 |
| Total | 143.0 | 104.0 | 159.0 | 185.0 |
| Average | 1.810 | 1.316 | 2.013 | 2.342 |
我在处理函数逗号的dealComa方法中引入了较为复杂的循环分支以支持处理嵌套函数，其实这里的嵌套交给parser也可以完成。还有就是Define中callFunc中我分别判断是x/y/z使得复杂度较高。我在Mono的toString中做了一些简化，同样需要各种判断。但除了Lexer和ParseFactor需要解析各种Token和因子，if-else难免较多之外，前面提到的还是可以进一步优化解耦使得框架更为清晰。
总结与心得
在优化方面我则基本没做，每次做完作业就都剩下
TODO，甚至将正项提前这一基本的优化我也是第二次才做。本单元第一次作业由于我封装的不够彻底，直到第二次作业才开始引入
Poly类。好在思路还是统一的，并没有进行大规模的修改。
本单元的递归下降方法要求我们写代码时头脑非常清晰，需要明确每一层递归到底发生了什么。我对面向对象思维的理解也更为深刻，在思考架构的时候尽量降低代码间的耦合度。此外我在判断对象相等时所用的equals和HashCode相关知识有了更进一步的了解，其中有很多更深刻的知识有待学习，总而言之还是很有收获的一次作业。
