OO第一单元训练（1）

训练栏目

表达式的层次化结构

数据结构中曾经用栈来将表达式转化为后缀式来进行处理。但表达式具有层次化结构，栈解析破坏了层次结构，也不利于其他表达式操作，因此教程中不建议使用。

可以将表达式（只包含加减和乘除）划分为三个层次：

  1. 最底层是表达式基本元素，数字（0~9），称为因子
  2. 中间是用乘除法连接的数字，称为项
  3. 最上层是用加减法连接的项，称为表达式

则表达式的运算优先级和层次的高低有一一对应，自底向上。所以层次结构隐含了运算顺序：处理高层次结构前要先处理低层次结构子对象。

正则表达式法

利用正则表达式来解析的方法。

重点：对每个层次的对象用不同的正则表达式进行描述，如果当前串可以匹配某个部分的正则表达式就用这个层次的对应方法解析（每个部分用一个方法），用工厂模式进行建模。

1
2
3
4
5
6
网络上查到的工厂模式的介绍：
意图：定义一个创建对象的接口，让其子类自己决定实例化哪一个工厂类，工厂模式使其创建过程延迟到子类进行。
主要解决：主要解决接口选择的问题。
何时使用：我们明确地计划不同条件下创建不同实例时。
如何解决：让其子类实现工厂接口，返回的也是一个抽象的产品。
关键代码：创建过程在其子类执行。

教程中的补充例子：例如项的形式为数字 +/- 数字 +/- ...，我们可以编写出对应的正则表达式和对应的解析方法，然后尝试用正则表达式去匹配当前的子串。如果匹配上了，则调用对应的方法解析；否则，尝试另外的匹配模式。

嵌套括号的处理

如果出现嵌套括号，就无法用正则表达式进行解析，这种时候就要采用”递归解析“的方式。

教程举例：有一个解析表达式（无括号）方法叫Expr parseExpr(String)，那么当这个方法解析到括号时，就应该找到与其匹配的括号，然后将括号中间的子串再用这一方法进行解析。在字串解析完成后将完成的表达式当作因子，再按照项的方式处理上一级表达式。

训练1

补全给出程序，读入一个不带括号、运算符只有+和*的表达式并输出后缀表达式，例子如下：

1
2
3
4
输入：
1+2*3+2
输出：
1 2 3 * + 2 +

教程给出的形式化定义：

  1. 表达式 → 表达式 ‘+’ 项 | 项
  2. 项 → 项 ‘*‘ 因子 | 因子
  3. 因子 → 数字因子
  4. 数字因子 → [‘1’|’2’|’3’|’4’|’5’|’6’|’7’|’8’|’9’]{‘0’|’1’|’2’|’3’|’4’|’5’|’6’|’7’|’8’|’9’}

同时给出了一些形式化定义符号的含义：

符号 名称 含义 样例 样例解释
→ 生成符 由前置表达式可以生成后置表达式 A->Ba 由前置表达式 A 可以生成表达式 B 后接小写字母 a 的表达式
‘或’选择符 从由‘或’选择符连接的集合中选择一个 A->a
[ ] ‘0或1’ 选择符 可以从中括号内的表达式中选择0个或1个表达式 A->[B]a 由前置表达式A可以生成Ba或a
{ } ‘0或多’ 选择符 可以从花括号内的表达式中选择0个或1个多个表达式 A->{a|b|c} 由前置表达式 A 可以生成由小写字母 a、b、c 组成的可以为空的字符串 如: ∅ (空串), a, b, c, aa, ab, bc, ca, acb, acbccaabcba 等等

查看给出的代码。首先是Term类（项）：

构建了一个factors容器来装数字因子：private ArrayList<Integer> factors;

同时也有自己的构建函数，写的是这样的：

1
2
3
4
5
6
7
public Term(String s) {
    factors = new ArrayList<>();
    String[] factorStrs = s.split(/* TODO */);
    for (String factorStr : factorStrs) {
        factors.add(Integer.parseInt(factorStr));
    }
}

初始化用到了一个字符串s，同时初始化的时候就创建了上面提到的factors容器。中间我们似乎需要对这个字符串s进行分割：split方法后面的括号要给出指定的分隔符。然后把这些分割后的小字符串放进字符串容器factorStrs中。

后面的for (String factorStr : factorStrs) {}相当于遍历factorStrs中的元素，然后用parseInt方法将字符串变成整数。那么这里应该就是要让项向下转化成因子,就要在乘除处分开。我的填法是：String[] factorStrs = s.split("\\*");（乘号是转义字符，要加\\）

之后的写法如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
@Override
    public String toString() {
        if (factors.size() == 1) {
            return factors.get(0).toString();
        } else {
            StringBuilder sb = new StringBuilder();
            sb.append(factors.get(0));
            sb.append(" ");
            /* TODO */
            sb.append(" ");
            sb.append("*");
            for (int i = 2; i < factors.size(); i++) {
                sb.append(" ");
                sb.append(factors.get(i));
                sb.append(" ");
                sb.append("*");
            }
            return sb.toString();
        }
    }

由于有了@Override，证明这里一定是字符串处理过程，因为同一个方法要对应不同类型的字符串所以写的时候要重载。

针对刚才的factors容器做了一个判断：如果这个容器只含有一个元素，那么证明根本就没有分割，这个项就是一个数字因子，就把这个数字再当作字符串输出（利用toString方法）

如果不是的话，我们就要构建一个新的项字符串。于是新建了一个StringBuilder类（我现在先当成一种比较好用的字符串类好了）的对象sb。首先将第一个分割出的数字因子放在开头，然后加入空格，所以这里要添加的肯定就是第二个分割出的数字因子（由于数字因子不止一个，则第二个肯定存在），写成sb.append(factors.get(1));。后面再加上乘号。

如果再有数字因子的话（即i>2）就还需要在后面再添加数字因子和乘号，这就是for循环里面干的事情。例如2*3*4就要改成2 3 * 4 *，前面的2，3和第一个乘号是必做的，在for外，而后面的4和乘号是不一定需要的，而且可能有循环的，就在for中。

最后利用toString方法把这个StringBuilder类给转换成String类输出。

再看Expr类（表达式）：

同样先构造了一个子串的容器（此处为Term类容器）：private ArrayList<Term> terms = new ArrayList<>();。同时专门给往这个容器里增加元素的命令写了一个方法addTerm：public void addTerm(Term term) {terms.add(term);}

然后在这里就也出现了toString方法，此处肯定针对的是表达式这一层次的方法，因此也有重载：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
@Override
public String toString() {
    if (/* TODO */) {
        return terms.get(0).toString();
    } else {
        StringBuilder sb = new StringBuilder();
        sb.append(terms.get(0));
        sb.append(" ");
        /* TODO */
        sb.append(" ");
        sb.append("+");
        for (int i = 2; i < terms.size(); i++) {
            sb.append(" ");
            sb.append(terms.get(i));
            sb.append(" ");
            sb.append("+");
        }
        return sb.toString();
    }
}

这里的原理和刚才差不多：首先如果terms容器中只有一个元素，证明这个表达是就是一个项，直接套用项的toString方法就可以。因此判断条件应该要写：if (terms.size() == 1) {。

如果不是，则也需要一个StringBuilder类对象sb，这里我认为我们要做的就是把不同的项顺序放入并整合成一个字符串。所以第二个填空处应该是将第二个处理好的项放入字符串中：sb.append(terms.get(1));，其他的处理方法和刚才Term类中的处理方法很类似，将2及之后的项和加号按顺序连接并最终转换成字符串即可。

最后看一下有main函数的MainClass类：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class MainClass {
    private static final String patternTerm = /* TODO */;
    public static final Pattern re = Pattern.compile(patternTerm);

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String inputExpr = scanner.next();

        Matcher matcher = re.matcher(inputExpr);

        Expr expr = new Expr();
        while (matcher.find()) {
            String termStr = matcher.group(0);
            Term term = new Term(termStr);
            expr.addTerm(term);
        }

        System.out.println(expr.toString());
    }
}

我先看一下Main函数中的代码是什么意思：首先用Scanner类和next方法将输入的字符串存入字符串变量inputExpr中，然后创建了一个Matcher类对象matcher，来将inputExpr套用re这一正则表达式。

后面创建了一个Expr类对象expr（表达式类）。因为其为最高级，一定匹配输入，所以直接在Main函数中创建。

如果说满足了re这一正则表达式，会创建一个字符串叫termStr，给它赋值为刚才inputExpr被正则表达式捕获的第一捕获组的内容。同时创建一个新Term类对象term，将termStr作为其初始化所需字符串，并把这个term放入expr对象的Term类容器中。

要注意这里是while (matcher.find()) {}，程序运行中find方法是一直往后走的，并不是说只要一段匹配上了就会死循环，第二次循环会从当前位置往后走去匹配。

因此我认为这里匹配的应该是项的正则表达式，整个程序的运行逻辑就是：输入捕获截断成一个一个项，在项中用toString处理完成就加入唯一的表达式对象中，最后把唯一的表达式对象toString处理了再输出。我写的是：private static final String patternTerm = "(\\d+)((\\*(\\d+))*)";，一个项我认为一定有第一个因子，后面的乘号和因子作为一组可以有零到多组。

训练2

同训练1，补充给出的程序，使其能够读入带有括号且运算符只有+和*的表达式，然后输出后缀表达形式。举例如下：

1
2
3
4
输入：
(1+2)*(3+4)
输出：
1 2 + 3 4 + *

教程同样给出了形式化定义的方式：

  1. 表达式 → 表达式 ‘+’ 项 | 项
  2. 项 → 项 ‘*‘ 因子 | 因子
  3. 因子 → 数字因子 | 表达式因子
  4. 数字因子 → [‘1’|’2’|’3’|’4’|’5’|’6’|’7’|’8’|’9’]{‘0’|’1’|’2’|’3’|’4’|’5’|’6’|’7’|’8’|’9’}
  5. 表达式因子 → ‘(‘ 表达式 ‘)’

在这里我们就要使用递归下降算法了，我们通过形式化定义已经将表达式分成了三层：表达式、项、因子并对应三种对象。针对不同对象用不同解析方式即可。

  1. 数字因子的解析只用看下一个字符是不是数字。
  2. 项的解析要分步：首先看开头一定是一个因子，然后把这段交给因子类；若下一个字符是乘除符号，就读入这个符号并处理，此时符号后肯定也是一个项，再回到第一步；其他情况就证明此项已经结束，退出处理并返回处理好的项。
  3. 表达式和项类似：首先开头一定是项，就调用项的解析；之后也有两个可能，如果是加减符号就读入并处理，把后面的再当成一个表达式处理；如果是其他情况证明解析结束。

这种通过形式化表述建立层次并互相调用的方法，通过方法间简介递归调用可以处理嵌套表达式，即为递归下降算法。现在研究一下给出的代码：

首先看看Factor接口和Number类：

1
2
public interface Factor {
}  //Factor接口
1
2
3
4
5
6
7
8
9
10
11
12
13
import java.math.BigInteger;

public class Number implements Factor {
    private final BigInteger num;

    public Number(BigInteger num) {
        this.num = num;
    }

    public String toString() {
        return this.num.toString();
    }
}  //Number类

我认为这里设定一个Factor接口就是用来统一数字因子和表达式因子的（还没有看其他代码），自然Number类需要接入Factor接口。Number类中包含一个私人的BigInteger变量num，并且在创建这类对象时就要求提供这个变量（见构建函数），同时也给出了处理方法toString，对于数字因子的处理方法自然就是转化成字符串。

再看高一级的项（Term）类代码：

1
2
3
4
5
6
7
8
9
private final HashSet<Factor> factors;

public Term() {
    this.factors = new HashSet<>();
}

public void addFactor(Factor factor) {
    this.factors.add(factor);
}

这是开始的几行代码：首先创建了一个私人的Factor类哈希表叫做factors，来装因子。然后写了构建函数Term()，就是创建出一个空的哈希表来当作factors指代的容器。

然后还写了一个addFactor的方法，就是用来简化将一个新的Factor类变量factor放入factors这一哈希表的过程。

然后就是重写了toString方法（此处省略了@Override这一标识作用的伪代码）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public String toString() {
    Iterator<Factor> iter = factors.iterator();
    StringBuilder sb = new StringBuilder();
    sb.append(iter.next().toString());
    if (iter.hasNext()) {
        sb.append(" ");
        sb.append(iter.next().toString());
        sb.append(" *");
        while (iter.hasNext()) {
            sb.append(" ");
            sb.append(iter.next().toString());
            sb.append(" *");
        }
    }
    return sb.toString();
}

此处Iterator是一个迭代器。它并不是一个集合，而是一种访问集合的方法，可以用来迭代ArrayList和HashSet等集合。就像这里写的Iterator<Factor> iter = factors.iterator();，集合factors想获得迭代器要使用iterator()方法，用这种方法获取了迭代器iter。（迭代器其他的用法我看到了再查）

然后就是和之前一样的用StringBuilder类创建一个对象sb。然后接上一个iter.next().toString()。iter这一迭代器拥有next()方法，可以一个个输出容器中的元素，这些元素都是Factor接口的，输出之后用写过的toString方法来将这些因子转化为字符串输出，连在sb后面。

后面的判断条件是iter.hasNext()，如果容器中还有元素就会是True。如果没有元素，证明这一项就是因子，直接输出；如果有元素证明后面还有要处理的部分：就连上，如果再有更多就用循环完成。最后返回处理完成的字符串。

然后我看了一下，用来处理表达式的Expr类的处理方式和Term类基本相同，就不再重新分析了，代码如下：

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
public class Expr implements Factor {
    private final HashSet<Term> terms;

    public Expr() {
        this.terms = new HashSet<>();
    }

    public void addTerm(Term term) {
        this.terms.add(term);
    }

    public String toString() {
        Iterator<Term> iter = terms.iterator();
        StringBuilder sb = new StringBuilder();
        sb.append(iter.next().toString());
        if (iter.hasNext()) {
            sb.append(" ");
            sb.append(iter.next().toString());
            sb.append(" +");
            while (iter.hasNext()) {
                sb.append(" ");
                sb.append(iter.next().toString());
                sb.append(" +");
            }
        }
        return sb.toString();
    }
}

我认为可能唯一的差别就是接入了Factor接口，也许是表达式加上括号就变成表达式因子的原因，之后分析好了。

然后看一下Lexer（词法分析器）类的写法，开头是对一些私人变量和构建函数的定义：

1
2
3
4
5
6
7
8
private final String input;
private int pos = 0;
private String curToken;

public Lexer(String input) {
    this.input = input;
    this.next();
}

定义了一个输入字符串，同时在构建函数中也要求输入一个字符串储存在输入字符串input中。同时定义了一个整数变量pos并赋初值为0，还定义了一个字符串叫做curToken。

然后是第一个方法getNumber()：

1
2
3
4
5
6
7
8
9
private String getNumber() {
    StringBuilder sb = new StringBuilder();
    while (pos < input.length() && Character.isDigit(input.charAt(pos))) {
        sb.append(/* TODO */);
        ++pos;
    }

    return sb.toString();
}

这里input.length()的值肯定是字符串的长度，而Character.isDigit(input.charAt(pos))中isDigit方法在括号内字符是数字时返回true，否则false；而charAt方法返回指定索引处的字符（范围自然从0到length()-1）。所以这个循环应该是一位一位检测这个Input字符串某一段是不是都是数字，如果pos位是数字就直接放进sb内，这样就将这一段数字变成字符串并输出了。所以我觉得这里应该写sb.append(input.charAt(pos));。

第二个方法next()：

1
2
3
4
5
6
7
8
9
10
11
12
13
public void next() {
    if (pos == input.length()) {
        return;
    }

    char c = input.charAt(pos);
    if (Character.isDigit(c)) {
        curToken = /* TODO */;
    } else if (/* TODO */) {
        pos += 1;
        curToken = String.valueOf(c);
    }
}

第一个if段指的是如果分析位置pos达到了input字符串的最后以后，就证明不需要后续分析，直接return即可。

在其他情况下，这个方法是用来提取下一个语法单元，例如数和符号的。如果检测到第一个字符是数字（即Character.isDigit(c)），则用getNumber()方法将这个数字放进curToken中。所以第一个todo位置我认为应该填curToken = getNumber();；第二个todo位置应该是用来判断检测到符号的情况的，如果检测到符号就把这个符号单独存入curToken输出。所以第二个位置我认为是else if (c == '(' || c == ')' || c == '+' || c == '*')，判断符号即可。

最后就是一个peek方法public String peek() {return this.curToken;}，将这个字符串curToken输出。

然后看一下Parser类：

1
2
3
4
5
private final Lexer lexer;

public Parser(Lexer lexer) {
    this.lexer = lexer;
}

开始就是定义了一个Lexer类变量lexer并定义了一个构建函数Parser()，这个构建函数需要lexer，所以证明构建Parser类对象时需要输入一个Lexer类对象。

然后定义了对于表达式、项和因子的三个处理方法：parseExpr()、parseTerm()、parseFactor()。首先考虑处理表达式：

1
2
3
4
5
6
7
8
9
10
public Expr parseExpr() {
    Expr expr = new Expr();
    expr.addTerm(parseTerm());

    while (/* TODO */) {
        lexer.next();
        expr.addTerm(parseTerm());
    }
    return expr;
}

对于一个表达式的处理，首先建立一个表达式类expr，然后由于表达式只可能是项或者项相加的形式，则一定能找到第一个项，就用parseTerm()找到第一个项然后加入expr的项容器。

后面就是判断还有没有后续项：方法就是看项后面是结束了还是有加号。所以判断加号即可，这里我认为该写：while (lexer.peek().equals("+"))

然后考虑处理项：

1
2
3
4
5
6
7
8
9
10
public Term parseTerm() {
    Term term = new Term();
    term.addFactor(parseFactor());

    while (lexer.peek().equals("*")) {
        lexer.next();
            /* TODO */
    }
    return term;
}

这里和表达式的方法类似，也是项只有两种可能：因子或者因子相乘，按照上面进行类比，应该将乘号后的新因子放入此项的因子容器中。则应该写：term.addFactor(parseFactor());，利用parseFactor()方法处理因子后放入项的因子容器中。

最后考虑处理因子：

1
2
3
4
5
6
7
8
9
10
11
12
public Factor parseFactor() {
    if (lexer.peek().equals("(")) {
        lexer.next();
        Factor expr = parseExpr();
        /* TODO */
        return expr;
    } else {
        /* TODO */
        lexer.next();
        return new Number(num);
    }
}

因子也有两种可能性：表达式因子和数字因子。如果是表达式因子就是括号括起表达式的方式，则需要脱去括号再进行内部的表达式处理。在处理完成之后我们自然需要忽略右括号，则在第一个空处填入lexer.next();跳过即可。

如果没有括号证明是数字因子，则只需要将这个数字输出，就要将lexer中获取的数字字符串改成BigInteger型，由于Biginteger型构造用的就是字符串，就直接填入：BigInteger num = new BigInteger(lexer.peek());即可。

最后看一下MainClass类中的主函数：

1
2
3
4
5
6
7
8
9
10
11
12
public class MainClass {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String input = scanner.next();

        Lexer lexer = new Lexer(input);
        Parser parser = new Parser(lexer);

        Expr expr = parser.parseExpr();
        System.out.println(expr);
    }
}

首先用scanner将输入存入input字符串，然后用这个输入字符串新建一个lexer对象用来分析，再用这个lexer中给出的分析方法来构建一个parser。由于给出的字符串一定是一个表达式，就新建一个表达式类对象expr，然后将这个parser对象先用parseExpr()方法进行分析，程序就会自动递归下降分析完毕。最后将这个处理完的表达式打印。

要注意println()这个方法在打印某一个类时会自动调用其toString()方法，因此就可以将处理完的表达式进行输出。

（注意本题由于使用了hashset，因此输出的结果可能顺序有所区别，但是优先级不会出现问题）