Java 面向对象 BUAA

「OO」 01

表达式的展开

OO lesson 01

Posted by Leo on March 7, 2022

题面大意

将一个表达式串进行展开，其中表达式串规定了+，-，*，**（乘方）几种运算符，并且允许有括号，可以有单变量x，但不会有括号嵌套，即不会出现(1+(2+3))的情况。同时严格规定如下：

  • 表达式 $\rightarrow$ 空白项 [加减 空白项] 项 空白项 | 表达式 加减 空白项 项 空白项
  • 项 $\rightarrow$ [加减 空白项] 因子 | 项 空白项 * 空白项 因子
  • 因子 $\rightarrow$ 变量因子 | 常数因子 | 表达式因子
  • 变量因子 $\rightarrow$ 幂函数
  • 常数因子 $\rightarrow$ 带符号的整数
  • 表达式因子 $\rightarrow$ ‘(‘ 表达式 ‘)’ [空白项 指数]
  • 幂函数 $\rightarrow$ ‘x’ [空白项 指数]
  • 指数 $\rightarrow$ ‘**’ 空白项 带符号的整数
  • 带符号的整数 $\rightarrow$ [加减] 允许前导零的整数
  • 允许前导零的整数 $\rightarrow$ (0|1|2|…|9){0|1|2|…|9}
  • 空白项 $\rightarrow$ {空白字符}
  • 空白字符 $\rightarrow$ （空格） | \t
  • 加减 $\rightarrow$ ‘+’ | ‘-‘

其中

  • {} 表示允许存在 0 个、1 个或多个。
  • [] 表示允许存在 0 个或 1 个。
  • () 内的运算拥有更高优先级，类似数学中的括号。
  • | 表示在多个之中选择一个。
  • 上述表述中使用单引号包裹的串表示字符串字面量，如 ‘(‘ 表示字符 (。

需要着重理解的是：表达式与项中加减的真正含义在于，对于每个表达式的第一项前可以有一个正负号，而对于每个项的第一个因子前也可以有正负号，所以不考虑括号的前提下，一个常数前最多三个正负号（常数因子也可以有一个符号位），变量前最多2个正负号，指数最终结果与过程中不会超过8

我们需要将表达式展开，化成不带括号的形式（和不合并同同类项随意，合并了分高）

解题思路

对于我来说，大体上是将这个任务分成解析字符串，和运算字符串两步，其中解析字符串要达到如下效果

</td>
# 输入 解析后输入 输出(省略标签) 说明
1 1 1
f1 1		 1 根据表达式定义可得。
2 x 1
f1 x		 x 根据表达式定义可得。
3 x+2*x 2
f1 mul 2 x
f2 add x f1		 x+2*x 未合并同类项，但表达式依然等价。
4 x+2*x 2
f1 mul 2 x
f2 add x f1		 3*x 在表达式等价的基础上合并同类项。
5 -3*(x) 3
f1 x
f2 mul 3 f1
f3 neg f2 		-3*x 拆括号后得到符合输出格式的表达式。
6 -3*(x-1) 3
f1 sub x 1
f2 mul f1 3
f3 neg f2 		-3*x--3*1 拆括号后得到符合输出格式的表达式。
7 (x-1)**2 2
f1 sub x 1
f2 pow f1 2		 x**2-2*x+1 拆括号后得到符合输出格式的表达式。
8 (x+2*x+1)**0 3
f1 mul 2 x
f2 add f1 x 1
f3 pow f2 0		 1 0 次幂的值为 1。
9 (x+1)**3+1 3
f1 add x 1
f2 pow f1 3
f3 add f2 1		 x**3+3*x**2+3*x+2 拆括号后得到符合输出格式的表达式。
10 (x*x*3*x)**2*x 5
f1 mul x x
f2 mul f1 3
f3 mul f2 x
f4 pow f3 2
f5 mul f4 x 		x*x*3*x*x*x*3*x*x 拆括号后得到符合输出格式的表达式。
11 (x+1)*(x+2) 3
f1 add x 1
f2 add x 2
f3 mul f1 f2
 x**2+3*x+2 把两个不嵌套的括号展开得到结果。
12 x*(x-(x+1)) 3
f1 add x 1
f2 sub x f1
f3 mul x f2
Wrong Format!（无需输出） 嵌套括号不会出现在本次作业中。
13 (x+y)*x 2
f1 add x y
f2 mul f1 x
 Wrong Format!（无需输出） 多变量表达式不会出现在本次作业中。

解析字符串

解析可以分成表达式拆分，得到后缀表达式和格式转化处理这几步

表达式拆分

（本来以为这是最简单的部分，实际上不是）

这一步需要将一整串的表达式的有用信息一个个抠下来，并作一些小处理，小处理主要是辨别每一个正负号，本题中复杂的就是正负号的辨别，有些正负号意味着加减法，有些是因子前面的正负号，有些是项前面的正负号，每个这样的正负号优先级是不同的，这在处理成后缀表达式并得到最终结果时有很大的影响。（我是用栈来处理后缀的，符号的优先级对出栈顺序有很大影响，从而影响后缀表达式）

我的处理方法是将表达式开头（即第一个项前面可添加的$\pm$）标记为+++ or —，对于项前面的$\pm$（即第一个因子前可添加的$\pm$）标记为++ 或–，并为其表明新的优先级。对于非加减法的$\pm$，按照项开头、因子开头、带符号整数的顺序依次判断，例如+-1，会理解为+(-(1))，此时的整数因子为1. 转化为+++ – 1，同理就算表达式开头为-1, 也是理解为— 1， 而非-1 （感觉理解为-1应该也可以处理，但我为了对拍方便，和官方提供的转换程序一致就这么处理了）

而因为只有表达式的开头会有多一个符号，因此在每个表达式的开头，以及扫到 (时进行一个检测

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

public int dealWithHead(int start) {
        int pos = start;
        int cnt = 3;
        StringBuilder sb = new StringBuilder();
        while ((expr.charAt(pos) == '+' || expr.charAt(pos) == '-') && (pos - start) < 2) {
            sb.delete(0, sb.length());
            //构造+++,---
            for (int i = 0; i < cnt; ++i) {
                sb.append(Character.toString(expr.charAt(pos)));
            }
            ++pos;
            --cnt;
            this.operators.add(sb.toString());
        }
        return pos;
    }

在表达式中遇到+-号时，仍然需要判断其性质，若其前一位为数字或 )则表示其含义为加减，而后需要判断其若还有+-号，则为第一项因子前面的正负号，或者通过其前面是否有*判断其是项的第一个因子，从而判断$\pm$的性质

1
2
3
4
5
6
7
8
9
10
11
12
13
14

if ((expr.charAt(pos) == '+') || (expr.charAt(pos) == '-')) {
    if (!preDigit(pos - 1)) {
        if (sufDigit(pos + 1) && isTerm(pos)) {
            start = pos;
            pos = splitNum(pos);
            String part = expr.substring(start, pos);
            this.operators.add(part);
            pos--;
        } else {
            this.operators.add(expr.charAt(pos) + Character.toString(expr.charAt(pos)));
        }
    } else {
        this.operators.add(Character.toString(expr.charAt(pos)));
    }

其余就按照符号一个个拆出来就好了

为了避免多余空格的影响，可以在获得表达式串的时候通过 split()把空白符剔除，再用StringBuilder拼接在一起

后缀表达式的获取

使用栈的方法处理后缀表达式，具体为如果遇到常数和x，就无条件出栈，放入后缀表达式的字符串中，遇到 (就无条件入栈，遇到 )就将栈里面的符号依次出栈，直到 (出栈，其他符号，如果栈顶不是 (或栈顶符号的优先级大于等于它那么就入栈，直到满足栈顶是 (或优先级低于它，

1
2
3
4
5
6
7
8
9
10
11

private void moveToStack(String i) {
    while (!stackSuf.empty()) {
        if (PRIORITY.get(stackSuf.peek()) >= PRIORITY.get(i)) {
            sufExpr.add(stackSuf.pop());
        } else {
            break;
        }
    }
    stackSuf.push(i);
}
//我将(的优先级设置为最低，因此不用优先判断

当遍历结束后，栈不为空，则依次出栈

1
2
3

while (!stackSuf.empty()) {
    sufExpr.add(stackSuf.pop());
}

而对于优先级的判断，我是先打了一个表来判断。而对于上一个拆分得到的+++ 或者++，可以得到其优先级低于*，** ，高于+-（毕竟作用于项或者因子），其中++的优先级高于+++

1
2
3
4
5
6
7
8
9

PRIORITY.put("**", 5);
PRIORITY.put("*", 4);
PRIORITY.put("++", 3);
PRIORITY.put("--", 3);
PRIORITY.put("+++", 2);
PRIORITY.put("---", 2);
PRIORITY.put("+", 1);
PRIORITY.put("-", 1);
PRIORITY.put("(", 0);

计算并转换

得到后缀表达式之后，事情变得简单了不少，对于后缀表达式来说，数字无条件入栈，遇到+，-，*，**就将栈顶的头两个元素A，B（B为栈顶）弹栈，并执行运算， A op B，得到的结果入栈，这边就是Id，如果是++，+++，–，—就将栈顶元素A弹出，得到op A后入栈

字符串运算

得到解析后的形式后，正常运算就好，可以设置一个HashMap存指数和系数的关系，设置一个HashMap存Id与多项式的关系，对于加减正常运算就好了，并判断下是否存在可合并的项。

1
2
3
4
5
6
7
8
9
10
11

public void setFeatures(Integer exp, BigInteger coefficient) {
    if (features.get(exp) == null) {
        features.put(exp, coefficient);
        // if the exp is new, then add directly
    } else {
        BigInteger value = features.get(exp);
        value = value.add(coefficient);
        features.put(exp, value);
        // else merge the term with the same idx
    }
}

对于乘除，就系数相乘，指数相加剧刻，遍历HashMap可以从遍历其 keySet(),然后再找其对应的value

1
2
3
4
5

for (Map.Entry < Integer, BigInteger > i: featureFac.entrySet()) {
    for (Map.Entry < Integer, BigInteger > j: featureAim.entrySet()) {
        polyNew.setFeatures(i.getKey() + j.getKey(), i.getValue().multiply(j.getValue()));
    }
}

对于乘方，也是类似的操作

在计算完之后，为了让式子尽量短（性能分），可以再做些比如删去系数为0的项，将正系数先输出，将x**2换成 x*x等。注意一点就是HashMap遍历删除时，尽量不要用remove，会导致iterator 的迭代出错

1
2
3
4

private HashMap < Integer,BigInteger > clearZero(HashMap < Integer, BigInteger > map) {
    map.entrySet().removeIf(item - >item.getValue().equals(BigInteger.ZERO));
    return map;
}
CATALOG
    ▲ TOP