BUAA-OO 第一单元第一次作业

[toc]

第一次作业主要是关于单变量多项式的展开，这次我们需要展开的表达式中项只有三种——幂函数，常数因子和表达式因子。我们的输出不能有括号，并且还要尽可能的简单。

思路概述

  1. 我们首先通过标准输入获得一个符合规范的表达式，并将其以String的类型传入lexer进行词法解析，获得一系列词块（token）。
  2. 然后我们利用递归下降的方法将token组合起来，自底向上形成一个个符合规范的factor，term，expression。
  3. 通过建立多项式类（Poly），单项式类（Mono）和实现它们的加，减，乘，幂运算方法来展开表达式。
  4. 最后还需要对输出结果做一定的化简。

代码UML类图

OO_hw1

8087137ad5f3d2875a759e8c414231c

词法解析

​ 词法解析中用到的lexer类沿用了OOpre_hw7中的设计思路，它具有如下属性：

1
2
3
4
public class Lexer {
    private ArrayList<Token> tokens = new ArrayList<>();
    private int index = 0;
}

​ 对于每个lexer对象，它维护一个词块构成的列表tokens和一个指向当前词块下标的索引index。

​ lexer的构造方法接受一个字符串input（来自标准输入），跳过空白符并将分割好的词块存入tokens列表中。

1
2
3
public Lexer(String input) {
    // 具体实现与OOpre_hw7很类似
}

​ lexer类还要实现如下方法：

1
2
3
4
public Token getCurToken() {}        // 返回当前token
public Token getLastToken() {}       // 返回上一token
public void nextToken() {}           // 索引自增
public boolean isEnd() {}            // 判断是否读完了tokens

语法解析（递归下降）

​ 为了理解递归下降的最终目标，我们首先介绍表达式类（Expr），项类（Term），因子接口（Factor）。

1
2
3
4
public class Expr {
    private final ArrayList<Term> terms = new ArrayList<>();   // 对每个表达式维护一个项构成的列表
    private final ArrayList<Token> signs = new ArrayList<>();  // 对每个表达式维护一个项的符号的列表
}
1
2
3
4
public class Term {
    private int sign;  // 项的整体符号
    private final ArrayList<Factor> factors = new ArrayList<>();  // 项的因子构成的列表
}
1
2
3
public class Var implements Factor {}         // 幂函数因子
public class Num implements Factor {}         // 常数因子
public class ExprFactor implements Factor {}  // 表达式因子

​ 我们进行语法解析的最终目的就是要将每个项的所有因子都放入它的factors列表，将每个表达式的所有项都放入它的terms列表，同时维护好符号关系。

​ 递归下降通过Parser类实现Parser类具有如下属性和构造方法：

1
2
3
4
5
6
Public class Parser {
    private final Lexer lexer;
    public Parser(Lexer lexer) {
        this.lexer = lexer;
    }
}

​ 同时为了解析表达式，项和因子，Parser类还要实现如下方法：

1
2
3
4
5
public Expr parseExpr() {}      // 解析表达式，返回表达式类
public Term parseTerm() {}      // 解析项，返回项类
public Factor parseFactor() {}  // 解析因子，返回因子类
public Num parseNum() {}        // 解析常数，返回常数类
public Var parseVar() {}        // 解析幂函数，返回幂函数类

​ 这里我们以parseExpr方法为例具体介绍parser方法的实现

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
public Expr parseExpr() {
        Expr expr = new Expr();
        Token tokenAdd = new Token(Token.Type.ADD,"+");
        Token tokenSub = new Token(Token.Type.SUB,"-");
    
        // 首先添加第一项的符号
        if (lexer.getCurToken().getType() == Token.Type.SUB) {
            // 表达式第一项为-号
            expr.addSign(tokenSub);
            lexer.nextToken();
        } else if (lexer.getCurToken().getType() == Token.Type.ADD) {
            // 表达式第一项为+号
            expr.addSign(tokenAdd);
            lexer.nextToken();
        } else {
            // 表达式第一项无符号
            expr.addSign(tokenAdd);
        }
    
        // 开始递归解析表达式
        expr.addTerm(parseTerm());
    
    	// 如果还有第二项，第三项...
        while (!lexer.isEnd() && ((lexer.getCurToken().getType() == Token.Type.ADD)
                || (lexer.getCurToken().getType() == Token.Type.SUB))) {
            // 词汇未结束且当前词汇为+或-
            if (lexer.getLastToken().getType() == Token.Type.ADD ||
                lexer.getLastToken().getType() == Token.Type.SUB) { // 如果上一项是加减号
                expr.addTerm(parseTerm());
            } else if (lexer.getCurToken().getType() == Token.Type.ADD) { // 当前符号为+
                lexer.nextToken();
                expr.addSign(tokenAdd);
                expr.addTerm(parseTerm());
            } else if (lexer.getCurToken().getType() == Token.Type.SUB) { // 当前符号为-
                lexer.nextToken();
                expr.addSign(tokenSub);
                expr.addTerm(parseTerm());
            }
        }
        // 结束表达式的递归解析
        return expr;
    }

​ 这样，我们就得到了一个表达式对象，它的terms列表中维护了它所有的项，signs列表中维护了这些项的符号。

表达式展开

​ 分析可知，本次表达式展开的最终结果是一个多项式形式：

​ 多项式由一些列单项式构成，每个单项式都是$a_ix^i$的形式。因此我们构造多项式类和单项式类：

1
2
3
4
5
6
7
public class Poly {
    private ArrayList<Mono> monoList = new ArrayList<>();
	public Poly addPoly(Poly B) {...}   // A+B
   	public Poly subPoly(Poly B) {...}   // A-B
	public Poly mulPoly(Poly B) {...}   // A*B
	public Poly powPoly(int exp) {...}  // A^exp
}
1
2
3
4
5
6
public class Mono {
    private BigInteger coe;  // 单项式的系数
    private BigInteger exp;  // 单项式的指数
    public Poly monMulPol(Poly polyB) {...} // 单项式乘多项式
    public Mono monMulMon(Mono polyB) {...} // 单项式乘单项式
}

​ 其中多项式类维护一个单项式列表来管理构成该多项式的所有单项式。同时多项式类还实现了加，减，乘，乘方计算的方法。单项式类实现了单项式乘多项式和单项式乘单项式的方法。此过程应当注意深浅拷贝的区别。

​ 这样之后，我们就可以在Expr、Term、Factor等类中都写一个toPoly()方法，将类中的内容转化为多项式。然后从factor.toPoly()一步步向上转化，那么最终可以通过expr.toPoly()来获得结果。这里以expr2poly为示例：

1
2
3
4
5
6
7
8
9
10
11
12
/*Expr.java*/
Poly expr2poly() {
        Poly ret = new Poly();
        for (int i = 0; i < this.terms.size(); i++) {
            if (this.signs.get(i).getType() == Token.Type.ADD) {
                ret = ret.addPoly(this.terms.get(i).term2poly());      
            } else if (this.signs.get(i).getType() == Token.Type.SUB) {
                ret = ret.subPoly(this.terms.get(i).term2poly());
            }
        }
        return ret;
    }

化简

化简主要分为两部分：合并同类项和输出化简。

  1. 合并同类项：

    在Poly类中通过循环遍历实现merge方法即可，同时删除系数为0的项。此过程应当注意循环完再删除mono。

    1
    public Poly merge() {}  // 合并同类项

  2. 输出化简：

    | | 指数为1 | 指数为0 | 指数既不是1，也不是0 |
    | ——————————- | ————- | ———- | —————————— |
    | 系数为1 | x | 1 | x ^ exp |
    | 系数为-1 | - x | - 1 | - x ^ exp |
    | 系数既不是1，也不是-1 | coe x | coe | coe x ^ exp |

    最后提一个细节，输出首项为负时可以将其与一个正项（如果有）调换位置，进而少输出一个符号。