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;
    }
}