北航OOU1 HW1 表达式解析

作业实现

预处理

replaceAll()函数
解决空白符与连续正负号

表达式解析（递归下降）

递归下降的特点是下降和递归。
下降实现了功能的独立性。
而递归是由要解析的表达式的结构决定的。

Lexer的作用

核心作用是处理数字，将连续的数字字符变为一个token单位
其他保持不变

提供方法：

当前token是什么 peek()
去下一个token next()

其实就相当于C语言字符串中的

str[i]
i++

只是我们需要的信息没那么多，就不采用先把式子变成token的ArrayList再去解析的方法
而是在解析的时候利用lexer作为移动和识别的工具

parseExpr

Expr是Term的和
通过加减符号实现Term的分割

判加减 (用peek()判内容用next()进入下一token)
parseTerm() addTerm()
循环：
判加减 (用peek()判内容用next()进入下一token)
parseTerm() addTerm()

parseTerm

Term是Factor的积通过乘号实现Factor的分割（其中第一个Factor可有额外正负号）

判加减 (用peek()判内容用next()进入下一token)
parseFactor() addFactor()
循环：
判乘号 (用peek()判内容用next()进入下一token)
parseFactor() addFactor()

parseFactor

Factor约等于解析最底层

分为三类，需要建立接口

常数因子与幂函数因子可以用 A*x^b统一
表达式因子分为(Expr)与(Expr)^n

所以Expr类，Mono类A*x^b和Power类(Expr)^n都需要Factor接口，以在解析完成时返回Factor类型的结果

其中Expr还能下降为A*x^b，(Expr)与(Expr)^n
因此最小单位就是Mono类A*x^b和Power类(Expr)^n

解析方法：

先判一下加减 (用peek()判内容用next()进入下一token)

判到左括号 (用peek()判内容用next()进入下一token)
- parseExpr();
- 把右括号跳过 next()
- 判^ (用peek()判内容用next()进入下一token)
- - 有^ : （若有正号先next()掉）peek()读取指数再next()
- - - 指数是0 ： return Mono类 1*x^0
- - - 否则： return Power类
- - 无^ ：直接return Expr类
判到数字 (用peek()判内容用next()进入下一token)
- Mono类数字*x^0
判到x
- Mono类 1*x^n 无^时n=1特殊处理

关于正负：传参

我在解析过程中将正负号落实到了Mono类与Power类
这样，Factor之间只是乘，Term之间只是加，相对简单

落实的方法: 传参 isNeg 初始参数值，即MainClass调用时是parseExpr(false)
改变的规则：

根据传入参数，在解析方法定义内部变量isNegative，用于传递给下级
遇到负号，isNegative = !isNegative
对于Expr到Term符号的继承，每一项isNegative的初始值都是isNeg
对于Term到Factor符号的继承，只有第一项isNegative的初始值是isNeg，其余初始值为False
特别的，对于Power类型，其Expr由于先被解析，所以正负号已经落实到内部，这时候Power的正负性就应该做出调整：
- 若符号为正，则无影响
- 若符号为负，且指数为奇数，则Power类型应当必须为正数，因为负属性已经在Expr中展现了
- 若符号为负，且指数为偶数，则Expr的负属性不能展现，Power类型需要为负

最终正负就落实到Mono与Power上，这两个类有isNeg属性

表达式求值

最终结果为多项式，而Mono和Power也可变为多项式。
只需先转化为多项式，再实现多项式的加与乘即可。

Poly类

只是有一个TreeMap，里面放着键值对<指数，系数>
TreeMap的优势在于merge()方法和有序
merge方法在加入一个键值对可以实现合并同类项的作用

Mono的toPoly()

先处理Negate(),直接系数取负然后直接new一个Poly，让其TreeMap去put(指数，系数)

Power的toPoly()

需要有Expr的toPoly(),再使用Poly的幂运算，再实施Negate()

Expr,Term,Factor的toPoly()

Expr就是Term的toPoly()的和
Term就是Factor的toPoly()的积
Factor的toPoly()借助接口就是Mono,Expr与Power的toPoly()

Poly的加，乘，幂

加法直接merge进去
乘法双重循环一项项merge进去（需注意只有一个因子时，另一个因子应变为<0,1>）
幂可用快速幂，也可直接循环乘。同样注意上述问题。

当然三种运算最后都应去除系数为0的单项式

结果的输出

由于结果是多项式，输出相对简单。

需要注意：

空Tree要输出0
若存在单项式系数为正，应将其提前并省略正号
指数为0的项只输出数字，指数为1的项只输出x，指数为-1的项只输出-x
中间的正项需额外输出+

评测机实现

DataMaker

使用c程序，同样使用递归下降的方法去生成表达式
printExpr() -> printTerm() -> printFactor() -> …
用rand()随机项数，因子数，正负号，以及因子的种类等等

Check

由于Python库的强大，这里使用了Python的sympy库
检测两个表达式化简结果是否相等，实现了对拍

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28


import sympy

x = sympy.symbols('x')

with open('./outA.txt','r') as fileA:
    e1 = fileA.read().replace("\n","")
    expr1 = e1.replace("^","**")

with open('./outB.txt','r') as fileB:
    e2 = fileB.read().replace("\n","")
    expr2 = e2.replace("^","**")
    
    expr1 = sympy.simplify(expr1, ratio=10)
    expr2 = sympy.simplify(expr2, ratio=10)

if (sympy.simplify(expr1 - expr2) == 0) :
    print ("True\n")
else : 
    print ("False")
    print ("data:")
    with open('./in.txt','r') as filein:
        data = filein.read()
    print (data)
    print ("right:")
    print (e1)
    print ("yours:")
    print (e2)
    print ("\n")

运行脚本

Windows系统的bat脚本和OS学习的Linux脚本异曲同工

主要使用了这些操作

指令	作用
REM	注释
java -jar 名称.jar	运行jar包
名称.exe	运行.exe文件
python 名称.py	运行python程序
< ，>	实现重定向

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


@echo off
for /l %%i in (1,1,100) do (
normaldata.exe > in.txt
java -jar oo_homework_2025_xxxxxxxx_hw_1.jar < in.txt > outA.txt
java -jar 1.jar < in.txt > outB.txt
python check.py
java -jar 2.jar < in.txt > outB.txt
python check.py
java -jar 3.jar < in.txt > outB.txt
python check.py
java -jar 4.jar < in.txt > outB.txt
python check.py
java -jar 5.jar < in.txt > outB.txt
python check.py
java -jar 6.jar < in.txt > outB.txt
python check.py
java -jar 7.jar < in.txt > outB.txt
python check.py
echo -------------------------------------------------------
)
cmd

如何制作jar包

具体流程可自行搜索。

文件->项目结构->工件-> + -> JAR -> …

构建->构建工件