計算表達式（中綴轉字尾表達式，逆波蘭式結果計算）

字首，中綴，字尾表達式(逆波蘭表達式)

參考: https://www.cnblogs.com/chensongxian/p/7059802.html

該算法可以解 leetcode 227題

中綴表達式

中綴表達式就是常見的運算表達式，如 (3 + 4) * 5 - 6

字首表達式

介紹

字首表達式又稱為波蘭式，字首表達式的運算符位于操作數之前

比如： - * + 3 4 5 6

字首表達式的計算機求值

從右至左掃描表達式，遇到數字時，将數字壓入堆棧，遇到運算符彈出棧頂的兩個數字，并進行運算，将結果壓入堆棧。重複上述過程，直到最後的一個數字，即為表達式的結果。

詳細代碼如下：

class Solution {

    public int calculate(String s) {
        // 1. 去除字元串中的空格
        s = s.replaceAll(" ", "");

        // 2. 把表達式轉換成中綴表達式
        List<String> infixExp = exp2InfixExp(s);

        // 3. 把表達式轉成字尾表達式
        List<String> RPNExp = infixExp2RPN(infixExp);

        // 4. 計算字尾表達式的值
        return evalRPN(RPNExp);

    }

    // 把表達式轉成中綴表達式
    public List<String> exp2InfixExp(String s) {
        List<String> ls = new ArrayList<>();
        int i = 0; String str; char c;
        do {
            if ((c = s.charAt(i)) < 48 || c > 57) {
                ls.add("" + c);
                ++i;
            } else {
                str = "";
                while (i < s.length() && ((c = s.charAt(i)) >= 48 && c <= 57)) {
                    str += c;
                    ++i;
                }
                ls.add(str);
            }
        } while (i < s.length());
        return ls;
    }

    // 把中綴表達式轉成字尾表達式（逆波蘭式子）
    public List<String> infixExp2RPN(List<String> tokens) {
        List<String> result = new ArrayList<>();
        // 初始化一個棧，存儲目前臨時
        Stack<String> stack = new Stack<>();

        // 從左往右掃描中綴表達式
        for (String token : tokens) {
            
            if (token.matches("\\d+")) {
                // 如果是操作數，直接放入字尾表達式結果集合 result 中
                result.add(token);
            } else if (token.equals("(")) {
                // 如果是 左括号，直接壓入操作符棧中
                stack.push(token);
            } else if (token.equals(")")) {
                // 如果是 右括号，依次彈出棧頂運算符直到遇到左括号
                while (!stack.peek().equals("(")) result.add(stack.pop());
                // 把左括号 彈出
                stack.pop();
            } else if ("-+*/".contains(token)) {
                // 如果目前是個 操作符
                while(true) {
                    // 如果stack為空， 或者棧頂是左括号，那麼直接将運算符壓入棧
                    if (stack.isEmpty() || stack.peek().equals("(")) {
                        stack.push(token);
                        // 跳出循環
                        break;
                    } else {
                        // 需要比較目前操作符與棧頂操作符的優先級
                        String opTop = stack.peek();
                        if (opIsLargerThan(token, opTop)) {
                            // 如果目前操作符優先級比棧頂高，直接壓入棧
                            stack.push(token);
                            break;
                        } else {
                            // 如果目前操作符優先級比棧頂底，則彈出棧頂操作符，放入字尾表達式結果集中
                            // 然後繼續循環比較 新的棧頂元素和目前運算符的優先級
                            result.add(stack.pop());
                        }
                    }
                }
            }
        }
        // 把剩下的棧元素放入 字尾表達式集合中
        while (!stack.isEmpty()) result.add(stack.pop());

        return result;
    }

    // 計算字尾表達式的值
    public int evalRPN(List<String> tokens) {
        Stack<Integer> stack = new Stack<>();
        for (String token : tokens) {
            if ("-+*/".contains(token)) stack.push(cal(stack.pop(), stack.pop(), token));
            else stack.push(Integer.parseInt(token));
        }
        return stack.pop();
    }

    // 兩個數 和 一個操作符 來計算他們運算後的結果
    public int cal(int b, int a, String op) {
        if (op.equals("-")) return a - b;
        else if (op.equals("+")) return a + b;
        else if (op.equals("*")) return a * b;
        else return a / b;
    }

    // 比較操作符 op1 是否優先級高于 操作符 op2
    public boolean opIsLargerThan(String op1, String op2) {
        int[] o = new int[2];
        String[] ops = new String[2];
        ops[0] = op1; ops[1] = op2;

        for (int i = 0; i < 2; ++i) {
            String op = ops[i];
            if ("/*".contains(op)) o[i] = 2;
            else o[i] = 1;
        }
        return o[0] > o[1];
    }

}