北航oo面向对象设计与构造第一单元总结

作者: 一一

发表于2026-03-30

更新于2026-03-30

总字数: 7.5k字

阅读时长: 25分钟

计算机 oo

oo 北航大二

写在前面：

好快好快好快就到博客周了！第一单元的历程可谓是跌宕起伏、曲折多变、动荡不安……

废话可能比较多，蓝色框的就是废话）比如这一条。

之前总是在想，写完一次作业就写一次博客，但是懒惰之下没有完成这个任务。最后发现，其实也有好处，下一次迭代过程中有可能对上一次作业又有了不一样的理解，完全把每次作业单独分隔开并不合理。

所以，这也是有好处也有坏处的事情！这一个月oo给我的感觉就是，全都是有好处也有坏处的事情！

第一单元表达式展开

第一次作业

本次作业需要完成的任务为：读入一个包含加、减、乘、乘方以及括号（其中括号的深度至多为 3 层）的单变量表达式，输出恒等变形展开所有括号后的表达式。

代码架构

第一次代码构造的时候，阅读往届博客，发现了可以不建立 AST 树状结构，直接转换为多项式线性结构的架构，会减少一次递归下降，遂采用。经过三次作业，回过头看，这个选择也是一个有好处也有坏处的事情！坏处在，初步建立的时候，理解就带来了很多bug，后续迭代的时候也会出现一些速度低于室友的 AST 的情况，而且因为和大部分同学不一样出bug了有用的意见会较少；好处在于，其实每次迭代更改增加的代码比较少，并且在大多数情况下速度还是不错的。

接下来我将通过表达式的处理流程，展开说一下我的代码架构：

预处理

为了简化后续的处理步骤，我在代码输入以后，就进行了预处理，主要包含三个部分：

去掉所有多余的空格

这个比较简单，替换即可

1
2
3

private void delBlank() {
	this.input = this.input.replaceAll("[\\x09\\x20]","");
}

处理多余重复的加减号

这里有个理解问题，重复的加减到底是如何出现的？

我们看向会增加加减的几个表述：

表达式 →→ 空白项 [加减空白项] 项空白项 | 表达式加减空白项项空白项
项 →→ [加减空白项] 因子 | 项空白项 ‘*’ 空白项因子
因子 →→ 变量因子 | 常数因子 | 表达式因子
常数因子 →→ 带符号的整数
带符号的整数 →→ [加减] 允许前导零的整数

我们根据这个理解可以分析，有几种情况：

表达式内的一个数字，允许前面有0~3个符号，分别是：整数带的符号、项前的符号、表达式开头或中间加减加的括号（此外在表达式最开始可以没有加减号）
表达式内的其他因子（包括表达式因子），前面允许有0~2，分别是：项前的符号、表达式开头或中间加减加的括号（此外在表达式最开始可以没有加减号）

所以，数据生成器生成+-+-+1完全不合法

根据上述说法，于是可以设置一个循环进行替换，直到再也没有多个加减号相连接的情况

do {
	prev = this.input;
	this.input = this.input.replace("+-","-");
	this.input = this.input.replace("-+","-");
	this.input = this.input.replace("--","+");
	this.input = this.input.replace("++","+");
} while (!this.input.equals(prev));

处理一下非项之间连接用于计算的加减符号

我一开始的想法是，把(后、表达式开头、^后、*后的加减都进行处理，加号直接消除掉，减号变成 0- 的形式，但是，有没有什么问题？有的。1*-x 经过预处理之后，就变成了1*0-x，这很坏！所以我把减号进行了保留，直接到因子的 parse 时进行处理。

this.input = this.input.replace("(+","(");
this.input = this.input.replaceAll("^\\+", "");//这里的^是开头的意思
this.input = this.input.replace("*+","*");//去掉*后的+
this.input = this.input.replaceAll("\\^\\+", "^");//去掉^后的+

预处理也是有好处也有坏处的事情！和室友紧张了半天如果后续迭代出现检验输入不合法的要求应该怎么办，幸好幸好~

表达式解析

目前没有见到有用正则表达式算法进行解析的，迭代性比较差，我也采用的是递归下降算法。通过一次递归下降算法，直接生成多项式。

lexer 部分

和课题组给的代码几乎没有什么区别，解析表达式，用peek()方法传递给 parser。

public class Lexer {
    private final String input;
    private int pos = 0;
    private String curToken;
    private TokenType tokenType;

    public Lexer(String input) {
        this.input = input;
        this.next();
    }

    private String getNumber() {
        ...
    }

    public void next() {
        if (pos == input.length()) {
            return;
        }
        char c = input.charAt(pos);
        if (Character.isDigit(c)) {
            curToken = getNumber();
            tokenType = TokenType.NUM;
        } else {
            ...
            }
            pos += 1;
            curToken = String.valueOf(c);
        }
    }

    public String peek() {
        return this.curToken;
    }

    public TokenType getTokenType() {
        return this.tokenType;
    }
}

稍微有以下不同：

getNumber方法，可以忽略前零的影响，因为后续转化为 BigInteger 时，前零的影响会自动消除。

加入了public enum TokenType {}，

public enum TokenType {
    NUM,
    X,
    MULTI, //*
    MINUS, //-
    EXP, //^
    PLUS, //+
    LP, //(
    RP //)
}

其实一开始并没有搞懂这个有什么用。后面发现，在 parser 中调用的时候可以利用其变成简短的 switch-case 形式，非常优雅。但是实际上确实是可有可无的

switch (lexer.getTokenType()) {
	case LP ://处理表达式因子
            ...
	case X ://处理指数因子
            ....
	default://处理数字因子
            ...
}

parser 部分

我觉得直接一口气变成多项式，不写AST，最最最困难的就是这部分o(╥﹏╥)o

没有AST，可以没有expr和term类，但是人心中要有o(╥﹏╥)o

Parser类的设计仍然沿用了本单元练习题中的写法，将表达式的解析分成了三部分——parseExpr(), parseTerm(), parseFactor()，我返回值的类型都是多项式 poly

parseExpr(), parseTerm()类

这两个类逻辑差不多，以expr为例，首先，先调用下一层的 parseTerm()，返回一个代表项的poly，若下一个字符是加减的计算，则进入 while 循环再次调用下一层的 parseTerm()，返回另一个代表项的 poly，调用 poly的方法进行项的加减计算获得计算后新的代表表达式的poly，如此反复，直到下一个字符不是加减为止。
1
2
3
4
5
6
7
8
9
10
public Poly parseTerm() {
Poly poly = parseFactor();

while (lexer.peek().equals("*")) {
lexer.next();
Poly poly1 = parseFactor();
poly = poly.mulPoly(poly1);
}
return poly;
}
parseFactor()类

首先！处理负号！记录下来负号，然后在最后调用poly的方法进行取相反数。

当时评测机搭建好，一直报错，就是因为这里忘记处理负号了，一直空指针o(╥﹏╥)o

然后根据输入，分别选择调用表达式因子、数字因子、幂函数因子的parser，在各因子中再调用各自的toPloy函数

数字因子直接存成 x 指数为0的单项式，幂函数因子直接存成系数为1的单项式。

表达式计算

我们可以把所有因子都表示成

最终表达式即可以表示成一个装因子的容器，我在这里使用了HashMap，多项式类我写的是Poly ，单项式类我写的是Unit。

unit

简单的先说！这类里面主要进行单项式的计算，加减乘以及系数变相反数，同时进行单项式的toString。为了防止不必要的问题发生，我将unit设置成了不可变对象。这也是有好处也有坏处的事情！好处在于，每次计算返回一个新的unit，不觉中解决了一些浅拷贝的问题，避免了一些bug；坏处在于，会用很多很多空间。

最近才了解到，原来不是对象变成野指针之后，内存就立刻释放了，还会存在一段时间。

public class Unit {
    private BigInteger number;
    private Integer expX;

    public Unit(BigInteger number, Integer expX) {
        this.number = number;
        this.expX = expX;
    }

    @Override
    public String toString() {
        //转换成字符串...
    }

    public int sign() {
        //告知符号...
    }

    public Unit mulUnit(Unit u) {
        //乘法
    }

    public Unit addUnit(Unit u) {
        //加法
    }

    public Unit negate() {
        //相反数
    }
}

Poly

在单项式已经建立好计算方法的基础上，完成多项式的计算和转换成字符串是相对轻松的事情。我依旧使poly是不可变对象。

在接下来的迭代中，此类把我折磨得要死不活，趁现在先看一下其还有逻辑的时候，后面一堆垃圾看到就有种无力感o(╥﹏╥)o

public class Poly {
    private HashMap<String, Unit> unitMap;

    public Poly() {
        this.unitMap = new HashMap<>();
    }

    public void addUnit(Unit unit) {
        //加入单项式
    }

    public String toString() {
        //转换成字符串
    }

    public Poly addPoly(Poly p) {
        //加法
    }

    public Poly subPoly(Poly p) {
        //减法
    }

    public Poly mulPoly(Poly p) {
        //乘法
    }

    public void negate() {
        //每一个项都变成相反数
    }

    public Poly expPoly(Integer n) {
        //次方
    }
}

看着很简单，但是确实是一个有好处也有坏处的类！理由如下：

可能可以注意到我的poly与大部分的不同：HashMap<String, Unit>，我用了String去做key！（String表示的是部分）

这是一个第一次作业感受不出来的，有好处也有坏处的事情！！对于第一次作业没有什么影响，但是后续迭代，，，o(╥﹏╥)o，放后面说吧，目前看起来只有算的过程中的所有过程量都生成了一遍字符串这个坏处，由于第一次作业的简单性也不会出现超时。
本人始终坚信，java 是一个方法齐全的语言，需要自己写的还是很少的，所以在写多项式的加法时，我去查了AI，AI告诉我map有提供merge方法，可以直接帮助完成加法，简单好用。
对于求多项式的幂，第一反应最快是快速幂。然而快速幂也是一个有好处也有坏处的事情。快速幂计算过程中会实例化大量的单项式，这反而会造成快速幂不快，对于后续迭代可能有超时风险

化简技巧：

如果单项式系数是0，输出0
如果单项式系数是1，省略系数
如果单项式系数是-1，输出-
如果单项式 x 的指数是0，省略 x 相关输出
如果单项式 x 的指数是1，输出 x 即可，不需要输出幂函数
加法优先输出会比减法先输出少一个符号

bug 分析

非常和平的一次，互测既没有人刀我，也没有刀到别人。

感觉比较容易出错的就是，当最后字符串是空的时候，要特判一个输出 0 。

第二次作业

本次作业需要完成的任务为：读入一个自定义函数的定义以及一个包含幂函数、指数函数、自定义函数调用和新增的选择式因子的表达式，输出恒等变形展开所有括号后的表达式。

在第一次作业基础上，本次迭代作业增加了以下几点：

本次作业支持嵌套多层括号。
新增指数函数因子 exp，其参数可以是任意因子。
新增选择式因子，一种形如 [(A==B)?C:D] 的三目运算结构，要求程序具备判定因子 A 与 B 数学恒等性的能力。
新增自定义函数，支持 f(x) = 表达式 形式的函数定义与调用。

指数函数、自定义函数、选择式因子，刀刀致命 o(╥﹏╥)o

我的强测，我的强测 o(╥﹏╥)o

代码架构

以下主要说明一下，和第一次作业不同的地方

预处理

要增加对=后、?后以及:后的加号进行处理
新增对自定义函数的定义的处理

为了方便后续迭代，我准备了一个函数库，函数库中有两个HashMap，分别是HashMap<String, String> initMap 和 HashMap<String, Poly> funcMap。一个以字符串形式存放最初读入的函数，另一个以多项式形式存放解析后的函数

由于函数中不会出现选择因子，不会出现f(x)=[(x==1)?1:0]，f(1)=1的情况。所以函数可以优先先解析，提高速度，防止TLE

函数第一次读入时，并不解析，直接存入 initMap 中，防止出现复杂函数但是表达式未调用导致 TLE 的情况。表达式第一次调用时进行解析，解析后存入 funcMap 中，后续调用直接使用多项式即可。

对于函数的调用，一定要使用深克隆，不可以使用浅克隆把函数库里的函数改了

表达式解析

lexer

新增对 exp、==、f、?、:、[、] 的解析

对于函数，为方便后续处理，函数参数作为一个token整体

//public class Lexer	
	private String getParameter() {
        StringBuilder sb = new StringBuilder();
        int num = 0;
        do {
            sb.append(input.charAt(pos));
            if (input.charAt(pos) == '(' || input.charAt(pos) == '[') {
                num++;
            }
            else if (input.charAt(pos) == ')' || input.charAt(pos) == ']') {
                num--;
            }
            ++pos;
        } while (pos < input.length() && num != 0);
        return sb.toString();
    }

同样，为了方便后续处理，将选择表达式 [(A==B)?C:D] 的C、D因子也作为一个整体的 token

//public class Lexer
	private String getC() {
        StringBuilder sb = new StringBuilder();
        int num = 0;
        while (pos < input.length() && !(input.charAt(pos) == ':' && num == 0)) {
            sb.append(input.charAt(pos));
            if (input.charAt(pos) == '(' || input.charAt(pos) == '[') {
                num++;
            }
            else if (input.charAt(pos) == ')' || input.charAt(pos) == ']') {
                num--;
            }
            ++pos;
        }
        return sb.toString();
    }

    private String getD() {
        StringBuilder sb = new StringBuilder();
        int num = 0;
        while (pos < input.length() && !(input.charAt(pos) == ']' && num == 0)) {
            sb.append(input.charAt(pos));
            if (input.charAt(pos) == '(' || input.charAt(pos) == '[') {
                num++;
            }
            else if (input.charAt(pos) == ')' || input.charAt(pos) == ']') {
                num--;
            }
            ++pos;
        }
        return sb.toString();
    }

Parser

新增parseFuncFactor()、parseExpFactor()、parseChoiceFactor

parseFuncFactor()

调用 func 的 toPoly方法：

func 的 toPoly 方法中，先将函数的参数解析为多项式 poly ，然后深克隆函数定义，调用 poly 的替换方法，将函数中的 x 替换为参数解析成的多项式。替换主要是 poly 调用单项式的替换方法。单项式的替换中，保留系数；调用 poly 的次方计算方法，计算参数解析成的多项式的 x_power 次方；调用 poly 的替换方法，替换exp中的 x 。
parseExpFactor()

调用parseFactor() 获得 exp括号中的表达式，然后存成一个系数为1，x 指数为0的单项式
parseChoiceFactor

[(<因子A> == <因子B>) ? <因子C> : <因子D>]，先将因子A，因子B调用parseFactor()变成 poly 形式，然后调用 poly 的比较数字相等的方法，得知其是否相等。再选择C和D中要用到的那一个进行解析，转换成poly

千万不可以无论比较结果如何先将因子C和D进行解析！！会TLE

表达式计算

我们可以把所有因子都表示成 $多项式$

新增内容如下：

unit增加表达 exp(多项式) 部分

1
2
3

private final BigInteger number;
private final BigInteger power;
private final Poly exp;

注意这里power是BigInteger！！

对所有的第一次作业写好的加、减、乘、取相反数计算都增加exp计算的部分。

新增对 exp 的优化，主要分为三个部分：

当 $多项式$ 中多项式是一个非表达式因子的因子时，可以少输出一个括号。

我采取的方法是加入方法 poly 和 unit 中 isSingle() 判断此时exp括号中是不是因子

//Poly
	public Boolean isSingle() {
        this.removeZero();
        if (this.unitMap.isEmpty()) {
            return true;
        }
        else if (this.unitMap.size() != 1) {
            return false;
        }
        else {
            for (Unit value : unitMap.values()) {
                if (value.isSingle()) {
                    return value.isSingle();
                }
            }
            return false;
        }
    }
//Unit
	public Boolean isSingle() {
        if (power.equals(BigInteger.ZERO) && exp.isEmpty()) { //x^0//exp(0)//常数因子
            return true;
        }
        if (number.equals(BigInteger.ONE) && exp.isEmpty()) { //幂函数
            return true;
        }
        if (number.equals(BigInteger.ONE) && power.equals(BigInteger.ZERO)) { //指数函数
            return true;
        }
        else {
            return false;
        }
    }

$多项式$ 也是合法格式，所以可以提取组成多项式所有单项式的系数的公约数，改变形式，比较长度获得最短值

以下是一些具体的例子，帮助理解，点击展开

exp((2*x))

exp(x)^2
exp(2)

exp(1)^2
exp((3600*x+5400))

exp((4*x+6))^900

exp((2*x+3))^1800

可以数学意义上证明，最短一定出现在提取出来的公约数是1、[gcd/10,gcd]中，通过这个方法，我们可以计算gcd，然后一一比较长度

//public class Poly
	public String toExpString() {
        this.removeZero();
        StringBuilder sb = new StringBuilder();
        if (this.unitMap.isEmpty()) {
            return "";
        }
        else {
            int min = Integer.MAX_VALUE;
            Gdc gcd = new Gdc(this.getNumbers());
            ArrayList<BigInteger> gdcList = gcd.getAllGdc();
            if (gdcList.isEmpty()) {
                gdcList.add(BigInteger.ONE);
            }
            for (int i = 0; i < gdcList.size(); i++) {
                StringBuilder s = new StringBuilder();
                Poly dividedPoly = this.divideNum(gdcList.get(i));
                s.append("(");
                String expString = dividedPoly.toString();
                Boolean expSingle = dividedPoly.isSingle();
                if (expSingle == true) {
                    s.append(expString);
                }
                else {
                    s.append("(");
                    s.append(expString);
                    s.append(")");
                }
                s.append(")"); //exp最短是什么
                if (!gdcList.get(i).equals(BigInteger.ONE)) {
                    s.append("^");
                    s.append(gdcList.get(i).toString());
                }
                if (s.length() <  min) {
                    min = s.length();
                    sb = s;
                }
            }
        }
        return sb.toString();
    }

//计算公约数
public class Gdc {
    private ArrayList<BigInteger> numbers;//原始数

    public Gdc(ArrayList<BigInteger> numbers) {
        this.numbers = numbers;
    }

    private BigInteger getMultiGdc() {
        if (numbers == null || numbers.isEmpty()) {
            return BigInteger.ZERO;
        }
        BigInteger result = numbers.get(0).abs();
        for (int i = 1; i < numbers.size(); i++) {
            result = result.gcd(numbers.get(i).abs());

            if (result.equals(BigInteger.ONE)) {
                return  BigInteger.ONE;
            }
        }
        return result;
    }

    public ArrayList<BigInteger> getAllGdc() {
        ArrayList<BigInteger> resList = new ArrayList<>();
        resList.add(BigInteger.ONE);
        BigInteger gdc = getMultiGdc();
        if (gdc.equals(BigInteger.ONE)) {
            return resList;
        }
        for (BigInteger i = BigInteger.ONE; i.compareTo(BigInteger.valueOf(10)) <= 0
                && i.multiply(i).compareTo(gdc) <= 0; i = i.add(BigInteger.ONE)) {
            if (gdc.remainder(i).equals(BigInteger.ZERO)) {
                BigInteger j = gdc.divide(i);
                resList.add(j);
            }
        }
        return resList;
    }

}

优化就必然带来问题！！

首先一定要控制好公约数在1、[gcd/10,gcd]中，否则遇到很大很大的数算所有的公约数直接TLE
一定要存好每次算出来的最小长度，下次直接使用，而不是从头算一遍

例如：
1
2
3
1
f(x) = exp(exp(exp(exp(exp(exp(x)^2)^2)^2)^2)^2)^2
exp(exp(exp(exp(exp(exp(exp(exp(exp(exp(exp(exp(f(f(f(f(x)))))^2)^2)^2)^2)^2)^2)^2)^2)^2)^2)^2)^2
如果没有记好之前算的最短表达式，你会计算多少次？

p.s 这里就展现出了使用 String 做 key 的优势！本身我就存有最短表达式，不需要再加属性进行存储

$多项式多项式$ 也是合法表达式，可能出现提出一个项后，前半部分可以化简为 $多项式$ ，导致式子更短的情况

以下是一些具体的例子，帮助理解，点击展开
exp((2998244367+10000000*x^6+1000000*x^8+1000000*x^3+1000000*x^5+1000000*x^4))

exp((x^6+x^8+x^3+x^5+x^4))^1000000*exp(2998244367)

这个其实目前还没有想到比较好的解决办法。我曾经问过AI，他提出了状压dp+启发式的方法，但是根据互测情况来说，这个非常容易TLE。

除此之外，还有一个很容易错误的数据点：

exp(exp((2998244367+10000000*x^6+1000000*x^8+1000000*x^3+1000000*x^5+1000000*x^4)))

不加注意，优化后就会输出：exp(exp((x^6+x^8+x^3+x^5+x^4))^1000000*exp(2998244367))

这个是错误的，正确输出应该是：exp((exp((x^6+x^8+x^3+x^5+x^4))^1000000*exp(2998244367)))

poly 中，我仍然使用了 $多项式$ 部分的字符串当做 key，即<String, Unit>。这是一个有好处有坏处的事情，这里分析一下优劣势：

优点：
1. 不用String的话大部分用了一个UnitKey类，UnitKey类里面存 x 的指数和exp的poly表达式，其存在几个问题：
  - 首先，其并非String一样的天然的不可变类，其需要自己写hashCode()和equals()方法，一不注意就错了
  - 由于计算中会更改exp的poly表达式，会出现 key 改变的情况，这样子会找不到相对应的key-value，虽然后面发现采取
    1
    for (Unit value : this.unitMap.values()) {}
    的遍历方法就不会有问题，但是debug还是好久好久
2. 如上述所示，很自然的形成了一个存最短表达式的结构，每次toString只需要“系数*key”即可
缺点：
1. 所有的计算中间形成的多项式都经过了一次toString，无疑，很容易TLE
2. 加入exp以后出现了一个问题，在hashMap中，单项式遍历顺序是随机的，toString会有 exp((x+x^2)) 和 exp((x^2+x)) 两种不同的情况，此时key不同，不会合并同类项，为了保证顺序相同，我改为了红黑树的方法，即treeMap，可能会有一定速度上的损失，但是差别可以接受。

bug 分析

强测挂了o(╥﹏╥)o

我出现的问题是在选择表达式无论选什么两边都解析成多项式，导致TLE了

其实这个提示在cost的计算中，Cost([(A==B)?C:D]) = Cost(A) + Cost(B) + choose(Cost(C), Cost(D)) + 5

认真读 cost 就会发现问题。但是o(╥﹏╥)o

exp化简上面的TLE也被互测刀了不少，过优化了，但是其实觉得这个尝试很值得

我觉得第二次会出现的 bug 主要分为两类：

错误
- 注意：exp(0)=1！！不然的话[(exp(0)==1)?1:0]会输出错误
- 函数表达式中也会出现连续加减号，也会出现空格，也要进行预处理
- x 的指数一定要是 BigInteger ！会超出 int 范围
TLE
- 选择表达式无论选什么，两边都解析成多项式，会TLE
- exp的化简非常容易TLE：
  - 架构不好的话，exp(exp(exp(exp(…exp(x)…))))就会TLE
  - 没有对已经算过的最短的exp表达式进行留存的话，exp(exp(exp(exp(…exp(x)^2…)^2)^2)^2)^2就会TLE
  - 如果优化没有给公约数设置限制的话，exp(9999999999…999999999999)就会TLE

第三次作业

本次作业需要完成的任务为：读入自定义函数的定义以及一个包含幂函数、指数函数、自定义函数调用、选择式因子和新增的求导算子的多变量表达式，输出恒等变形展开所有括号后的表达式。

在第二次作业基础上，本次迭代作业增加了以下几点：

表达式从单变量 x 扩展为双变量 x, y。
新增求导算子 dx, dy 和 grad，要求程序具备对表达式进行符号求偏导的能力，为了限制难度，求导算子不会出现在函数定义中。
新增自定义递推函数 f{n}(x)，要求程序能够处理推展开。

代码架构

第三次作业原本没有什么大改特改，但是我小小重构了，重构的内容就是把 poly 中的 key 改成 UnitKey类，所以上面可以去分析比较它们之间的优缺点。

主要说一下，求导算子和自定义递推函数的处理吧！其他的变动都不大。

自定义递推函数

我的递归函数的处理方法，继承了函数的处理方法，巧妙的运用了函数库：

递推函数就是名字不一样的函数！

函数的存取有两个 HashMap ，分别是一开始输入的 HashMap<String（函数名字）, String（函数内容）> initMap ，和后面经过 Poly 转化的 HashMap<String（函数名字）, Poly（函数内容）> funcMap。递归函数读取进来之后，我优先把函数名字 f{i} 和等号后面的函数部分进行分割，存在 HashMap<String（函数名字）, String（函数内容）> initMap。当函数被调用的时候，优先搜索 funcMap 中有没有这个函数，如果有就直接调用，如果没有寻找 initMap 中有没有，如果有，把函数后面部分进行 poly 分析，进行使用，然后存在 HashMap<String（函数名字）, Poly（函数内容）> funcMap 中，如果 initMap 中也没有，在进行递归计算，把计算后的 poly 存入funcMap 中。在后面调用的过程中，利用 poly 和 unit 中加入的替换方法，对提取的函数的 poly，用参数一一进行替换，对 poly 进行一个重塑。

求导算子

先将求导符号后面的表达式解析成 poly ，然后在 poly 和 unit 中加入求导计算。

unit 中求导计算的逻辑：（以对 x 求导为例）

系数乘上x的指数；x的指数减一；exp不变
原表达式乘上exp求导的结果
1和2形成新的poly

//Unit	
	public Poly derive(String var) {
        Poly res = new Poly();
        if (this.number.equals(BigInteger.ZERO)) {
            return res;
        }

        if (var.equals("x")) {
            // 1. 对 x 幂求导项： c * a * x^(a-1) * y^b * exp(E)
            if (powerX.compareTo(BigInteger.ZERO) > 0) {
                res.addUnit(new Unit(this.number.multiply(powerX),
                        powerX.subtract(BigInteger.ONE), powerY, exp.clone()));
            }
            // 2. 对 exp 链式求导项： c * x^a * y^b * exp(E) * E'_x
            if (!this.exp.isEmpty()) {
                Poly innerExp = this.exp.derive("x");
                if (!innerExp.isEmpty()) {
                    Unit baseU = new Unit(this.number, powerX, powerY, exp.clone());
                    for (Unit du : innerExp.getUnitMap().values()) {
                        res.addUnit(baseU.mulUnit(du));
                    }
                }
            }
        }
        else if (var.equals("y")) {
            // 1. 对 y 幂求导项
            if (powerY.compareTo(BigInteger.ZERO) > 0) {
                res.addUnit(new Unit(this.number.multiply(powerY), powerX,
                        powerY.subtract(BigInteger.ONE), exp.clone()));
            }
            // 2. 对 exp 链式求导项
            if (!this.exp.isEmpty()) {
                Poly innerExp = this.exp.derive("y");
                if (!innerExp.isEmpty()) {
                    Unit baseU = new Unit(this.number, powerX, powerY, exp.clone());
                    for (Unit du : innerExp.getUnitMap().values()) {
                        res.addUnit(baseU.mulUnit(du));
                    }
                }
            }
        }
        return res;
    }

bug 分析

其实感觉第三次作业大家互测都在刀第二次作业的bug，对我这种重构的人打击是毁灭性的o(╥﹏╥)o

我觉得第三次会出现的 bug 主要分为两类：

递推函数的预处理解析出现问题，还是要注意处理好空格和连续的加减
第二次作业的部分有没有被发现的问题

最终的复杂度

Method	CogC	ev(G)	iv(G)	v(G)
Choice.Choice(Poly, Poly, String, String, FuncLib)	0	1	1	1
Choice.toPoly()	2	1	1	2
Exp.Exp(Poly)	0	1	1	1
Exp.expPower(Poly)	0	1	1	1
Exp.toPoly()	0	1	1	1
Func.Func(String, Poly, FuncLib)	0	1	1	1
Func.toPoly()	0	1	1	1
FuncLib.FuncLib()	0	1	1	1
FuncLib.addFunc(String, String)	0	1	1	1
FuncLib.addRecFunc(String, String, String)	5	1	5	5
FuncLib.findFunc(String)	1	1	2	2
FuncLib.toPoly(String)	2	1	2	2
Gdc.Gdc(ArrayList)	0	1	1	1
Gdc.getAllGdc()	5	2	4	5
Gdc.getMultiGdc()	5		3	5
Lexer.Lexer(String)	0	1	1	1
Lexer.getC()	8	1	7	8
Lexer.getCurToken(char)	11	1		9
Lexer.getD()	8	1	7	8
Lexer.getFuncName()	8	1	7	8
Lexer.getNumber()	2	1	3	3
Lexer.getParameter()	7	1	6	7
Lexer.getTokenType()	0	1	1	1
Lexer.getTokenType(char)	1	1	1
Lexer.next()	5	2	4	5
Lexer.peek()	0	1	1	1
MainClass.main(String[])	4	1	4	4
Number.Number(BigInteger)	0	1	1	1
Number.toPoly()	0	1	1	1
Parser.Parser(Lexer, FuncLib)	0	1	1	1
Parser.parseChoiceFactor()	0	1	1	1
Parser.parseDeriveFactor()	4	1	3	3
Parser.parseExpFactor()	1	1	2	2
Parser.parseExpr()	5	1	5	5
Parser.parseExprFactor()	1	1	2	2
Parser.parseFactor()	3	1	3	9
Parser.parseFuncFactor()	0	1	1	1
Parser.parseNumberFactor()	1	1	2	2
Parser.parsePowerFactor()	2	1	2	2
Parser.parseTerm()	1	1	2	2
Poly.Poly()	0	1	1	1
Poly.addPoly(Poly)	5	1	4	4
Poly.addUnit(Unit)	0	1	1	1
Poly.clone()	3	1	3	3
Poly.derive(String)	3	1	3	3
Poly.divideNum(BigInteger)	1	1	2	2
Poly.equals(Object)	3	3	2	4
Poly.expPoly(BigInteger)	9		7	8
Poly.getNumbers()	1	1	2	2
Poly.getUnitMap()	0	1	1	1
Poly.hashCode()	1	1	2	2
Poly.invalidateStringCache()	0	1	1	1
Poly.isEmpty()	0	1	1	1
Poly.isMathEquals(Poly)	0	1	1	1
Poly.isSingle()	8		5	5
Poly.mulPoly(Poly)	5	2	4	5
Poly.negate()	1	1	2	2
Poly.removeZero()	9		5	8
Poly.subPoly(Poly)	0	1	1	1
Poly.substitute(Poly)	3	1	3	3
Poly.toExpString()		3	7	8
Poly.toString()	14	3	6	9
Power.Power(String, BigInteger)	0	1	1	1
Power.toPoly()	2	1	3	3
Processer.Processer(String)	0	1	1	1
Processer.adjustInput()	0	1	1	1
Processer.adjustSign()	1	1	2	2
Processer.delBlank()	0	1	1	1
Unit.Unit(BigInteger, BigInteger, BigInteger, Poly)	0	1	1	1
Unit.addUnit(Unit)	0	1	1	1
Unit.clone()	0	1	1	1
Unit.derive(String)		2
Unit.divideNum(BigInteger)	0	1	1	1
Unit.equals(Object)	4	3	5	7
Unit.expUnit(BigInteger)	5	3	4	5
Unit.getNumber()	0	1	1	1
Unit.hashCode()	0	1	1	1
Unit.isSingle()	9
Unit.isZero()	0	1	1	1
Unit.mulUnit(Unit)	0	1	1	1
Unit.negate()	0	1	1	1
Unit.substitute(Poly)	2	2	2	3
Unit.toKey()	0	1	1	1
Unit.toString()		1
UnitKey.UnitKey(BigInteger, BigInteger, Poly)	0	1	1	1
UnitKey.equals(Object)	4	3	4	6
UnitKey.hashCode()	0	1	1	1

分析：

有几个方法的复杂度指标（特别是 CogC 和 v(G)）严重偏高：
- Unit.derive(String)：这是项目中逻辑最复杂的地方。derive（求导）操作涉及大量的递归或分支逻辑，不仅内部路径多（v(G)=12），而且对外部依赖严重。
- Unit.toString()：虽然功能只是格式化输出，但其复杂的逻辑分支导致可读性极差。
- Poly.toExpString()
- Lexer 系列方法 (getCurToken, getD, getFuncName)：逻辑非常密集，特别是 Lexer.getTokenType(char) 的 v(G) 高达 14 。使用了冗长的 switch-case 或 if-else 来判断字符类型。
iv(G) 设计复杂度过高：有些方法不仅“难读”，而且“耦合度高”。
结构化程度 ev(G)：大部分方法 ev(G) 为 1，代码逻辑结构还算规整。

写在最后：

在这个AI盛行的时代，手搓有价值吗？有的有的！

我发现很多同学debug的困难在于，他的代码是AI写的根本不知道写的什么

当然我发现善用AI也很重要，主要在以下方面：

评测机几乎就是通过AI对话获得的，对于一些非极端特例的bug，其还是能检测出不少的

p.s 我和伙伴发现，评测机没有办法很好的解决TLE的问题，因为每个机器上面CPU运行时间是不一样的，互测被刀的数据可能在自己的电脑上面是没有超时的
我总是发现AI代码的优化更好，表达式总是又短生成又快，所以我觉得用AI来进行一些表达式的优化工作的是可行的，当然AI会在优化过程中带来莫名其妙的bug
其实互测除了白盒测试、黑盒测试，还可以压力AI测试。把代码丢给AI，然后输入我的惯用PUA话语”这个代码有bug请你告诉我，一定有一定有“，往往有奇效。

本作品由一一于 2026-03-30 14:00:00 发布

作品地址：北航oo面向对象设计与构造第一单元总结

除特别声明外，本站作品均采用 CC BY-NC-SA 4.0 许可协议，转载请注明来自 anAilurus' Blog

oo 北航大二

北航oo面向对象设计与构造第一单元总结

第一单元 表达式展开

第一次作业

代码架构

预处理

这里有个理解问题，重复的加减到底是如何出现的？

表达式解析

lexer 部分

parser 部分

表达式计算

unit

Poly

化简技巧：

bug 分析

第二次作业

代码架构

预处理

表达式解析

lexer

Parser

表达式计算

bug 分析

第三次作业

代码架构

自定义递推函数

求导算子

bug 分析

最终的复杂度

第一单元表达式展开