Java实现表达式化简，支持括号嵌套、三角函数化简、求导运算

第一次作业

1. 迭代思路

（1）预处理（Worker类）

• 去除所有空白字符
• 将所有连续的正负号合并为一个

（2）文法改写（Parser类）

• 左递归文法是指文法中存在某个非终结符 A，使得 A 可以通过一系列推导得到以自身开头的符号串
• 递归下降法是一种自顶向下分析的分析方法，它无法直接处理左递归文法，会导致无限循环
• 所以，考虑对文法进行改写，消除左递归，生成新的易于解析的文法

表达式 → [加减] 项 | 表达式 加减 项
项 → [加减] 因子 | 项 '*' 因子

表达式 → [加减] 项 中间表达式
中间表达式 → null | 加减 项 中间表达式
项 → [加减] 因子 中间项
中间项 → null | '*' 因子 中间项

• 在代码实现层面，使用修改后的文法在编程时无需过多考虑，直接翻译即可

// 表达式 →  [加减] 项 中间表达式
public Poly parseExp() {
    Poly sign = parseSign();
    Poly term = parseTerm();
    Poly midExp = parseMidExp();
    return term.mul(sign).add(midExp);
}

// 中间表达式 → null | 加减 项 中间表达式
public Poly parseMidExp() {
    if (pos < input.length() && (input.charAt(pos) == '+' || input.charAt(pos) == '-')) {
        Poly sign = parseSign();
        Poly term = parseTerm();
        Poly midExp = parseMidExp();
        return midExp.add(term.mul(sign));
    }
    return new Poly(BigInteger.ZERO);
}

// 项 → 加减 因子 中间项
public Poly parseTerm() {
    Poly sign = parseSign();
    Poly factor = parseFactor();
    Poly midTerm = parseMidTerm();
    return factor.mul(sign).mul(midTerm);
}

// 中间项 → null | '*' 因子 中间项
public Poly parseMidTerm() {
    if (pos < input.length() && input.charAt(pos) == '*') {
        pos++;
        Poly factor = parseFactor();
        Poly midTerm = parseMidTerm();
        return factor.mul(midTerm);
    }
    return new Poly(BigInteger.ONE);
}

（3）表达式存储

• 由于本次作业只涉及x的幂函数，所以使用单个哈希表对多项式进行存储

• 哈希表的Key代表幂次，Value代表该幂次对应的系数，维护哈希表使得增删改查都非常快

（4）一切皆Poly（Poly类）

• 如果你比较细心，可能会发现，在上面展示Parser类的代码时，方法的返回值都是Poly
• 在我的架构设计中，只向外暴露一个Poly类，Poly类内部维护一个上述的哈希表，实现了各类运算的成员方法
• 这样做减少了维护不同类型数据的难度，把所有的内容都看作Poly，无需过多考虑直接运算即可，较好的满足了面向对象编程的高内聚低耦合思想，这一点的优势在后续的迭代中会充分体现

2. 优化方法

• 如果结果以负号开头，那么输出结果会比最优结果长一个字符
• 我的优化方法是：在toString方法中，与数学上的降幂排列不同，我将各项按照系数从大到小排列
• 这样做尽可能保证正项在前，实现最佳的性能，最短的输出

3. bug分析

• 本次作业强测和互测均未出现bug

第二次作业

1. 迭代思路

（1）函数预处理（Worker类）

• 形参列表统一化：形参列表强制转为(x,y)，那么思考一下，如果是单个参数的函数，怎么办？答案很简单，单个参数的函数，在调用时，无论另一个参数传入什么，都不会影响函数调用的值，忽视掉他即可
• 排序：对于递归函数的三行定义进行排序，最后，把函数定义“=”左端内容去掉，构建成易于解析的字符串。

（2）表达式存储（Poly->Mono->Expr)

第二次作业相比第一次作业，复杂程度剧烈上升，第一次作业相对简单的架构显然不能满足这样的需求，重构势在必行

• 采用Poly（多项式） -> Mono（单项式） -> Expr（因子） 三层架构
• Poly类维护一个Mono类的ArrayList
• Mono类维护一个Expr类的ArrayList
• Expr类存储最小的，不可进一步合并的表达式单元，分为三种类型，常数、幂函数和三角函数

（3）递归函数实现（Func类）

• Func类维护一个Poly类的ArrayList和一个字符串，ArrayList内存储初始定义和之前计算好的定义，字符串存储递归定义
• 为了应对日后迭代多个函数的情景，我在Worker类定义一个静态的公开哈希表，以函数名作为Key，函数类对象作为Value
• 这样一方面防止错误的调用其他函数，另一方面，静态公开的对象，保证之前定义的函数无论何时被调用，都能访问到，这很好的解决了一个函数可以由另一个函数定义的问题，当然，这也是后续迭代需要考虑的问题了
• 在调用函数的时候，首先将递归层数n通过字符串替换的方式，把递归定义换成对应的数字，而后将生成的新表达式进行解析，直到回归初始定义。通过这样的方式，我们能求出所有小于等于n的函数表达式，将他们存储下来，带入形参即可

（4）代入方法

• 在解析函数的过程中，需要将形参带入函数表达式，所以对上述的三层架构，就需要分别实现代入方法
• 如果是常规的架构设计，代入因子，返回单项式；代入单项式，返回多项式，难免考虑对象的类型转换，而一切皆Poly的方法，能很好的避免这些麻烦，所有的代入和加减乘运算，返回的都是Poly，编程时对语法的考虑更少

（5）toString方法

• 在本次迭代过程中，我们需要对三角函数进行输出，由于我们把所有内容都视作多项式，不区分因子和表达式，那么三角函数内的多项式应该是一层括号还是两层括号，是必须要考虑的问题
• 判定方法如下：只有当该多项式只有一个单项式，且该单项式只有一个因子，或者两个因子其中一个是常数1的情况下，输出单层括号，其余情况均为双层括号

2. 优化方法

本次作业的优化比较困难，可优化的点比较多，为了在优化的同时，保证代码的简洁性与正确性，我并没有创建单独的优化类，而是只考虑了能够在计算中进行的优化，这样做一方面减少出bug的可能，另一方面也节约了时间的开销

（1）$ sin(0) = 0 ,\space cos(0)=1$

• 在Poly类的构造函数中，进行特殊判定
• 从源头上杜绝了上述不美观形式的出现，为后续的处理打下坚实的基础

（2）$ sin(-f(x)) = -sin(f(x)),\space cos(-f(x)) = cos(f(x))$

• 在Poly类的构造函数中，进行特殊判定，那么判定条件是什么呢？
• 如果无脑替换，很可能导致优化后长度变长，这是我们不愿意看到的
• 所以采用如下判断方法，首先保证Poly类的toString方法，尽可能的满足正项在前（与第一次作业的优化方式相同），那么如果内部因子的负号以负号开头，那么证明这个多项式所有的项都是负的，需要进行上述优化，这样的优化方式可以保证结果一定变短

（3）$ 2^nsin^n(f(x))cos^n(f(x)) = sin^n(2\cdot f(x))$

• 对于二倍角优化，在向单项式乘因子的时候同步进行，减少不必要的遍历，降低犯错可能性
• 当前向单项式中乘一个$ sin^n(f(x)) $，需要检查单项式的系数是否为$2^n$的倍数，是否存在$cos^n (f(x))$，如果条件满足，那么可以合并为一项，单项式系数不要忘记除以$2^n$，函数名交换亦然

（4）$ g(x)\cdot sin^2(f(x)) + g(x)\cdot cos^2(f(x)) = g(x) $

• 对于平方和优化，在向多项式插入单项式的时候同步进行，同样，减少犯错的可能性，但很不幸，我初次实现的时候还是犯错了
• 遍历原多项式，如果待插入的单项式$A$和遍历到的单项式$B$的因子个数一致，那么这两个单项式有合并的可能，否则一定是不能合并的
• 如果有合并的可能，遍历单项式$A$，忽略系数的情况下，遍历查找单项式$B$是否有相同的因子，如果没有，那么将该因子的索引插入列表，最终返回所有不能匹配的因子的索引
• 如果列表为空，那么代表可以直接合并同类项；如果列表长度为1，那么检查是否是满足$sin^2(f(x))$的形式，如果满足，那么回到原单项式中，查找是否有对应的$cos^2(f(x))$，如果有，那么把原多项式的这一项合并为1，函数名交换亦然；否则直接插入

3. bug分析

本次作业强测侥幸未出现bug，得分97.7分，互测出现两个异质bug

• 平方和优化出错：不难看出，上述优化中对平方和的优化方法是复杂度是非常高的，在提交中测的那一版本代码中，我妄想通过单次遍历实现这一复杂的合并，在判断因子是否相同时，草率地把$sin^2(f(x))$和$cos^2((f(x)))$认为是可以匹配的，这导致在某些情况下，本应合并同类项的两个单项式，错误的进行了归一化。但这个错误是比较隐蔽的，只有当两个单项式本身是可合并的，而且还出现了互补的三角函数项时，才会犯这个错误
• 超时问题：对于复杂的三角函数多层嵌套的样例，输出速度过慢导致超时，为解决这个问题，我通过IDEA中代码复杂度分析，以及运行时间监视的方法，成功找到了复杂度较高，耗时较长的方法
  • 因子类的toString方法，在涉及三角函数时，需要对内部表达式进行层层解析后才能输出，调用多次时，时间开销是惊人的，所以对于每一个三角函数因子，我为之添加了一个成员变量，用于存储内部表达式解析出的字符串，在构造方法中为变量赋值，这样避免了重复调用toString方法，极大节约了时间开销
  • 初版的代入方法，我采用的是套括号进行字符串替换的方法，这种方法会导致一些本来被解析过的内容被重复解析，也会造成一定的时间浪费，于是我将字符串替换改为更加科学的逐层代入方法
  • 对于递归函数的调用，可能涉及多次调用的情况，如果之前计算的结果没有被保留，有可能造成极大的时间浪费，所以我在每一次调用递归函数时，都会将调用结果存入该Func类，为下次调用提供便利

经过上述对于逻辑的修改，以及大刀阔斧的时间优化，我才艰难的通过了bug修复环节

第三次作业

1. 迭代思路

（1）普通函数实现（Func类）

• Func类添加一个Poly类的成员变量，用于存储普通函数的表达式
• 在调用普通函数的时候，直接调用代入方法，将形参代入定义表达式即可
• 两种类型的函数用同样的类维护，对外需要暴露两种不同的构造方法和调用方法

public class Func {
    private final ArrayList<Poly> initial = new ArrayList<>();
    private String input;
    private Poly definition;

    Func(StringBuilder input) {
        Parser p = new Parser(input);
        definition = p.parseExp();
    }

    Func(ArrayList<StringBuilder> in) {
        Parser p = new Parser(in.get(0));
        initial.add(p.parseExp());
        p = new Parser(in.get(1));
        initial.add(p.parseExp());
        input = in.get(2).toString();
    }

    public Poly call(Poly x, Poly y) {
        return definition.substitution(x, y);
    }

    public Poly call(Integer n, Poly x, Poly y) {
        for (int i = initial.size(); i <= n; i++) {
            String temp = input.replaceAll("n-1", Integer.toString(i - 1))
                .replaceAll("n-2", Integer.toString(i - 2));
            Parser p = new Parser(new StringBuilder(temp));
            initial.add(p.parseExp());
        }
        return initial.get(n).substitution(x, y);
    }
}

（2）求导方法

• 和带入方法类似，这只是增添了一种运算方法而已，对上述的三层架构，按照求导公式，利用已经实现的加减乘运算，分别添加求导方法即可

2. 优化方法

本次作业我没有进行新的优化

3. bug分析

强测大翻车，出现5个bug，得分71.2分，互测出现5个bug，这10个bug均为同质bug

• 由于对求导因子解析的过程中，没有吃掉dx后面的右括号，导致所有求导因子后面的表达式都无法正常解析，默认解析为乘1，后果十分惨烈
• 在中测极弱的情况下，由于个人的懈怠，我没有进行手动构造数据进行测试，也没有通过自动化方法进行评测，反而放松了警惕，沉浸于第二次强测侥幸通过的喜悦中，将希望寄托于运气，于是，第三次强测便给了我当头一棒
• 添加一行pos++便修复了所有bug，让我想起因为算错一个小数点导致飞机坠毁的事故，不禁庆幸这只是一次练习，那么如果我的这次失误出现在企业发行的产品中呢？那造成的损失，恐怕会让我直接吃上牢饭

总体复盘

1. 架构分析

• 三次作业中，我的核心思想都是一致的，从主类中获取输入，送给Worker类进行处理
• Worker类首先进行预处理后，把处理好的函数送给Func类解析，待化简的表达式送给Parser类解析
• Func类中再次使用Parser为函数的定义进行解析，将结果送入Worker类中存储函数的哈希表
• 所有的类均可以使用Worker类中存储函数的哈希表，实现函数的嵌套定义
• 解析的结果全部规定为多项式，减少类型转换的麻烦
• 多项式类在第一次作业相对简单，后续作业经历了重构，实现了Poly（多项式） -> Mono（单项式） -> Expr（因子） 三层架构，但对外只暴露Poly接口，符合高内聚低耦合的思想

2. 复杂度分析

• 在最终的作业中，我仅使用了七个类，上图是每个类的复杂度，其实单看每个方法，复杂度都不算很高，但最终WMC（加权方法复杂度）却全部爆红，这并不符合面向对象的思想
• 对于后续的改进，可以将功能不同的方法，封装到多个类中，例如三角函数因子，常数因子，幂函数因子，分为三个类，由Expr类提供统一的接口，降低方法的复杂度，提高代码的可拓展性

上图是我作业中CogC（圈复杂度）最高的20个方法，下面我对圈复杂度前五的方法进行分析

• 两个是toString方法，用于在输出时进行小范围的优化，可以考虑将其中复杂的判断分为多个方法来写，降低方法的复杂度
• 对于预处理类中，处理连续的加减号，以及参数列表的转换过程，本身就涉及较为复杂的字符串操作，但测试难度并不算高，复杂度略高一点也是能够接受的
• 在解析函数方法中，我将递归函数和普通函数同等看待，同样方法解析，因此复杂度较高，而且我在其中嵌套了较多的条件语句，这对于测试是很不利的，所以可以考虑将两种函数的解析方法分开，减少出错的可能

3. 迭代情景

假设新的迭代情景需要考虑指数函数、对数函数、以及其他不同名的三角函数，且保证求导因子中没有对数函数

• 如果是目前的架构，那么需要对Expr类进行大规模的改写，其中的每个方法后都要添加一段处理新函数的代码，这对于迭代开发是非常不利的
• 因此如果在降低复杂度的情况下进行迭代，必须进行一次小范围的重构，指数因子，三角函数因子，常数因子，幂函数因子，分为四个类，由Expr类提供统一的接口
• 六种不同名的三角函数创建六个类，都继承于三角函数因子类，每个模块层次分明，功能清晰
• 最终需要实现的是，各种因子的加、减、乘、求导、代入方法，同时需要重写toString和equals方法

4. hack策略

• 在前两次作业中，我的代码在A房，而且没有写数据生成器，对互测的参与度不算很高，所以只是根据自己和他人的经验，提交了几个自认为有可能出错的样例，并在第二次作业中成功hack两次
• 第三次作业中，我发现自己进入C房后，内心十分焦虑，迅速写了一个简陋的数据生成器，生成一些复杂度并不高的样例
• 在生成的过程中，我没有考虑符号嵌套的情况，只有一些普通的运算，考虑到互测的数据限制，以及C房的代码健壮性，我认为这样的生成方式也是相对合理的
• 正确性判断方法也同样简陋，我使用了一个A房同学的代码，假定他的输出为标准答案，将本房的代码与A房同学的代码的输出，用减号拼接起来，再送入A房同学的代码中计算结果，在逻辑上实现结果作差
• 如果结果为0，那么有较大的把握认为这个测试点是通过的，否则，需要人工检查一下，是否是因为优化导致的无法进一步化简，采用这样的方式，我在很短的时间内成功hack了六次

心得体会

1. 设计架构

• 将所有表达式统一为Poly类（多项式），通过内部嵌套Mono（单项式）和Expr（因子）实现层级化存储。这种设计避免了不同类型数据的频繁转换，符合高内聚低耦合的特点，显著降低了代码复杂度

• 通过消除左递归文法，实现了代码结构与文法规则的契合

• 在进行复杂度分析时，发现自己的类个数较少，WMC非常高，可拓展性并不强，这警示我在之后的编程中，尽可能将功能不同的方法，封装到多个类中，降低方法的复杂度，也降低自己调试的难度

2. 速度优化

• 通过监视运行时间，定位高复杂度方法（如toString），将三角函数内部表达式的字符串缓存，避免重复解析

• 使用静态哈希表缓存已定义函数，递归调用时逐层展开并缓存结果，减少重复运算

3. 未来改进方向

• 可将不同类型的因子类（Expr）用不同类进行维护，提高架构的可拓展性，降低因子类的复杂度

• 可将递归函数和普通函数分开解析，降低ParseFunc方法的复杂度

4. 总结

• 本单元通过三次迭代逐步处理复杂表达式，让我深刻体会到抽象设计和代码测试的重要性，也熟练掌握了程序的调试方法

• 写程序的思维从面向过程转变为面向对象，让自己的设计尽可能满足高内聚低耦合的特点，同时我也感受到了面向对象与面向过程之间的差异，面向对象的编程只需要让每个部分做好自己的事情，向外暴露简单易用的接口，供其他模块使用

• 在迭代的过程中，从最初的表达式展开，到三角函数化简，再到最终的求导功能，每一步都困难重重，在经历一次大规模重构，以及反复的bug修复后，我完成了最终的任务，在代码运行成功的那一刻，内心还是成就感满满的
• 本次作业我认为我做的不够好，第三次作业因缺乏自动化测试导致强测翻车，我深刻体会到了构造测试数据，对代码进行测试的必要性，但好在这才是第一个迭代任务，略有遗憾也在情理之中
• 悟已往之不谏，知来者之可追，已经失去的分数无法挽回，我将调整好心态，以更严谨的思维，更谦卑的态度，面对这门课程之后更大的挑战

未来方向

本单元的课程经受多年的考验，我认为设置已经相对完善，感谢在此过程中为同学们辛勤付出的老师和助教