OO_U1 - 数学表达式

Hw1

这本是一个描述本人思路的草稿，后决定还是整理一下，发到公屏交流一下））

要求

读入一个含：

• 加，减
• 乘
• 乘方
• 至多一层括号（建议考虑多层的拓展）
  的 单变量（e.g. 字母x） 表达式。

输出：

• 展开所有括号
• 结果尽可能短

构造

我们可以继续沿用先前的逻辑，不过需要针对乘方进行优化（用一个我看得懂，杂揉了RegEx的写法，严谨定义请参阅参考书）：

- Expr：(+|-){0,1}term | expr(+|-)term
- Term：Term * Factor | (+|-){0,1}Factor
- Factor：**变量** | 常数 | Expr
- 变量：x(^【一个正数，可能有前导0和+】){0,}
- 常数：(+|-){0,1}\d+

为了处理幂函数，我们引入Factor的下一级SubFactor：当前定义下，为^两端的对象，可为数字，变量或表达式。

此时，我们的指数一定为一个正数，这里SubFactor涵盖指数会不会有问题？在Parser标记的过程，不会；但在后面由标记好的Expr，得到多项式的过程中，就有可能出问题了。

多层括号嵌套

看了OOpre.hw7的都知道，那边的实现之所以不能处理多层嵌套，是因为在最低层次中引入了SubExpr；我们只需把SubExpr换成Expr，就可以处理多层括号嵌套了。

发病

这是一个在参考书的定义下不可能出现的情况，但仍然值得考虑：

+-++---+++-009+b

对应regex：

(\+|-){0,1}((\d|\+|-)+)

实际情况中，至多只可能出现三个连续的符号，但考虑一下也好。

继续构造

lexer

将输入tokenize。
分以下几类：

• +
• -
• *
• ^
• (
• )
• 数字：调用parseNum()，分析出数字。此时我们先不考虑符号数的问题。

空字符直接跳过，毕竟在我们的定义中，空格不存在语义；不关心其数量而直接跳过，并无影响。

为什么在parse前要tokenize？这对后续拓展其实是有利的，比如说，变量名字不是一个字符x，而是多个字符时。

符号化简

我们认为，此时各个Term的连接应该都是加号。因此，我们需要想一个处理正负的方法。

我们需要对符号进行简化，得到唯一的正负标识reversed。

这个reversed标记该放到哪一层呢？

此时，我们应在最小单元处，进行加减号的化简；因此，我们决定，在parseSubFactor()过程中进行加减号的吞并，同时使用一标识符，指示SubFactor是否取反。

事实上，我们只需要对Num，Var记录这一取反符号

仔细思考发现，上述思路对于以下样例处理存在问题：

+-5+-x^5

幂函数整体是一个正值。因此，我们处理正负的问题，应该停留在Factor层次。处理连续符号的过程，因此也放在Factor处进行。

为此，我们还需修改Factor类的构成：除SubFactor容器外，还需记录一个boolean reversed.

具体实现为：

• Expr：parse方法需提供reversed，指示默当前正负；直接向下parse，并传递reversed。
• Term：符号可认为只对第一个乘数有影响，故只将该reversed传递到第一个Factor，其余Factor的reversed全设为false；继续向下parse
• Factor：先处理符号。 当前读到+保持reversed不变，读到-对reversed取反。完成处理后，使用处理好的reversed新建Factor对象，再进行下一层的parse（方法同现有的类似，不再赘述）。
• SubFactor：分三类情况，数字，变量和表达式。仿照现有思路处理即可。不过，对于表达式，我们此时调用parseExpr()时，传入的reserved应为false，因为我们已经在其上一级Factor处理好了符号。

这样一来，我们逐层向下传递了各个Factor的正负属性，从而为下文进行多项式转换提供便利。

多项式转换

我们通过Parser.parseExpr()，得到了一个处理（或者说，标记？）后的Expr。

考察最终化简式，可以得知其形式为：
$$\sum a*x^b$$
因此，我们需要构造：

• Mono类：一个单项式
• Poly类：一个多项式，使用容器存储其包含的单项式

同样，我们认为，此时各单项式间连接只有加法。

如何定义Mono？其中包含：

• BigInteger multiplier：a
• String var:x
• BigInteger exp: b

针对纯数字的表达，我们规定：

• 值全部存储在multiplier中
• var此时为空串""，为变量可能为多字符的情况准备
• exp恒为1

在这个思路的指引下，我们引入一个处理器Flattener，将已进行标记的表达式expr“拍扁“，得到一个满足上式的多项式。此时，我们并不需要考虑化简的问题；化简的过程，我们在Poly类内实现一个方法即可。

为何要多一个Flattener? 感觉上，边Parse边获取单项式似乎是可行的，但为了高内聚低耦合，还是把获取单项式的过程独立出来吧。

Flatter中需要实现的方法：

• getPoly()：将表达式转为多项式
• getMono()：逐层得到单项式，返回一个单项式容器；显然，要根据传入的是Expr/Sub/Factor来进行不同的处理

getPoly()调用getMono(Expr)，随后将容器包装为Poly对象。

我们在此仍然采取递归下降的思路，对已标记的Expr进行处理。根据传入对象类别划分：

• Expr：创建一单项式容器monoList；遍历包含的Term，由getMono()得到子容器；此时是加号，简单合并各容器即可。

• Term：遍历Factor，得到各子容器；此时是乘号，调用一个多项式乘法方法，得到存有单项式的一个容器

• Factor：过程略有复杂。
  在当前定义下，必为a^b的形式。若为x^b，直接构建新的Mono，加入将返回的单项式容器；若为<num>^b，则直接进行计算，按照上文中，纯数字下单项式的约定，构建单项式；若为<expr>^b，则调用一个多项式求幂方法，得到一系列单项式，最后加入容器。

  在得到单项式，返回容器之前，还记得Factor的reserved属性吗？此时，若其为true，则需要调用一个取反方法，将各个单项式的系数取反。

好的，现在我们还要做：

• 多项式乘法：多次单项式乘法
• 多项式求幂：多次调用多项式乘法即可
• 取反：将各个单项式的系数取反。
• 单项式乘法：功能不赘述。
  不过，我们的乘数为0，乘后指数为0的情况都需要在此处理。

这三者的实现其实很简单，这里就不再赘述，不过可以提一下多项式求幂：

在定义中，m^0=1，我们怎么实现这个逻辑呢？显然，我们求幂返回的是个单项式容器；故，我们在方法被调用的开始，初始化一个只含单项式：数字1的容器；随后，根据次幂，将其同底数多项式相乘指数次即可。

一番操作后，我们就得到了一个未化简的多项式对象Poly了。

多项式化简

思路很简单：遍历单项式容器，合并同次幂单项式。

需要对单项式为数字（即，var.equals("")）单独开情况处理。不用担心指数为0的情况，上面的单项式乘法里，我们已经处理掉了。

限于篇幅，且实现也不困难，这里就不展开说了。

Hw2

引入了两个新功能：

• 三角函数：sin，cos
• 自定义递推函数

其他的定义可以认为没改。我们逐个分析。

递归函数解析

也可以参考这篇帖子，其思路也很不错，本人思路也有不少与之相近之处

这是本次作业里较为头疼的一点，要怎么办呢？

书接上文，我们在解析表达式时，在Factor下再加了一层SubFactor。一番分析可知，递归函数调用正是属于SubFactor这一层次。那么，我们能不能在parseSubFactor()中添加调用对应的处理规则，使得我们parse函数调用的时候，得到一个完全展开的表达式呢？

是可以的。在此之前，我们需要搓一个**展开递归函数的“求解器”Solver**。

求解器

我们这里的整体思路是：

• Parser解析输入表达式时，读到调用，交给Solver处理；
• Solver通过调用序号，得到调用对应的表达式；此时，我们不要求此处得到的表达式完全展开
• 解析这一表达式；遇到调用，则递归重复上述思路。

我们当然先要知道递归函数定义如何。我的处理是：

• 先把各定义Tokenize为Token串；
• 非递归定义的Token串：存入一个以序号为索引的定义表内
• 递归定义的Token串：单独存储。

至于为什么这么做，这就要看我们的求解过程了；我们此时先不管形参转实参的问题：

• 对传入的调用序号，先查定义表内有没有该序号，有则直接解析表项的Token串，没有则继续：
• 定义表不存在该序号，则获取递归定义的Token串，并将其中不定序号n对应的Token，换成序号对应的数字Token
• 解析这一替换好的Token串副本。随后，就是我们上面的整体思路。

问题来了，我们要怎么解析递归表达式？我们这里的Token串仍然是表达式，复用我们写好的Parser即可，不过需要些许更改：

• 添加SubFactor为调用时的处理方法，并解析出调用的序号与参数(上面已经提到）
• 序号的解析应该支持<num>和<num>-<num>的形式，为递归做准备
• 实现形参替换

形参替换

我们能不能在Parser进行处理的时候，就直接自动把变量解析成实参呢？

答案是有的，我们只需要略微修改Parser，以及parseSubFactor()时，读到变量类型的处理方法：

• Parser：添加属性：符号查找表HashMap<String,Factor>
• parseSubFactor()：碰到变量先查表，如有对应实参，则返回实参的Factor对象，没有则返回变量
• 显然，我们还要把Factor分类到SubFactor里。

在我们解析输入函数时，我们向parse()传入空表；而在解析递归函数时，我们则先把变量建立好对应的查找表，再在调用的parse()中传入递归函数的符号查找表。

至此，我们即可展开递归函数并传递变量，完成原设计中标记表达式的功能。

获取多项式

我们这里先不管三角函数。

Flattener这里本没有什么好说的，但是：参数必须是Factor类型，而我们把Factor类归在了SubFactor类下，故这里也需补充对应获取多项式的逻辑…

事实上，参数完全可以视作Expr类，毕竟参数内容是由你的parse方法得到的，而且递归下降的原理也告诉我们，这么处理没问题；视作表达式来处理还更方便，因为不用把Factor归进SubFactor，维持我们Hw1的处理逻辑就行；但题目这么说就这么做吧

这里我们先在“标记”阶段处理掉了递归函数展开，因而获取多项式的部分不需大改，这算是低耦合的好处吧。

单项式结构的修改

由于三角函数的引入，我们不得不修改单项式的定义！

现定义单项式如下：
$$a*\prod$$
其中：$$unit = <Var|TrigFunc>^n$$
Var代指变量，TrigFunc代指三角函数。

因此，我们只需要一个BigInteger存进乘数，一个ArrayList<Unit>存入后面累乘的幂函数。

在修改了单项式的定义后，是不是需要大规模的重构呢？

先看Flattener：

• 构造方法：我们在构造方法处使用多态，从而兼容先前构造接口
• 多项式求幂/相乘：只涉及ArrayList<Mono>的相关处理，在这一层次不涉及Mono内部操作，维持现状即可，算是万幸
• 单项式相乘：这个没办法，必须重写；

我的重写思路如下：

• 分两步进行：
• 第一步：简单的乘数相乘，幂函数容器合并
• 第二步：合并底数相同的幂函数

第二步中如何比较底数相等，以及如何合并难度不大，留给读者自行探索。

再看负责多项式化简的Poly：

• 属性不用更改，本来就是Mono容器
• 出问题了！合并同类项的mergeMono()要大改！

mergeMono()分两步：

• 比较多项式是否为同类项，是则合并
• 进行三角函数的化简，这个后面再提

三角函数

这才是本次作业最头大的问题，主要在于化简的复杂度实在太高。

TrigFunc与TrigFuncFactor

我们引入这两个新的类。

• TrigFuncFactor在Parser内使用，其内存放三角函数的类型，及参数对应的Factor
• TrigFunc在处理成多项式后使用，其内存放三角函数的类型，及参数对应的多项式

三角函数与函数调用被放在了“变量因子”层次，同之前幂函数在一个层次。因此，我们决定，将与TrigFuncFactor置于SubFactor层次，这对sin()^2情况的处理亦有好处。

需要在Flattener和Parser处编写针对三角函数的规则，这里不再赘述。

化简

我选择复现讨论区内已有方法，化简规则看这个基本就够了。不过这篇帖子里讲的是是单次化简。

考虑这样一个输入：
$$(cos(x)^2-sin(x)^2)^2+sin(2x)^2$$
理想的化简结果是1；显然，单化简一次是不够的！

我们引入这样一个多重化简机制：

• 两个容器：原始单项式集合monoList和结果newMonoList
• 外层套while()，由一个布尔变量proceed指示是否继续重复化简
• 引用一个写回缓存区buffer，实现“化简之后，把结果加回正在遍历的结果列表”的效果
• 判断单项式集合中mono与newMonoList中元素是否可化简：
• 若能，则将合并结果写入缓存，并将此mono从原始集合中移除；
• 若不能，将此mono移动到结果列表中；也就是说，mono无论如何都得删。
• 双层遍历完成后，**若缓存为空，则说明不可化简，proceed设为否；反之，则将缓存内容写回newMonoList**。

示意如下：

boolean proceed = true;
while (proceed) {
	<for mono in monoList> {
		<第一次进行化简时，把第一个mono放入结果列表>
		<for newMono in newMonoList> {
			// do something
		}
	
	}
	if (buffer.isEmpty) { proceed = false; } else {
		newMonoList.addAll(buffer)
	}
}

Hw3

引入非递归自定函数与求导因子。

SubFactor引入上述两个新元素，对应修改Flattener规则

求导规定成dx(<Expr>)；在Flattener.getMono(Factor)中，读到求导因子的Subfactor，则将里面的<Expr>化成多项式，随后逐单项式，运用求导规则，获得新的表达式。

可以造一个单项式求导器。

非递归自定函数，按照现有实现改进即可。考虑到我们写递归函数求解器的写法，我们甚至可以直接复用。

改Solver

复用已有的Solver。

首先要改lexer，把两个自定函数的符号进行分类，分类就继续分到FUNC内；

接下来是Parser部分；我们在处理递归函数的时候，写了这么一个东西：

lexer.forward(); // Skip LCurly  
final int times = parseInvocationTimes();  
lexer.forward(); // Skip RCurly

我们在此次修改时，需要这么做：

• 读取当前Token，看是圆括号还是花括号
• 圆括号->普通函数，花括号->递归函数
• 圆括号默认调用次数为0

随后，目光转向Solver；

在我初始化Solver时，我采用了如下写法，以获取n行的函数定义：

Solver(int n) {  
    int lines = n;  
    while (lines > 0) {  
        String expr = scanner.nextLine();  
        Lexer lexer = new Lexer(expr);  
        classify(lexer);  
        lines--;  
    }  
}

我们初始化一般函数时，n设成1；递归函数，n为3.

其中的classify()方法，是根据输入的定义式，判断递归表达式的类型，从而决定将定义放入递归定义，还是定义表内；

classify() {
	// Skip Name  
	// Skip {  
	Token typeToken = lexer.getCurrentToken();  
	// Skip n  
	// Skip }  
	// Skip (
}

用同样的思路，在普通函数时，让typeToken变成”0”；随后，就可顺利复用Solver。

那么，我们怎么实现多个函数的解析呢？

• 首先，我们需要给Solver添加String name属性，从而记录当前求解器解的是哪一个函数；
• 随后，我们需要构建一个按名称的函数求解器表，将其传给Parser；
• Parser在遇到函数关键字时，查找求解器表，获得求解器，随后求解得到表达式。

这部分就成功解决了，接着看求导。

加求导

首先，我们要在Lexer里面加dx的规则，这就不多说了。

求导因子会出现嵌套，比如：

dx(dx(x^2)+x^3)

我们此时仍然不用担心，递归下降的原理保证其可以被处理；我们只需在getMono(Factor)处正确获取多项式即可。

getMono(Factor)处，读到求导因子，调用一个求导器，获取实际多项式。

求导器

为方便求导的进行，我们决定对一个多项式求导。也就是说，我们需要先将dx(<expr>)中的表达式先转换为多项式，再进行我们求导的过程。

我们需要求导的表达式，符合如下一般形式：
$$expr = \sum{a*\prod{^b}}$$
我们将其分为以下层次，分别求导：

• 多项式：如上
• 单项式：$a*\prod{^b}$
• 幂函数：$^b$
• 底数：$$

这样即可应对链式法则中，幂函数之底数为三角函数的问题。

各层规则如下：

• 多项式：对各单项式求导，合并各次求导所得多项式
• 单项式：实现乘法法则，得到求导后多项式
• 幂函数：
  先假设<base>为一个整体，按照幂函数的求导方法正常进行；随后，将结果与底数求导结果相乘，实现链式法则。这里可能需要对^0，^1等情况做特殊考虑。
• 底数：返回一个多项式
  数字：求导为0；
  变量：求导为1；
  三角函数：sin,cos按各自方式求导（内部表达式视为整体）后，与内部表达式的求导结果相乘，实现链式法则。

不难注意到，我们上面需要用到多项式乘法；调用我们已实现的方法即可。

拓展三角化简

在Hw2中，我没有搓sin的二倍角化简。在本次作业中，由于出现可化简情况的概率大幅增大，我们决定补齐这一化简策略。

$$(cos(x)^2)’=-2cos(x)sin(x)=-sin(2x)$$

为了防止化简后，输出长度不减反增，我们规定其：

• 在其它三角化简后进行。
• 仅在sin,cos指数均为1时进行

还有化简本身的规则：

• 乘数绝对值大于1（因为我们的系数是BigInteger）.

总结

回顾本次作业，我发现自己的最终成果存在以下问题：

• Flattener中，ArrayList<Mono>与Poly类混用；这是因为，Poly类是在我发现多项式化简需求后才引入的；我没有狠下心，将单项式容器全部重构为Poly类，导致Flattener处画风相当混乱；
• 各方法所属的类并未妥善划分；我的多项式/单项式乘法全部放在了Flattener中。虽说获取多项式需要这些方法，但仔细想来仍然不合理：多项式有关计算，应该在多项式类中才对；
• 部分过程未打包为方法，导致可读性下降：最明显的，就是我赶工赶出来的三角函数化简。
• 不敢@Override，导致实现深克隆的过程未被打包为方法，而直接出现在过程中；

日后多加改正。