基于度量分析程序结构

类图

Unit1 最终版本的类图如上图所示。整个程序的核心思想采用了递归下降法，大体流程是：对于输入数据 input，先在 Main 方法中依次调用类 ComFunc 的 defineComFunc 静态方法和 RecFunc 的 defineRecFunc 静态方法，解析自定义普通函数和自定义递推函数，然后再解析待展开表达式：实例化一个 Lexer 对象，实现词法解析，并将解析的结果传递到 Parse 的实例对象，实现语法解析，解析得到一个 Expr 实例 expr，然后再将 expr 转为 Poly（由 Unit 构成）的多项式形式，并在转化的过程中实现表达式的计算（实体类 Poly 与 Unit）与化简（工具类 Simplify），最后将结果作为字符串输出。

度量

IntelliJ IDEA 的插件 MetricsReloaded 帮助计算了以下方法度量值，故在此围绕这些度量进行分析。

CogC（Cognitive Complexity，认知复杂度）

CogC 是通过代码中的逻辑分支（如 if、for、switch）和嵌套层级计算，衡量代码的对于程序员的理解难度（单个方法的 CogC 应 < 15）。由上图可见，大部分方法认知复杂度合理，但个别方法的认知复杂度较大。经分析，主要是由于单个方法中逻辑分支过多、判断条件复杂以及嵌套层级较深所导致。

优化方案：使用卫语句（Guard Clauses）提前返回，减少嵌套层级。
ev(G)（基本复杂度）与 iv(G) （模块设计复杂度）

ev(G) 衡量代码中非结构化逻辑的复杂度，值越高说明代码越难以简化或重构（单个方法的 ev(G) 应接近 1）；iv(G) 衡量模块与其他模块之间的交互复杂度（单个方法的 iv(G) 应 < 9）。由上图可见大部分方法的复杂度都比较合理，但是个别方法复杂度太大。经分析，主要是由于一个方法中过多地调用其它类方法，导致过多依赖外部逻辑，违反了低耦合原则。

优化方案：
- 模块的功能化分尽可能的单一（功能单一的模块供其它模块调用的机会就少）。
- 类属性和方法的声明少用 public，多用 private 关键字（公共的就有可能被到处调用，到处 new 对象）。
- 少使用类的继承，多用接口隐藏实现的细节。

v(G)（圈复杂度）

v(G) 是基于代码中独立路径数量的经典复杂度指标，高 v(G) 的代码单元测试需要覆盖更多路径（单个方法的 v(G) 应< 10）。由上图可见个别方法圈复杂度太大，经分析主要是条件判断和处理逻辑太复杂导致的，如圈复杂度为 40 的一个方法：

public static ArrayList<Unit> simplify(Unit unit1, Unit unit2, Unit samePart) {
        // ...
        if (s1 == 1 && c1 == 0 && c2 == 1 && s2 == 0) {
            units = simplifyOne(unitOnly1, unitOnly2);
            if (units != null) {
                return units;
            }
        } else if (s2 == 1 && c2 == 0 && c1 == 1 && s1 == 0) {
            units = simplifyOne(unitOnly2, unitOnly1);
            if (units != null) {
                return units;
            }
        }
        // ... 大量类似于上述的if-else if分支，其中条件判断包含 && 和 ||
    }

优化方案：使用策略模式，将每个条件分支的条件判断和处理逻辑分离。

public static ArrayList<Unit> simplify(Unit unit1, Unit unit2, Unit samePart) {
    // 定义条件-处理的策略列表
    List<SimplificationStrategy> strategies = Arrays.asList(
        new SimplificationStrategy(SimplifyType.ONE, (u1, u2) -> checkSize(u1, 1, 0) && checkSize(u2, 0, 1)),
        new SimplificationStrategy(SimplifyType.ONE, (u1, u2) -> checkSize(u2, 1, 0) && checkSize(u1, 0, 1))
    );

    // 按顺序匹配策略
    for (SimplificationStrategy strategy : strategies) {
        if (strategy.condition.test(unitOnly1, unitOnly2)) {
            ArrayList<Unit> result = strategy.apply(unitOnly1, unitOnly2);
            if (result != null || strategy.allowNullResult) {
                return result;
            }
        }
    }
}
// ... 定义内部类策略类 SimplificationStrategy，封装条件和处理方法

分析总结

优点：对于表达式（包括自定义函数）的解析，使用工具类 Lexer 和 Parse，实现了模块化与单一原则。对于表达式的语法解析，将每个层次封装为一个类，同一层次若有不同类型则封装为接口（如 Factor），并通过类（如 NumFactor，DrvFactor 等）实现接口的方式实现，最终形成语法树。这种方式将不同表达式的构成高度模块化，遵循高内聚低耦合的思想，使代码的调试、修改与重构，以及迭代中的增量开发变得更加清晰容易。
缺点：部分方法太过臃肿，例如表达式的计算与化简，很多方法都是面向过程，没有很好地使用 java 设计模式的特性。

架构设计体验

第一次作业：参考往届博客经验，采用先导课所讲的梯度下降法。先进行词法解析生成 Token 流，词法解析结束后表达式将不包含空白项，不包含多余正负号。再进行语法解析，从左至右遍历 Token 流，按照形式化表述递归解析（自上而下），生成语法树。最后自下而上依次将因子、项、表达式转化为多项式形式。多项式 Poly 由若干个 Mono 组成，Mono 的基本形式为 a * xⁿ，这种形式可以将所有表达式构成转化为统一的形式，极大地便利了计算与化简过程。

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String input = scanner.nextLine();

        Lexer lexer = new Lexer(input.replaceAll("[ \t]", "")); // 删除所有空白符
        Parse parser = new Parse(lexer);
        Expr expr = parser.parseExpr();
        System.out.println(expr.toPoly());
    }
}

第二次作业：程序主体流程与第一次作业相同，难点主要在于三角函数的计算与化简、自定义递推表达式调用的解析。由于引入三角函数，故最小单元 Mono 需要调整为 Unit，其基本形式为

axⁿ∏sinⁱ(factor)∏cos^j(factor)
- 对于自定义递推表达式的定义，借助递推函数类 RecFunc 中的 defineRecFunc 静态方法实现解析，解析结果保存为字符串；对于递推调用，解析步骤是：先将 f{n} 表达式的所有形参正确替换为实参，得到替换结果 exprString，再对 exprString 进行与题目输入表达式相同的解析流程，即词法解析、语法解析和转为多项式形式，结果保存在该递推实例中。
- 对于三角函数的计算与化简，难点在于如何判断两个三角函数括号内的内容是否相等或互为相反数、如何分离出两个 unit 的不同部分。
  - 对于两个三角函数括号内内容的比较，我起初做法是将两个内容 poly1 与 poly2 进行加减运算，若相加为得到的 poly 为 0，那么互为相反数；若相减得到的 poly 为 0，那么相等；否则既不相等也不互为相反数。这种做法确实可行，且帮助我渡过了强测与互测，但是我在应对形如 f{5}(f{5}(f{5}(sin(sin(sin(x)))))) 的表达式时，出现了长时间出不了结果的问题。通过工具分析，发现上述比较过程占据了大量的时间（因为每比较一次就要进行 Poly 的计算与化简）。所以最后我不得不重构，采用了重写 hashCode() 和 equals() 方法的方式实现三角函数内容的比较，这种方式确实极大地优化了我程序的时间复杂度。
    
    重构前：
    
    重构后：
  - 对于三角函数的化简，我在第二次作业中实现了以下几种类型的化简（下图截自第二次作业的思路 note）。
    
    我的化简思路是先判断两个 unit 是否符合化简的前置条件，即幂指数是否相等。若符合，则提取两个 unit 的公共部分，再根据公共部分提取出两个 unit 的不同部分 unitOnly1 和 unitOnly2，最后再对这两个不同部分进行判断是否符合上图的化简情况。起初我的化简是在 Unit 类中实现的，后来发现类超过了 500 行，并且违反了单一职责原则，所以我新建了一个工具类 Simplify 专门用于化简三角函数。对于一些特殊情况的化简，如两个三角函数化简后，整个多项式又出现了可化简的两个 unit；-sin(x) 比 sin((-x)) 短等情况，我专门写了一些方法如 selfMerge() 和 selfSimplify() 用于化简：
    1
    2
    // class Main
    System.out.println(expr.toPoly().selfMerge().selfSimplify());

第三次作业：由于前两次作业的高度模块化，第三次作业要求新增的求导因子与自定义普通函数很快地实现了，且改动极小。我也趁此实现了三角和差公式的化简。最终的 main 方法是这样的：

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();
        scanner.nextLine(); // 读取换行符
        if (n != 0) {   // 读取普通函数定义并解析
            ArrayList<String> definitions = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                definitions.add(scanner.nextLine().replaceAll("[ \t\n]", ""));
            }
            ComFunc.defineComFunc(definitions);
        }

        int m = scanner.nextInt();
        scanner.nextLine(); // 读取换行符
        if (m == 1) {   // 读取递推函数定义并解析
            ArrayList<String> definition = new ArrayList<>();
            for (int i = 0; i < 3; i++) {
                definition.add(scanner.nextLine().replaceAll("[ \t\n]", ""));
            }
            RecFunc.defineRecFunc(definition);
        }

        String input = scanner.nextLine();
        Lexer lexer = new Lexer(input.replaceAll("[ \t]", "")); // 删除所有空白符
        Parse parser = new Parse(lexer);
        Expr expr = parser.parseExpr();
        System.out.println(expr.toPoly().selfMerge().selfSimplify());
    }
}

若有新的迭代场景，如引入除法和小数，我的程序也能够稍加改动变可以实现：

词法解析新增除法 /，语法解析中因子与因子的连接符新增 /;
程序中作为系数出现的 BigInteger 替换为 BigDecimal;
Poly 与 Unit 计算引入除法，Unit 基本形式引入分子部分和分母部分；
对于化简，可以先对 unit 各自进行约分化简，即遍历分子分母，有无同项化简、二倍角化简，然后在进行 unit 间的化简。

程序 bug 分析

很幸运，在第一单元中，我只在第二次作业的强测和互测各有一个点未通过，其余测试均 AC。我将其归功于高度模块化的程序结构设计与自主搭建的评测机的压力测试。未通过的两个点都是同一个 bug：当三角函数括号内为非因子时，我在某些情况下不会输出非因子外应有的一层括号。具体而言，当输入为 sin((sin(x)*cos(x))) 时，我会输出 sin(sin(x)*cos(x))，不符合形式化表述。

原因：我在判断是否要输出嵌套括号时，对三角函数因子匹配采用了错误的正则表达式匹配逻辑：^(sin|cos)$(.)+$$，由于贪婪匹配的特性，导致 x)*cos(x 会被 (.)+ 给匹配，从而误以为该表达式是三角函数因子，实则为项。

解决方案：强化判断。在匹配上述正则的情况下，遍历三角函数括号内部分，记录括号匹配情况，当第一次出现左右括号一一配对完毕时，若仍有剩余内容，则非三角函数因子，反之则为三角函数因子。

互测策略

基于 Python 搭建的评测机。

generate_data.py 完全遵守形式化表述，依概率随机生成输入样例。并手动调节自定义函数和输入表达式的项与因子个数，限制生成样例的复杂度，提高生成样例的质量。

pipeline.py 作为对拍器，从 generate.py 获取输入样例，并依次输入给不同的 .jar 程序，获取相应的输出，借助 Python 的第三方库函数 Sympy 进行两两比较，当出现表达式不相等或超时时终止程序并保存相应的样例。

由于互测输入数据的限制，对于别人出现异常的输入样例，先进行手动化简，定位到测试出 bug 的数据段，然后再提交样例。

程序优化分析

代码结构优化：对于三角函数的化简功能，一开始是在 Unit 类中实现，但发现类行数超过 500。经过分析，该代码设计违反了单一职责原则，Unit 类做了过多的实现。因此我新建了 Simplify 类，专门用于三角函数的化简，既减轻了 Unit 的负担，也使代码更加清晰易懂。
时间复杂度优化：对于不同三角函数的括号内内容的比较，一开始通过计算的方式实现，但该方法时间复杂度巨大，有大量重复且冗余的计算。因此我通过重写 Poly 与 Unit 的 hashCode() 与 equals() 方法，避免了比较时多项式的计算，而是通过 hash 值的计算，大大优化了时间复杂度。

我的优化可以保证代码的简洁性与正确性。主要得益于我尽可能地限制了类成员的访问级别，实体类字段一律采用 private 属性，外部只能通过调用 get 方法去访问。部分类方法采用 priavte 字段，避免外部类去更改该类的属性。在重构时，基本只需关注代码编译正确性而非运行正确性，因为类的属性被很好地保护。

心得体会

本单元我最大的收获主要是以下三方面：

大大加深了对递归下降法的理解：通过该单元的练习，我从先导课时对递归下降法的晦涩不解、望而生畏，到三次迭代作业结束后对递归下降法的清晰明了、游刃有余。在这个过程中，我深刻体会到递归下降的优雅，极大地方便了对一串输入的解析与处理。
第一次自主搭建了评测机：在 OO 强测与互测的压力下，我不得不去搭建一个评测机去测试我程序的正确性。这是我第一次搭建评测机。在这个过程中，我真的收获颇多，学会了如何依概率生成测试数据、如何对数据生成质量调优、如何将 Python 程序打包成 exe 程序……
学会了如何重写 hashCode() 与 equals()：在重写的过程中，我深刻体会了 Java 比较两个对象是否相等的逻辑：先比较两个对象的 hash 值是否相等，若相等，再调用 equals() 方法进一步判断是否相等。并且，一个 Key 在放入 HashMap 之后，若其字段发生改变，HashMap 可能无法再找到这个 Key（除非用遍历的方法）！这个错误非常隐蔽，因此 HashMap 的键最好是不变类！

此外，对于大模型的使用，我也积累了一些经验。鉴于 DeepSeek 的强大功能，我在评测机搭建以及代码优化方面使用了大模型，以帮助我更好地实现。