LeetCode770之基本计算器IV(相关话题：波兰表达式,多项式运算)

题目描述

给定一个表达式如 expression = "e + 8 - a + 5" 和一个求值映射，如 {"e": 1}（给定的形式为 evalvars = ["e"] 和 evalints = [1]），返回表示简化表达式的标记列表，例如 ["-1*a","14"]

表达式交替使用块和符号，每个块和符号之间有一个空格。

块要么是括号中的表达式，要么是变量，要么是非负整数。

变量是一个由小写字母组成的字符串（不包括数字）。请注意，变量可以是多个字母，并注意变量从不具有像 "2x" 或 "-x" 这样的前导系数或一元运算符 。

表达式按通常顺序进行求值：先是括号，然后求乘法，再计算加法和减法。

例如，expression = "1 + 2 * 3" 的答案是 ["7"]。

输出格式如下：

对于系数非零的每个自变量项，我们按字典排序的顺序将自变量写在一个项中。

例如，我们永远不会写像 “b*a*c” 这样的项，只写 “a*b*c”。

项的次数等于被乘的自变量的数目，并计算重复项。我们先写出答案的最大次数项，用字典顺序打破关系，此时忽略词的前导系数。

例如，"a*a*b*c" 的次数为 4。

项的前导系数直接放在左边，用星号将它与变量分隔开(如果存在的话)。前导系数 1 仍然要打印出来。

格式良好的一个示例答案是 ["-2*a*a*a", "3*a*a*b", "3*b*b", "4*a", "5*c", "-6"] 。

系数为 0 的项（包括常数项）不包括在内。

例如，“0” 的表达式输出为 [] 。

注意：你可以假设给定的表达式均有效。所有中间结果都在区间 [-231, 231 - 1] 内。

示例 1：

输入：expression = "e + 8 - a + 5", evalvars = ["e"], evalints = [1]

输出：["-1*a","14"]

示例 2：

输入：expression = "e - 8 + temperature - pressure",

evalvars = ["e", "temperature"], evalints = [1, 12]

输出：["-1*pressure","5"]

示例 3：

输入：expression = "(e + 8) * (e - 8)", evalvars = [], evalints = []

输出：["1*e*e","-64"]

提示：

1 <= expression.length <= 250

expression 由小写英文字母，数字 '+', '-', '*', '(', ')', ' ' 组成

expression 不包含任何前空格或后空格

expression 中的所有符号都用一个空格隔开

0 <= evalvars.length <= 100

1 <= evalvars[i].length <= 20

evalvars[i] 由小写英文字母组成

evalints.length == evalvars.length

-100 <= evalints[i] <= 100

知识铺垫

看这篇文章之前，我们先要明确一些概念。

1.前缀表达式又称波兰式，前缀表达式的运算符位于操作数之前。比如:​

​- × + 3 4 5 6​

​​ 2.中缀表达式就是常见的运算表达式，如​

​(3+4)×5-6​

​ 3.后缀表达式又称逆波兰表达式,与前缀表达式相似，只是运算符位于操作数之后,比如:3 4 + 5 × 6 -

人类最熟悉的一种表达式1+2，(1+2)3，3+42+4等都是中缀表示法。对于人们来说，也是最直观的一种求值方式，先算括号里的，然后算乘除，最后算加减，但是，计算机处理中缀表达式却并不方便。

然后我们还需明确一些概念，下面通过我们最熟悉的中缀表达式画出一棵语法树来直观认识一下前后缀表达式的生成。以​

​A+B*(C-D)-E*F​

​为例：

 中缀表达式得名于它是由相应的语法树的中序遍历的结果得到的。上面的二叉树中序遍历的结果就是​

​A+B*(C-D)-E*F​

​。

前缀表达式是由相应的语法树的前序遍历的结果得到的。上图的前缀表达式为​

​- + A * B - C D * E F​

​

后缀表达式又叫做逆波兰式。它是由相应的语法树的后序遍历的结果得到的。上图的后缀表达式为：​

​A B C D - * + E F * -​

​

下面我们关注两个点：

1.如何根据一个逆波兰表达式求出运算结果？

2.如果将一个中缀表达式转换成后缀表达式（逆波兰表达式）

解题思路

在这道题目中，我们需要使用两个栈：主栈和操作符栈。我们线性扫描 expression，并对遇到的变量、常量、操作符进行入栈或者其他的操作。

对于主栈，我们可以：

将变量或常量压入栈中；

将栈顶两个元素弹出，并进行某种运算（加、减、乘）后，将结果压入栈中。

对于操作符栈，我们可以：

将栈顶元素弹出；

将操作符压入栈中。

注意，仅当操作符栈为空，或者栈顶元素的优先级低于想要入栈的元素时，才可以进行压栈操作。否则，我们需要将栈顶元素弹出，直到满足压栈条件为止。操作符的优先级如下：( < ) < + = - < *。

还需要注意的是：

（1） ( 无条件入栈的，以保证括号的优先级最高。

（2）遇到 ) 时，我们将栈顶元素弹出，直到弹出 ( 为止，并且 ) 本身不进入栈中。

举例：

例如，我们想要计算 ((5 - 12) * (12 - 7) + (7 - 5)) * (5 - 12)。为了方便描述，我们使用 | 当作光标，其左侧为已经扫过的字符串，其右侧为未扫描字符串。其次，规定下面的描述中，左侧为栈顶。最后，我们在下列描述中跳过了空格。

|((5 - 12) * (12 - 7) + (7 - 5)) * (5 - 12)

主栈：

操作符栈：

解释：开始之前。

(|(5 - 12) * (12 - 7) + (7 - 5)) * (5 - 12)

主栈：

操作符栈：(

解释：栈空，操作符入栈。（或者解释为 ( 无条件入栈。）

((|5 - 12) * (12 - 7) + (7 - 5)) * (5 - 12)

主栈：

操作符栈：(，(

解释：( 无条件入栈。

((5| - 12) * (12 - 7) + (7 - 5)) * (5 - 12)

主栈：5

操作符栈：(，(

解释：遇到常量，将其入栈。

((5 -| 12) * (12 - 7) + (7 - 5)) * (5 - 12)

主栈：5

操作符栈：(，(，-

解释：( 的优先级比 - 低，因此 - 入栈。

((5 - 12|) * (12 - 7) + (7 - 5)) * (5 - 12)

主栈：5，12

操作符栈：(，(，-

解释：遇到常量，将其入栈。

((5 - 12)| * (12 - 7) + (7 - 5)) * (5 - 12)

主栈：-7

操作符栈：(

解释：遇到了 )，弹出操作符栈栈顶元素。发现弹出的操作符为 -，因此我们将主栈栈顶两元素取出相减，将结果压回主栈。继续弹出操作符栈顶元素，发现是 (，结束。

((5 - 12) *| (12 - 7) + (7 - 5)) * (5 - 12)

主栈：-7

操作符栈：(，*

解释：( 的优先级比 * 低，因此 * 入栈。

((5 - 12) * (|12 - 7) + (7 - 5)) * (5 - 12)

主栈：-7

操作符栈：(，*，(

解释：( 无条件入栈。

((5 - 12) * (12| - 7) + (7 - 5)) * (5 - 12)

主栈：-7，12

操作符栈：(，*，(

解释：遇到常量，将其入栈。

((5 - 12) * (12 -| 7) + (7 - 5)) * (5 - 12)

主栈：-7，12

操作符栈：(，*，(，-

解释：( 的优先级比 - 低，因此 - 入栈。

((5 - 12) * (12 - 7|) + (7 - 5)) * (5 - 12)

主栈：-7，12，7

操作符栈：(，*，(，-

解释：遇到常量，将其入栈。

((5 - 12) * (12 - 7)| + (7 - 5)) * (5 - 12)

主栈：-7，5

操作符栈：(，*

解释：遇到了 )，弹出操作符栈栈顶元素。发现弹出的操作符为 -，因此我们将主栈栈顶两元素取出相减，将结果压回主栈。继续弹出操作符栈顶元素，发现是 (，结束。

((5 - 12) * (12 - 7) +| (7 - 5)) * (5 - 12)

主栈：-35

操作符栈：(，+

解释：由于 * 的优先级不低于 +，因此 + 不能入栈，需要先将 * 弹出。弹出后，取出主栈栈顶两个元素相乘，将结果压回主栈。继续观察操作符栈栈顶元素， ( 的优先级低于 +，可以入栈。

((5 - 12) * (12 - 7) + (|7 - 5)) * (5 - 12)

主栈：-35

操作符栈：(，+，(

解释：( 无条件入栈。

((5 - 12) * (12 - 7) + (7| - 5)) * (5 - 12)

主栈：-35，7

操作符栈：(，+，(

解释：遇到常量，将其入栈。

((5 - 12) * (12 - 7) + (7 -| 5)) * (5 - 12)

主栈：-35，7

操作符栈：(，+，(，-

解释：( 的优先级比 - 低，因此 - 入栈。

((5 - 12) * (12 - 7) + (7 - 5|)) * (5 - 12)

主栈：-35，7，5

操作符栈：(，+，(，-

解释：遇到常量，将其入栈。

((5 - 12) * (12 - 7) + (7 - 5)|) * (5 - 12)

主栈：-35，2

操作符栈：(，+

解释：遇到了 )，弹出操作符栈栈顶元素。发现弹出的操作符为 -，因此我们将主栈栈顶两元素取出相减，将结果压回主栈。继续弹出操作符栈顶元素，发现是 (，结束。

((5 - 12) * (12 - 7) + (7 - 5))| * (5 - 12)

主栈：-33

操作符栈：

解释：遇到了 )，弹出操作符栈栈顶元素。发现弹出的操作符为 +，因此我们将主栈栈顶两元素取出相加，将结果压回主栈。继续弹出操作符栈顶元素，发现是 (，结束。

((5 - 12) * (12 - 7) + (7 - 5)) *| (5 - 12)

主栈：-33

操作符栈：*

解释：栈空，操作符入栈。

((5 - 12) * (12 - 7) + (7 - 5)) * (|5 - 12)

主栈：-33

操作符栈：*，(

解释：( 无条件入栈。

((5 - 12) * (12 - 7) + (7 - 5)) * (5| - 12)

主栈：-33，5

操作符栈：*，(

解释：遇到常量，将其入栈。

((5 - 12) * (12 - 7) + (7 - 5)) * (5 -| 12)

主栈：-33，5

操作符栈：*，(，-

解释：( 的优先级比 - 低，因此 - 入栈。

((5 - 12) * (12 - 7) + (7 - 5)) * (5 - 12|)

主栈：-33，5，12

操作符栈：*，(，-

解释：遇到常量，将其入栈。

((5 - 12) * (12 - 7) + (7 - 5)) * (5 - 12)|

主栈：-33，-7

操作符栈：*

解释：遇到了 )，弹出操作符栈栈顶元素。发现弹出的操作符为 -，因此我们将主栈栈顶两元素取出相减，将结果压回主栈。继续弹出操作符栈顶元素，发现是 (，结束。

代码实现

public class LeetCode770基本计算器IV {

    public static List<String> basicCalculatorIV(String expression, String[] evalvars, int[] evalints) {
        
        //item用于记录多项式的每一个单项
        class Item implements Comparable<Item> {
            //系数
            int coeff;
            //字母
            private ArrayList<String> factors;

            private Item(String factor, int coeff) {
                this.factors = new ArrayList<>();
                this.factors.add(factor);
                this.coeff = coeff;
            }

            private Item(int coeff) {
                this.factors = new ArrayList<>();
                this.coeff = coeff;
            }

            private Item() {
                this.factors = new ArrayList<>();
                this.coeff = 0;
            }

            @Override
            public int compareTo(Item item) {
                if (this.factors.size() == item.factors.size()) {
                    int index = 0;
                    while (index < factors.size() && this.factors.get(index).equals(item.factors.get(index))) {
                        index += 1;
                    }
                    return (index == factors.size()) ? 0 : this.factors.get(index).compareTo(item.factors.get(index));
                } else {
                    return item.factors.size() - this.factors.size();
                }
            }

            @Override
            public String toString() {
                StringBuilder stringBuilder = new StringBuilder();
                stringBuilder.append(coeff);
                for (String factor : factors) {
                    stringBuilder.append("*").append(factor);
                }
                return stringBuilder.toString();
            }

            Item mul(Item item) {
                Item result = new Item();
                result.coeff = this.coeff * item.coeff;
                result.factors.addAll(this.factors);
                result.factors.addAll(item.factors);
                result.factors.sort(String::compareTo);
                return result;
            }
        }

        class Expr {
            
            private ArrayList<Item> items;

            private Expr(Item item) {
                this.items = new ArrayList<>();
                this.items.add(item);
            }

            private void add(Expr expr) {
                items.addAll(expr.items);
                items.sort(Item::compareTo);
                clean();
            }

            private void mul(Expr expr) {
                ArrayList<Item> result = new ArrayList<>();
                for (Item item1 : items) {
                    for (Item item2 : expr.items) {
                        result.add(item1.mul(item2));
                    }
                }
                items = result;
                items.sort(Item::compareTo);
                clean();
            }

            //合并多项式
            private void clean() {
                for (int i = 0; i < items.size(); i++) {
                    while (i + 1 < items.size() && items.get(i).compareTo(items.get(i + 1)) == 0) {
                        items.get(i).coeff += items.get(i + 1).coeff;
                        items.remove(i + 1);
                    }
                    if (i < items.size() && items.get(i).coeff == 0) {
                        items.remove(i--);
                    }
                }
            }

            private Expr operate(Expr expr, String op) {
                switch (op) {
                    case "+":
                        add(expr);
                        break;
                    case "-":
                        for (Item item : expr.items) {
                            item.coeff *= -1;
                        }
                        add(expr);
                        break;
                    case "*":
                        mul(expr);
                        break;
                }
                return this;
            }
        }

        HashMap<String, Integer> map = new HashMap<>();
        for (int i = 0; i < evalvars.length; i++) {
            map.put(evalvars[i], evalints[i]);
        }

        LinkedList<Expr> mainStack = new LinkedList<>();
        LinkedList<String> symStack = new LinkedList<>();
        int index = 0;
        while (index < expression.length()) {
            if (expression.charAt(index) == ' ') {
                index += 1;
            } else if (expression.charAt(index) >= '0' && expression.charAt(index) <= '9') {
                int x = 0;
                while (index < expression.length() && expression.charAt(index) >= '0' && expression.charAt(index) <= '9') {
                    x = x * 10 + expression.charAt(index++) - '0';
                }
                mainStack.push(new Expr(new Item(x)));
            } else if (expression.charAt(index) >= 'a' && expression.charAt(index) <= 'z') {
                StringBuilder stringBuilder = new StringBuilder();
                while (index < expression.length() && expression.charAt(index) >= 'a' && expression.charAt(index) <= 'z') {
                    stringBuilder.append(expression.charAt(index++));
                }
                String factor = stringBuilder.toString();
                if (map.containsKey(factor)) {
                    mainStack.push(new Expr(new Item(map.get(factor))));
                } else {
                    mainStack.push(new Expr(new Item(stringBuilder.toString(), 1)));
                }
            } else if (expression.charAt(index) == '(') {
                symStack.push("(");
                index += 1;
            } else if (expression.charAt(index) == ')') {
                while (!symStack.isEmpty() && !symStack.peek().equals("(")) {
                    Expr expr2 = mainStack.pop();
                    Expr expr1 = mainStack.pop();
                    mainStack.push(expr1.operate(expr2, symStack.pop()));

                }
                symStack.pop();
                index += 1;
            } else if (expression.charAt(index) == '*') {
                //表达式遇到*号，符号栈顶有*号都要触发计算
                while (!symStack.isEmpty() && symStack.peek().equals("*")) {
                    Expr expr2 = mainStack.pop();
                    Expr expr1 = mainStack.pop();
                    mainStack.push(expr1.operate(expr2, symStack.pop()));
                }
                symStack.push("*");
                index += 1;
            } else {
                //表达式遇到+、-号符号，栈顶有+、-、*号都要触发计算
                while (!symStack.isEmpty() && (symStack.peek().equals("+") || symStack.peek().equals("-") || symStack.peek().equals("*"))) {
                    Expr expr2 = mainStack.pop();
                    Expr expr1 = mainStack.pop();
                    mainStack.push(expr1.operate(expr2, symStack.pop()));
                }
                symStack.push((expression.charAt(index) == '+') ? "+" : "-");
                index += 1;
            }
        }
        while (!symStack.isEmpty()) {
            Expr expr2 = mainStack.pop();
            Expr expr1 = mainStack.pop();
            mainStack.push(expr1.operate(expr2, symStack.pop()));
        }

        ArrayList<String> result = new ArrayList<>();
        //symStack为空代表所有的多项式的项已经运算完毕，
        //mainStack里只有一个Expr，此时要合并多项式输出最后结果
        Expr expr = mainStack.pop();
        expr.clean();
        for (Item item : expr.items) {
            result.add(item.toString());
        }
        return result;
    }
}