摘要：將表達(dá)式轉(zhuǎn)換為逆波蘭式，然后求值轉(zhuǎn)換中綴表達(dá)式為逆波蘭式魯棒性檢測，表達(dá)式中沒有操作數(shù)計算逆波蘭式值參考

[TOC]

文章均為本人技術(shù)筆記，轉(zhuǎn)載請注明出處：
[1] https://segmentfault.com/u/yzwall
[2] blog.csdn.net/j_dark/

根據(jù)運(yùn)算符與相關(guān)操作操作數(shù)的位置不同，將表達(dá)式分為前綴，中綴和后綴表達(dá)式；

前綴表達(dá)式(prefix)：又稱波蘭式(polish)，運(yùn)算符位于相關(guān)操作數(shù)之前；

中綴表示式(infix)：運(yùn)算符位于相關(guān)操作數(shù)之間，是通用的表達(dá)式記法；計算機(jī)計算中綴表達(dá)式，一般先將中綴表達(dá)式轉(zhuǎn)換為前綴或后綴表達(dá)式，然后再求值；

后綴表達(dá)式(postfix)：又稱逆波蘭式(reverse polish)，運(yùn)算符位于相關(guān)操作數(shù)之后；逆波蘭式與前綴表達(dá)式是逆序關(guān)系；

當(dāng)一個表達(dá)式以逆波蘭式給出，無需考慮運(yùn)算符優(yōu)先級

假設(shè)給出逆波蘭式合法，從左到右挨個掃描逆波蘭式，

遇到數(shù)字，入棧；

遇到運(yùn)算符，出棧相關(guān)操作數(shù)（加減乘除運(yùn)算出棧2個操作數(shù)，自增自減出棧1個操作數(shù)）

加減乘除：第一個出棧元素為first, 第二個出棧元素為second，計算second op first，將計算結(jié)果入棧

自增自減：棧頂元素出棧，計算first++或first--，將計算結(jié)果入棧（阿里2017實習(xí)生算法題考點）；

假設(shè)給出逆波蘭式不保證合法，需檢查除法出棧的第一個元素是否為0，檢查遇到運(yùn)算符時棧內(nèi)元素數(shù)目是否滿足要求（阿里2017實習(xí)生算法題考點）；

時間復(fù)雜度為$O(N)$，空間復(fù)雜度輔助棧占用空間為$O(N)$$；

/**
 * 逆波蘭表達(dá)式 or 后綴表達(dá)式求值
 * http://www.lintcode.com/en/problem/evaluate-reverse-polish-notation/
 * @author yzwall
 */
class Solution {
    public int evalRPN(String[] tokens) {
        ArrayDeque stack = new ArrayDeque<>();
        String Operations = "+-*/";
        for (String token : tokens) {
            if (!Operations.contains(token)) {
                stack.push(Integer.parseInt(token));
                continue;
            }
            int first = stack.pop();
            int second = stack.pop();
            if (token.equals("+")) {
                stack.push(second + first);
            } else if (token.equals("-")) {
                stack.push(second - first);
            } else if (token.equals("*")) {
                stack.push(second * first);
            } else {
                stack.push(second / first);
            }
        }
        return stack.pop();
    }
}

中綴表達(dá)式符合人類表達(dá)邏輯，運(yùn)算符有優(yōu)先級，除加減乘除運(yùn)算外還有左右括號。用一個棧stack只負(fù)責(zé)存儲中綴表達(dá)式中的運(yùn)算符號（右括號)不入棧）：

規(guī)定運(yùn)算符優(yōu)先級：規(guī)定加減運(yùn)算優(yōu)先級相等且最低，左右括號優(yōu)先級相等且最高，乘除優(yōu)先級相等介于中間；

轉(zhuǎn)換時從左往右掃描表達(dá)式，

空棧時，符號直接入棧；

棧不空時，
4.1 當(dāng)前符號為右括號）：運(yùn)算符棧一直出棧到逆波蘭式，直到棧頂為左括號(或者空棧；棧頂為左括號時，pop掉不加入逆波蘭式（bug點）；

4.2 當(dāng)前符號為其他符號：優(yōu)先級<=棧頂運(yùn)算符優(yōu)先級（bug點），運(yùn)算符棧一直出棧到棧頂運(yùn)算符優(yōu)先級低于當(dāng)前符號或者空棧；優(yōu)先級>棧頂運(yùn)算符優(yōu)先級，直接入棧，

表達(dá)式掃描完畢后，如果棧不空將全部符號出棧到逆波蘭式；

時間復(fù)雜度為$O(N)$，空間復(fù)雜度輔助棧占用空間為$O(N)$

/**
 * 將（中綴）表達(dá)式轉(zhuǎn)換為逆波蘭式（去掉括號）
 * http://www.lintcode.com/zh-cn/problem/convert-expression-to-reverse-polish-notation/
 * @author yzwall
 */
class Solution {
    ArrayList convertToRPN(String[] expression) {
        // 魯棒性檢測
        ArrayList postfix = new ArrayList<>();
        if (expression == null || expression.length == 0) {
            return postfix;
        }
        
        // 規(guī)定運(yùn)算符優(yōu)先級
        HashMap op = new HashMap<>();
        op.put("+", 1);
        op.put("-", 1);
        op.put("*", 2);
        op.put("/", 2);
        op.put("(", 3);
        op.put(")", 3);
        
        // stack為運(yùn)算符號棧
        ArrayDeque stack = new ArrayDeque<>();
        for (String token : expression) {
            // 數(shù)字直接輸出到逆波蘭式
            if (!op.containsKey(token)) {
                postfix.add(token);
                continue;
            }
            if (!stack.isEmpty()) {
                // 遇到右括號，一直出棧（輸出到逆波蘭式）到棧頂為左括號或空棧
                if (token.equals(")")) {
                    while (!stack.isEmpty()) {
                        if (stack.peek().equals("(")) {
                            stack.pop();
                            break;
                        }
                        postfix.add(stack.pop());
                    }
                // 當(dāng)前符號優(yōu)先級低于棧頂符號，一直出棧到棧頂符號優(yōu)先級低于當(dāng)前符號或空棧
                } else if (op.get(stack.peek()) >= op.get(token)) {
                    while (!stack.isEmpty() && op.get(stack.peek()) >= op.get(token)) {
                        // 左括號只有token為右空號時才出棧
                        if (stack.peek().equals("(")) {
                            break;
                        }
                        postfix.add(stack.pop());
                    }
                    stack.push(token);
                } else { // 當(dāng)前符號優(yōu)先級高于棧頂符號，直接入棧
                    stack.push(token);
                }
            } else {
                // 空棧，直接入棧
                stack.push(token);
            }
        }
        
        // 表達(dá)式掃描完畢，將棧內(nèi)符號全部出棧到逆波蘭式
        while (!stack.isEmpty()) {
            postfix.add(stack.pop());
        }        
        
        return postfix;
    }
}

將（中綴）表達(dá)式轉(zhuǎn)換為逆波蘭式；

求轉(zhuǎn)換后的逆波蘭式值；

注意：表達(dá)式中可能一個操作數(shù)都沒有，在進(jìn)行2.之前進(jìn)行魯棒性檢測，比如極端樣例
["(","(","(","(","(",")",")",")",")",")"]答案為0；

/**
 * 給出（中綴）表達(dá)式，求表達(dá)值。將表達(dá)式轉(zhuǎn)換為逆波蘭式，然后求值
 * http://www.lintcode.com/en/problem/expression-evaluation/
 * @author yzwall
 */
class Solution {
    public int evaluateExpression(String[] expression) {
        int result = 0;
        if (expression == null || expression.length == 0) {
            return result;
        }
        
        // 1. 轉(zhuǎn)換（中綴）表達(dá)式為逆波蘭式
        HashMap op = new HashMap<>();
        ArrayList postfix = new ArrayList<>();
        ArrayDeque stack = new ArrayDeque<>();
        op.put("+", 1);
        op.put("-", 1);
        op.put("*", 2);
        op.put("/", 2);
        op.put("(", 3);
        op.put(")", 3);
        
        for (String token : expression) {
            if (!op.containsKey(token)) {
                postfix.add(token);
                continue;
            }
            if (!stack.isEmpty()) {
                if (token.equals(")")) {
                    while (!stack.isEmpty()) {
                        if (stack.peek().equals("(")) {
                            stack.pop();
                            break;
                        }
                        postfix.add(stack.pop());
                    }
                } else if (op.get(stack.peek()) >= op.get(token)) {
                    while (!stack.isEmpty() && op.get(stack.peek()) >= op.get(token)) {
                        if (stack.peek().equals("(")) {
                            break;
                        }
                        postfix.add(stack.pop());
                    }
                    stack.push(token);
                } else {
                    stack.push(token);
                }
            } else {
                stack.push(token);
            }
        }

        while (!stack.isEmpty()) {
            postfix.add(stack.pop());
        }
        
        // 魯棒性檢測，表達(dá)式中沒有操作數(shù)
        if (postfix.isEmpty()) {
            return result;
        }
        
        // 2. 計算逆波蘭式值
        ArrayDeque stack1 = new ArrayDeque<>();
        for (String token : postfix) {
            if (!op.containsKey(token)) {
                stack1.push(Integer.parseInt(token));
                continue;
            }
            int first = stack1.pop();
            int second = stack1.pop();
            if (token.equals("+")) {
                stack1.push(second + first);
            } else if (token.equals("-")) {
                stack1.push(second - first);
            } else if (token.equals("*")) {
                stack1.push(second * first);
            } else {
                stack1.push(second / first);
            }
        }
        result = stack1.pop();
        return result;
    }
}

[1] http://blog.csdn.net/antineutrino/article/details/6763722/