你好！本文章为该博客的第⑩篇文章！

本文章包含北航2025面向对象设计与构造第一次作业的思路简述，期望通过一个我自己用的顺手的构造给予一些设计上的提示。

本文章即将同步投送至该次作业下的讨论区！

需要注意的是，本文仅完全适用于北航2025OO课程，对于之前和之后的课程，课程部分内容可能会发生变动，发生冲突时请以当前课程为准！

以及，如果本文章涉及学术诚信问题，请第一时间和我联系，我将及时做出修改，谢谢支持！

北航2025面向对象设计与构造第一次作业思路简述

前言——为什么要写这个

hw1本身难点在于递归下降的递归过程，以及化简过程中隐含的各类操作。

因此，总结一种尽可能简单，且基本符合课程组形式化描述的设计方法。

同时保证文字尽可能精炼，怕太长的文章没人读。

整体思路

采用递归下降的分析方法，定义乘法方法和加法方法化简表达式。细分为以下四步：

定义类型：好的类型能让后续过程更加容易处理。
词法分析：给出合理的切词方式。
语法分析：处理出表达式树。
括号拆解和同类项合并：拆开各级括号，同时用合并来避免计算过程项数过多。
调整符号和顺序：通过一些显然的优化，让表达式更简短。

定义类型

需要把表达式的一些必要信息以合理结构保存下来，同时避免处理过多细节。

基本思路是：表达式下若干项，项下若干因子。

由于因子中存在表达式因子，从而递归产生“表达式-项-因子”的结构，因此会有人担心该存储方式会产生无限递归，但可以证明表达式因子内的表达式长度相对于原表达式肯定是更小的，因此不会引起无限递归。

总之，所需的类型有7个：符号，数字，幂函数，表达式因子，因子接口，项，表达式。

其中，数字，幂函数，表达式因子需要实现因子接口。

其中，符号类为枚举类，仅用于辅助存储项的符号信息，数字类内不使用该类型。

此外，每个类型都必须包含一个Override的toString()方法，方便将其递归转化为字符串。

以及，在toString()方法内，大多数情况下你不应该对转化结果在此处进行简化，除指数为1的情况，或表达式起始项的符号为正等不会引起逻辑混乱的情况外。

在本次作业设计中，一种思路是保证所有类型构造后内部属性不可变，增加了时间和空间开销，以此保证不会因为浅克隆产生若干问题。

词法分析

采用课程组提供的递归下降的处理方法，并除空白字符处理外严格采用课程组给出的形式化描述。

可以发现，表达式可切分为若干词语（Token），类型如下：纯整数，正负符号，空白项，指数符号，变量，左括号，右括号。

对于数位和空白字符，可以贪婪的把尽可能多的连续字符合并，作为单个Token。

因此，可以将表达式字符串分割为若干互不相交的Token，每个Token包含其类型和内容（仅数位和变量需要）。

切分方法参考OOpre hw7。

需要指出，该方法下词法分析与形式化定义存在一个不同之处：在形式化定义中，空白项Token可包含0个空白字符，但词法分析中该Token至少需要一个空白字符才可以构建。

语法分析

以上对空白项Token的处理区别将在该部分显现出来。

修改形式化描述，要求空白项至少包含1个空白字符，且在其他对空白项的使用中，空白项总是可以出现0次。

故，当定义中出现“空白项”时，若当前Token为空白项，则直接丢弃该Token。

接下来，对于形式化描述中出现的各个模块，各自实现一个函数进行转化。

转化出一个模块的通用大致思路为，检查当前未被处理的首个Token的类型，若该类型恰好符合该模块定义的某种分支，则根据需求调用子函数处理，或读取信息并转化后丢弃该Token。

以表达式的转化为例（为方便表述，记录“此时未被使用的第一个Token”为起始Token）：

若起始Token为空白项，丢弃该Token。
此时若起始Token为符号，则“记录下该符号类型，之后若起始Token为空白项，丢弃该Token”。否则，仅记录符号类型为正，不丢弃Token。
此时尝试调用转换函数获取返回值，即获取一个项。将项中的符号信息与先前读取的符号信息合并（负正得负，负负得正），存入表达式的项的列表中。
此时若起始Token为空白项，跳过该Token。（到此为止，形式化表述的第一种情况结束）
此时若起始Token为符号，则重复第2步。否则，转化过程结束，返回结果。

由于因子中存在表达式因子，从而递归产生“表达式-项-因子”的结构，因此会有人担心转化过程产生无限递归，但可以证明表达式因子内所用Token个数相对于原表达式肯定是更少的，因此不会引起无限递归。

括号拆解和同类项合并

实测同类项合并不可能不做，否则运行速度极慢。

此处需要两个概念：规格化项，规格化表达式。

规格化项的要求为：项的符号为正，且项内要么有且仅有一个表达式因子，要么仅包含数字（1和-1不可省略）和幂函数（数字因子必须存在，幂函数的变量两两不同）。

规格化表达式的要求为：表达式具有若干项，项均为规格化项，项内无表达式因子，且项之间两两不为同类项。

下面给出一个结论：括号拆解的过程，实际上就是将整个表达式自底向上的转化为规格化表达式的过程。

因此，需要实现两个方法：将项转化为规格化项，将表达式转化为规格化表达式。

将表达式转化为规格化表达式后，得到的答案已经可以作为合法答案了。

将项转化为规格化项

先做两个易做的事情：

把项的数字因子直接相乘，同时将项的符号信息塞进数字因子里，保证有且仅有一个数字因子。
合并所有同变量幂函数。

接下来，如果项内无表达式因子，则直接结束该过程。

否则，把各个表达式因子中的表达式提取出来（表达式因子的幂次是多少，就要提取出多少个表达式）依次相乘，每做一次乘法之后就将运算结果规格化。

最后，将数字因子和幂函数乘入上述运算结果（为一个表达式），将该表达式封装为一个幂次为1的表达式因子后放入项中。

设置项的符号为正。

将表达式转化为规格化表达式

先获取所有规格化后的项的列表。

之后，遍历所有项，若该项为仅含一个表达式因子的项，则删除该项，将表达式因子内表达式的所有项提取出来放入列表中。

最后，可以确保所有项均为规格化且无表达式因子的项，合并同类项后消除含有0因子的项即可。

如果合并同类项后，表达式内没有任何项，则需要人为添加一个仅包含0因子的项。

上述过程所需的部分关键函数

项与项的乘法，表达式与项的乘法，表达式与表达式的乘法。三者为递进关系，可通过后者调用前者的方法实现。

调整符号和顺序

这里是一些对于规格化表达式转化为长度更小的表达式的优化。

若项中存在负数因子，则可以将其符号反转，将项的符号也反转。
若存在正数项，则可将其提至最前方。

以上优化均不可写入toString()方法内。

结语

面向对象设计与构造不是数据结构与算法，也不是代码精简大赛。

我的意思是，至少在这门课里，我认为作业的完成要求只有一条：用好的设计解决一切问题。