BUAA_OO_HW 4 第一单元博客作业

OO 面向对象设计与构造

软件工程

Publish Date: 2023-03-17

前言

开局暴击是OO课程的传统。OO的精华在于其前两个单元。本单元作为OO的第一个单元，其重要性不言而喻，难度也不小。

笔者在第一次作业花费约40小时，第二、三次作业均花费20小时左右。个人觉得在基本架构定型之后，后面的难度递减，但是不可掉以轻心，要始终抱着谨慎的态度和热切的求知欲来完成每一次作业，这样我们的能力才能持续性提升。

基于度量的程序结构分析

作业总类图

类图十分简洁，这些类可以分为三个部分：

Main: 负责I/O处理(包括处理读入的函数)
Lexer/Parser: 递归下降解析含有函数的形式化表达式
Expr/Node/Factor: 分别构成单项式、多项式、表达式因子(较为特殊，单独提取出来，便于扩展)

具体来说：

Main: 读入函数和表达式，并且声明他们(如有需要再展开使用)
Lexer: 词法分析器，识别表达式的形式化结构
Parser: 语法分析器，逐层解析，按照表达式自身的层次(+/- * ** sin/cos selfDefFun)逐层解析对应的Expr，Term，Content，Factor，调用对应的类，储存表达式并做相应的运算
Expr 多项式，由单项式组成，含有多项式乘法、求导、toString等核心方法(其实这些方法都设置再Factor里面，本类就是一个 $\lceil$ 架子 $\rfloor$ ，但是这个架子十分必要，为了更复杂的运算和其他更新的数据结构，我们要保留这个类)
Node 单项式，包含系数(常数)、幂函数、三角函数的数据结构，以及求导运算
Factor 作为抽象的父类，其实质就是Expr类

复杂度分析

类复杂度

方法复杂度

代码行数

总的来看，代码的行数适中，复杂度不高，类与类耦合度也在可以接受的范围内，内聚性高。复杂度高的方法，如Node.toString()，Parser.parseFactor()，Parser.TrianglSimp()均需要针对不同的字符串或数据结构进行处理，使用了大量if-elif-else语句，拉高了复杂度。

hw1

架构设计体验

第一次作业做得十分艰难，有一种被暴击的感觉。我已经靠着上机实验和课堂讲授的内容建立了基本的代码框架，甚至填充了部分细节，但是在乘法的地方卡住了。乘法是因子到多项式的转化，为了实现这个功能，我并没有优化方法，而是定义了奇怪的数据结构：


private BigInteger ra;

public BigInteger getRa() {
    return ra;
}

public void setRa(BigInteger ra) {
    this.ra = ra;
}

public Map<String, BigInteger> getVars() {
    return vars;
}

public void setVars(Map<String, BigInteger> vars) {
    this.vars = vars;
}

public void setElements(HashSet<Node> elements) {
    this.elements = elements;
}

private Map<String, BigInteger> vars;
private HashSet<Node> elements;

这样虽然效果很好，但是可维护性差，一修改就出bug。细细推究，还是Node，负担太重，自己本来式单项式，却时常肩负多项式的职责，自己指向自己(HashSet<Node> elements)，深浅拷贝不分。在后面的迭代中，这样的问题将最终得到解决。

第一次作业bug

第一次作业由于本地测试较为充分，强测和互测均未被发现bug。

第一次作业发现房内一人一个bug，这位同学对于表达式位于首位的变量符号处理不当， $-x$ 的负号会被吞掉。

这次测试主要采取精准打击+评测机辅助的手段

hw2

第二次作业架构分析

第一次作业中，虽然基本的多项式(expr/factor)-单项式(node)的结构已经建立，但我在运用算法的时候遇到了麻烦，不知道该如何处理。我的问题出在如何由底层的Factor回到表达式。因为有 $\lceil 表达式因子 \rfloor$ 这个存在，导致单项式经过运算之后也有可能变成多项式，之前我尝试在node中使用Set装填node运算之后的结果，但是这样导致了结构的混乱，因为node会自己装填自己。于是在之后的作业中，我取消了单项式-多项式的继承关系，用接口统一它们相同的功能。

无论是乘法、乘方、还是求导，都可以抽象为这样一个过程：

构建单项式，组成多项式
$\lceil 运算 \rfloor$ 多项式，进而运算其中的单项式
$\lceil 运算 \rfloor$ 运算单项式，产生多项式(内含多个单项式)
返回多项式，将其中的单项式添加到被运算的多项式中

这是一个可以 $\lceil 递归 \rfloor$ 的过程。这样的重构为第三次作业的完成和优化奠定了良好的基础。

这一次作业添加了三角函数，和自定义函数。对于自定义函数我增加了SelfDefFun实现函数的解析和预处理，对于三角函数，起初我只是把它当成普通变量因子优化，但是这样就固化了函数结构，要使用内部多项式就要再次解析，效率较低。于是我把 $\sin$ 、 $\cos$ 从中单独提取出来，和普通变量因子并列，还增加了储存内部表达式因子的数据结构，这样就可以更加便利地操作三角函数内部的表达式了。这主要是考虑到后面的迭代可能使用三角函数的内部表达式。

第二次作业bug

第二次作业强测未被发现bug，互测被发现一个bug，原因是词法分析器出现了问题。


char c = str.charAt(loc);
nowSymbol = "";
while (c == '\t' || c == ' ') {
  ++loc;
  if (isFinalSym()) {
   return; //special judge
  }
  c = str.charAt(loc);

}

这里给出正确程序。出现bug的地方往往是最复杂的几个类，里面使用了大量条件语句。一旦有某个地方考虑不周，就会出现问题。

第二次作业发现房内三人三个bug，仍然是用自己的评测机，不过这次发现适当结合手搓数据可以加强数据的强度。使用数据如下：


0
+sin((-cos((x- x))-+z*-3*-7*-8*cos(0)*x)) # Wrong answer sin((1+168*x*z))

0
-cos((sin(0)**0+-(sin(x))*cos(0)*-3*cos(0))) # Wrong Answer -cos((3*sin((1*x)))) -cos((3*sin((1*x))))

这次测试以评测机测试为主，辅以手搓特殊数据池为辅，一个数据池的构造如下：

sym = ["+", "-", "*", "(", ")", "**", "sin", "cos", "dx", "dy", "dz"]
var = ["x", "y", "z", "sin((x - y - z))", "cos(0)", "cos((x- y - z * z))", "sin(0)", "(sin(x) ** 2 + cos(x) ** 2)",
       "cos((x * y * z ** 2)), ""$f$",
       "$g$", "$h$"]

很欣赏陈昊学长的这句话：山不在高，有仙则名；水不在深，有龙则灵；数不在大，爆long就行。诸如 $2^{63}$ 、 $2^{31}$ 、 $\cos(0)$ 、 $(x^2, y^2)$ 之类的数据，虽然简单，但是能游走在程序运算边界之间，可能让某系程序出现漏洞和bug，是为“恢恢乎其于游刃必有余地也”。

这次自己搭建的评测机关于自定义函数的部分还不够完善，不然可以hack得更爽。

hw3

第三次作业架构设计体验

得益于架构，只添加了100余行就实现了对应功能，此外添加了三角函数优化，但是为了防止强测互测被卡TLE，最终忍痛删除了优化，但结过防不胜防，最后互测还是被大佬通过自定义函数还是被卡了(虽然或许不是架构问题)。

主要就是在Node类和Factor类中加入了求偏导函数，核心代码如下：


// Node.java
Factor derivation(String variable) { //find out whether this is unchangeable variable
    Factor finalExpr = new Factor();
    if (vars.get(0).get(variable) != null) {
        BigInteger index = vars.get(0).get(variable);
        BigInteger newIndex = index.subtract(BigInteger.ONE);
        BigInteger newRa = ra.multiply(index);
        Node node = new Node(this);
        node.ra = newRa;
        if (newIndex.equals(BigInteger.ZERO)) {
            node.vars.get(0).remove(variable);
        } else {
            node.vars.get(0).put(variable, newIndex);
        }
        finalExpr.addElements(node); //add results
    }
    //System.out.println("Here!" + pools);
    for (int i = 1; i < Node.types; ++i)
    {
        calTriDiff(i, finalExpr, variable);
    }
    return finalExpr;
}


// Factor.java
public Factor derivation(String variable)
{
    Factor expr = new Expr();
    for (Node node : getElements())
    {
        Node tmpNode = new Node(node);
        //            System.out.println("node pool is" + node.getPools());
        Factor expr1 = tmpNode.derivation(variable);
        for (Node node1 : expr1.getElements())
        {
            expr.addElements(new Node(node1));
            //System.out.println("new node pool is" + node.getPools());
        }
    }
    return expr;
}

其实质就是多项式求导转化为单项式求导，单项式求导转化为每一个幂函数的求导，每一个幂函数的求导产生新的多项式，组合起来就得到了最终的表达式，如图所示：

第三次作业bug

第三次作业强测未被发现bug，互测被发现一个bug(来自洪陈天一大佬，但不是架构问题)

第三次作业发现房内同学的bug，甚至没有提交数据，但是房内大佬发现了指导书语焉不详之处以及评测机漏洞，用这样一组数据把房内其余所有人和评测机都打穿了 😦


3
f(x,y)=1+x+y-sin(x)-sin(y)
g(x)=dx(((f(x,cos(x)))**4)**3)
h(x,y)=(((x+y)**8)**8)**8
1

这是因为指导书中的cost没有对定义但不调用的函数做出限制，于是如果采用预解析而不是调用解析的方法，就会被卡掉。
在第二次作业时我就发现了这个问题，但我不以为意，认为这种数据存在问题，就没有提交互测(~~肠子都悔青了~~)。从中我体会到对待Bug一定要立场坚定，态度坚决(~~宁可错杀一千，也不放过一个~~)。

这次自定义函数比较完善了，也有限支持求导(不过没有限制求导层数，且时有报错)。评测机自定义函数部分代码如下：


f1 = "f(x, y, z)="
 f1_body = gen_expr(2, 0, 0)[0] # no loop
 f2 = "g(x, y, z)="
 f2_body = gen_expr(2, 0, 0)[0]
 f3 = "h(x, y, z)="
 f3_body = gen_expr(2, 0, 0)[0]
 f11 = "f(" + gen_factor(random.randint(0, 2), random.randint(0, 5), 0)[0] + "," \
       + gen_factor(random.randint(0, 2), random.randint(0, 5), 0)[0] + "," \
       + gen_factor(random.randint(0, 2), random.randint(0, 5), 0)[0] + ")"
 f21 = "g(" + gen_factor(random.randint(0, 2), random.randint(0, 5), 0)[0] + \
       "," + gen_factor(random.randint(0, 2), random.randint(0, 5), 0)[0] + \
       "," + gen_factor(random.randint(0, 2), random.randint(0, 5), 0)[0] + ")"
 f31 = "h(" + gen_factor(random.randint(0, 2), random.randint(0, 5), 0)[0] + \
       "," + gen_factor(random.randint(0, 2), random.randint(0, 5), 0)[0] + \
       "," + gen_factor(random.randint(0, 2), random.randint(0, 5), 0)[0] + ")"
 while len(f11.replace("\t", "").replace(" ", "")) > 50:
     f11 = "f(" + gen_factor(random.randint(0, 2), random.randint(0, 5), 0)[0] + \
           "," + gen_factor(random.randint(0, 2), random.randint(0, 5), 0)[0] + \
           "," + gen_factor(random.randint(0, 2), random.randint(0, 5), 0)[0] + ")"
 while len(f21.replace("\t", "").replace(" ", "")) > 50:
     f21 = "g(" + gen_factor(random.randint(0, 2), random.randint(0, 5), 0)[0] + \
           "," + gen_factor(random.randint(0, 2), random.randint(0, 5), 0)[0] + \
           "," + gen_factor(random.randint(0, 2), random.randint(0, 5), 0)[0] + ")"
 while len(f31.replace("\t", "").replace(" ", "")) > 50:
     f31 = "h(" + gen_factor(random.randint(0, 2), random.randint(0, 5), 0)[0] + \
           "," + gen_factor(random.randint(0, 2), random.randint(0, 5), 0)[0] + \
           "," + gen_factor(random.randint(0, 2), random.randint(0, 5), 0)[0] + ")"
 while len(f1_body.replace("\t", "").replace(" ", "")) > 150:
     f1_body = gen_expr(2, 0, 0)[0]
 while len(f2_body.replace("\t", "").replace(" ", "")) > 150:
     f2_body = gen_expr(2, 0, 0)[0]
 while len(f3_body.replace("\t", "").replace(" ", "")) > 150:
     f3_body = gen_expr(2, 0, 0)[0]
 poly = poly.replace('$f$', f11).replace('$g$', f21).replace('$h$', f31)

心得体会

本单元学习的心得体会是十分丰富的，大致有以下几点：

复习了 Java 基本语法和数据结构，熟练使用 ArrayList、HashMap 等数据结构优化计算速度。
学习了面向对象的基本思想、项目的架构方法和思路、提升了数据分析和抽象能力。
提升了数据对拍能力，通过搭建评测机/手搓数据来检验自己和他人的Bug，提高代码的质量和鲁棒性。

同时笔者深深体会到了面向对象开发的不易。我为自己的程序付出了心血和汗水，然而一个小小的架构问题或者 Bug 就可能让之前的努力付之东流。因此，我们在开发过程中一定要慎之又慎。但是本人的 Java 编程知识还不够丰富，我还要继续多看 Java 面向对象基本的书记，同时预习多线程的内容，避免在下个单元再次遇到困境。

2024.08.24 补充：大二下对我来说绝对是最充实、收获最多的一学期了。此后由于规划、身体等原因，我没能很好地平衡课内学习和课外竞赛，留下了一些遗憾。

Yixiang Zhang

http://zxdfcv.github.io/2023/03/17/BUAA-OO-HW-4-%E7%AC%AC%E4%B8%80%E5%8D%95%E5%85%83%E5%8D%9A%E5%AE%A2%E4%BD%9C%E4%B8%9A/

All articles in this blog are used except for special statements CC BY 4.0 reprint policy. If reproduced, please indicate source Yixiang Zhang !

OO 面向对象设计与构造

BUAA_OS_LAB 1 内核启动 printf

2023-03-20 体系结构

OS 操作系统

BUAA_OS_LAB 2 内存管理

2023-03-15 体系结构

OS 操作系统