OO_U1 - 数学表达式

Hw1

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

要求

读入一个含:

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

输出:

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

构造

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

1
2
3
4
5
- 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,就可以处理多层括号嵌套了。

发病

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

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

对应regex:

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

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

继续构造

lexer

将输入tokenize。
分以下几类:

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

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

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

符号化简

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

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

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

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

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

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

1
+-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

引入了两个新功能:

  • 三角函数:sincos
  • 自定义递推函数

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

递归函数解析

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

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

书接上文,我们在解析表达式时,在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()分两步:

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

三角函数

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

TrigFuncTrigFuncFactor

我们引入这两个新的类。

  • 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,实现“化简之后,把结果加回正在遍历的结果列表”的效果
  • 判断单项式集合中mononewMonoList中元素是否可化简:
  • 若能,则将合并结果写入缓存,并将此mono从原始集合中移除
  • 若不能,将此mono移动到结果列表中;也就是说,mono无论如何都得删。
  • 双层遍历完成后,**若缓存为空,则说明不可化简,proceed设为否;反之,则将缓存内容写回newMonoList**。

示意如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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部分;我们在处理递归函数的时候,写了这么一个东西:

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

我们在此次修改时,需要这么做:

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

随后,目光转向Solver;

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

1
2
3
4
5
6
7
8
9
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()方法,是根据输入的定义式,判断递归表达式的类型,从而决定将定义放入递归定义,还是定义表内;

1
2
3
4
5
6
7
8
classify() {
// Skip Name
// Skip {
Token typeToken = lexer.getCurrentToken();
// Skip n
// Skip }
// Skip (
}

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

那么,我们怎么实现多个函数的解析呢?

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

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

加求导

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

求导因子会出现嵌套,比如:

1
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,导致实现深克隆的过程未被打包为方法,而直接出现在过程中;

日后多加改正。

作者

LajiPZ

发布于

2025-02-28

更新于

2025-03-12

许可协议

评论