前言

第一单元的主题是表达式括号展开化简，初步体会面向对象的思想，学习使用类管理数据，分工协作的行为设计等。该单元一共有三次作业层层递进，逐步实现括号嵌套，自定义函数，三角函数和求导等功能。

第一次作业

第一次作业为多变量表达式括号展开，运算分为加、减、乘和乘方四种，括号深度至多为一层，UML类图如下图所示

image-20230318195545580

架构

通过形式化表达可知表达式遵循expr->term->factor的结构，通过递归下降算法可以将这些部分给解析出来，和正则表达式相比支持迭代。

不难发现 expr=∑coe∗xexpX∗yexpY∗zexpZexpr = \sum coe*x^{expX}*y^{expY}*z^{expZ},其实无论是factor或者term都可以表示成上述式子，于是为了可以将其统一成Operator类进行计算。同时为了便于同类项的合并，将 xexpX∗yexpY∗zexpZx^{expX}*y^{expY}*z^{expZ} 封装成Unit类，Operator采用HashMap进行储存，其中key为Unit，value为coe。

本次作业的因子Pow和Number都继承Operator类，Parse类中方法的返回值都为Operator，于是对于Operator来说只需要实现加法和乘法即可，同类项合并以及括号展开都是在这个过程中实现的。

复杂度分析

本次作业部分方法复杂度如下，其余方法复杂度较低

  • CogC:认知复杂度，代码被阅读和理解的复杂程度
  • ev(G):衡量程序非结构化程度
  • iv(G):衡量模块判定结构即模块和其他模块的调用关系，模块设计复杂度高意味着模块耦合度高
  • v(G):衡量模块判定结构复杂度，数量上表现为独立路径的条数(与循环以及条件语句有关)，圈复杂度大会导致难以测试和维护

image-20230316201823884

总的复杂度不算太高，对于Operator的toString方法因为需要选出一个正项先输出，就导致需要额外一次对HashMap的遍历，其实也不是很有必要。

Bug分析

中测出现以下错误

  • 解析数字因子的时候忘记还有符号了
  • 在解析指数之后没有进行lexer.next()的操作
  • isConstant方法将其中的 expZexpZ 写成 expXexpX 了，导致会将 zyz^y 判断为不含未知数

强测和互测没有出现bug

tips

  • HashMap以类作为键值通常判断相等是基于两个类的地址来说，也就是是否是同一个实例，所以想要通过内部元素判断相等就得重写hashcode和equal函数，判断过程为如果hashcode不等为不等，否则通过equal函数判断，所以hashcode作为基础判断只需要保证构造的函数使得相等对象hashcode相同即可，想要简单的话也可以返回统一值跳过这一判断。
  • 预处理将空白符去掉，**变成^方便判断
  • 对于连续的±号并未提前处理，对于项之前的符号用sign传入parseTerm方法中，对于数字则是在parseFactor中进行处理
  • 优化：
    1. x∗∗2x**2->x∗xx*x
    2. 将正的项先输出
    3. 对于系数为±1\pm1且含有未知数因子的项不输出1

第二次作业

第二次作业支持括号嵌套，新增三角函数因子和自定义函数因子，UML类图如下图所示

image-20230318200106301

架构

对于三角函数的处理，Unit需要表示为 xexpX∗yexpY∗zexpZ∗∏(sin(expri))∏(cos(expri))x^{expX}*y^{expY}*z^{expZ}*\prod(sin(expr_i))\prod(cos(expr_i)) ，为了便于输出与合并同样采用HashMap储存三角函数，key值为expr即Operator类，value值为该三角函数的指数部分，新增继承Operator的Sin和Cos类进行构造。

1
2
3
//Unit.java
private final HashMap<Operator, Integer> sinMap;
private final HashMap<Operator, Integer> cosMap;

对于自定义函数的处理，新增Definer类处理自定义函数的定义和调用，所有成员以及方法都是静态的，直接采用类名调用。

1
2
3
4
5
6
7
//Definer.java
private static final HashMap<String,String> funcMap = new HashMap<>();
private static final HashMap<String, ArrayList<String>> paraMap = new HashMap<>();
private static final String funcPattern = "(?<funcName>[fgh])\\((?<para>.*)\\)=(?<expr>.*)";
private static final String paraPattern = "(?<para>[xyz]),?";
public static void addFunc(String input) {}
public static String callFunc(String funcName,ArrayList<Operator> actualPara) {}

addFunc内部采用正则表达式分割自定义函数各部分。callFunc调用的时候传入的实参是Operator类的，也可以调用它的toString方法传入String类型的数组,具体过程是按字符遍历函数定义式，如果是参数就用对应位置的实参替换(不是在原String替换，而是新建一个StringBuilder)。

同时新增Function类储存调用之后得到的表达式，同时可以将此表达式解析成Operator类。

1
2
3
//Function.java
private final String expr;
public Operator expandExpr() {}

在Parse中新增parseFunction方法，内部使用parseFactor读取实参列表，接着使用callFunc得到新的表达式，再返回expandExpr即可。

这次调整了一下Parse内部解析因子的方法，将对数字、未知数、三角函数和指数等的解析用方法封装了起来，指数的处理在需要的方法内进行，使得未知数以及三角函数的指数不用通过乘法实现而是直接赋值，总体来说可读性和可维护性提高了。

复杂度分析

image-20230317103249850

部分方法复杂度如上，Unit中的equals复杂度高是因为采用涉及两个HashMap的相等判断，先用if判断了size其次使用for循环判断元素是否存在映射，主要是sin和cos虽然结构类似但是由于采用两个容器储存，导致不能进行统一处理，结果出现了很多的重复性工作，这一缺点在输出等地方均存在。Operator的equals也是由于HashMap的相等判断。

Bug分析

中测

  • 就像上面说的一样，因为Cos和Sin很多类似的操作，所以复制代码结果导致一些地方没有修改到（复制是坏文明
  • cos(0)=0cos(0)=0

强测和互测

  • sin(0)0=0sin(0)^0=0
  • 比较表达式相等的时候忘记比较系数了，导致sin(x)+sin(2x)=2sin(x)sin(x)+sin(2x)=2sin(x)

互测过程中有一个同学没有处理自定义函数中的空白字符(帮我挽回了一点分数

tips

  • 对于函数实参的代入不能直接replaceAll，不然可能将已替换实参中的未知数替换掉，研讨课某些同学提出将xyz换成pqr等没出现的字符(可行不过没有可拓展性)，还有使用java中的MessageFormat类替换的。
  • 传入实参需要在左右两侧加括号。

第三次作业

第三次作业新增求导因子，函数定义时可以调用已有函数，函数定义中的求导因子先求导再代入实参,UML类图如下

image-20230318204703578

架构

这次主要就是在Operator和Unit分别加入求导的方法,通过乘法法则和链式法则等返回新的表达式,需要注意的是Unit采用乘法法则需要深拷贝。

其次函数在定义的时候先进行解析操作去掉求导因子，于是将解析字符串的操作封装在Definer方法中(Function显得更没必要了)

1
2
3
4
5
public static Operator simplifyExpr(String expr) throws CloneNotSupportedException {
    Lexer lexer = new Lexer(expr);
    Parser parser = new Parser(lexer);
    return parser.parseExpr();
}

复杂度分析

image-20230317112423675

部分方法复杂度如上，自己比较习惯将一些模块化的部分封装成方法进行调用，所以复杂度看上去还好，不然的话某些方法会很臃肿复杂度可能也会很高，不过也会导致方法很多的问题。

tips

  • 第二次作业中sin输出内部因子无脑加了层括号，在这一次判断了是否是单因子，减少括号输出，主要有数字，幂函数，三角函数这三种情况，不过由于 x2x^2 会输出为x∗xx*x，所以需要特判一下。

Bug分析

中测

  • 主要bug就出在上面所说的优化判断，细节没有考虑好

强测和互测没有bug。

反思与体会

  • 还是比较面向过程，主打的就是everything is Operator，没有将各模块解耦合，都集中在Operator和Unit两个部分，理想的架构应该是先解析出式子，再实现括号展开以及化简，用老师的话来说就是可以将每部分的工作交给不同的程序员来做。
  • Number等单因子虽然继承了Operator但是实际上没有什么自己的feature，只是为了方便构造或者理解，有些鸡肋。
  • Unit中指数的部分是用三个数分别储存的，对于后面可能的迭代开发并不是很有利，而且在某些方法中需要进行一个一个判断，应该使用HashMap储存会更加合理。
  • 作业中对三角函数做过多的优化，只是在构造的时候对sin(0)和cos(0)进行了简单的判断，不过也多亏了是边构造边化简的形式，当然也是架构的问题导致过程中不太能做更多的三角优化，除非最后再进行一次化简。
  • 三角函数没做统一处理，导致很多重复性的工作，后面再出现其余的三角函数的话，就需要继续同样的操作，应该合并成一个类在里面存有三角函数名。
  • 这次就只有没测试的第二次作业出问题了(虽然第一次和第三次都是用的大佬的评测机),深深体会到了评测的必要性。
  • OO的讨论区有很多大佬分享自己的架构经验以及评测等等，没有思路的时候可以多看看。