1.前綴表達(dá)式又稱波蘭式，前綴表達(dá)式的運(yùn)算符位于操作數(shù)之前。比如:- × + 3 4 5 6
2.中綴表達(dá)式就是常見的運(yùn)算表達(dá)式，如(3+4)×5-6
3.后綴表達(dá)式又稱逆波蘭表達(dá)式,與前綴表達(dá)式相似，只是運(yùn)算符位于操作數(shù)之后,比如:3 4 + 5 × 6 -

人類最熟悉的一種表達(dá)式1+2，(1+2)3，3+42+4等都是中綴表示法。對于人們來說，也是最直觀的一種求值方式，先算括號里的，然后算乘除，最后算加減，但是，計(jì)算機(jī)處理中綴表達(dá)式卻并不方便。

然后我們還需明確一些概念，下面通過我們最熟悉的中綴表達(dá)式畫出一棵語法樹來直觀認(rèn)識一下前后綴表達(dá)式的生成。以A+B*(C-D)-E*F為例：

image

中綴表達(dá)式得名于它是由相應(yīng)的語法樹的中序遍歷的結(jié)果得到的。上面的二叉樹中序遍歷的結(jié)果就是A+B*(C-D)-E*F。

前綴表達(dá)式是由相應(yīng)的語法樹的前序遍歷的結(jié)果得到的。上圖的前綴表達(dá)式為- + A * B - C D * E F

后綴表達(dá)式又叫做逆波蘭式。它是由相應(yīng)的語法樹的后序遍歷的結(jié)果得到的。上圖的后綴表達(dá)式為：A B C D - * + E F * -

下面我們關(guān)注兩個點(diǎn)：
1.如何根據(jù)一個逆波蘭表達(dá)式求出運(yùn)算結(jié)果？
2.如果將一個中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式（逆波蘭表達(dá)式）

一.通過逆波蘭表達(dá)式計(jì)算結(jié)果

我們先看一個例子...后綴表達(dá)式3 4 + 5 × 6 -的計(jì)算
1.從左至右掃描，將3和4壓入堆棧；
2.遇到+運(yùn)算符，因此彈出4和3（4為棧頂元素，3為次頂元素，注意與前綴表達(dá)式做比較），計(jì)算出3+4的值，得7，再將7入棧；
3.將5入棧；
4.接下來是×運(yùn)算符，因此彈出5和7，計(jì)算出7×5=35，將35入棧；
5.將6入棧；
6.最后是-運(yùn)算符，計(jì)算出35-6的值，即29，由此得出最終結(jié)果。

從上面的過程我們?nèi)绾尉帉懘a實(shí)現(xiàn)呢？

可以采用一個輔助的棧來實(shí)現(xiàn)計(jì)算，掃描表達(dá)式從左往右進(jìn)行，如果掃描到數(shù)值，則壓進(jìn)輔助棧中，如果掃描到運(yùn)算符，則從輔助棧中彈出兩個數(shù)值參與運(yùn)算，并將結(jié)果壓進(jìn)到棧中，當(dāng)掃描表達(dá)式結(jié)束后，棧頂?shù)臄?shù)值就是表達(dá)式結(jié)果。

下面是代碼實(shí)現(xiàn)(Java）

 /**
     * 通過逆波蘭表達(dá)式計(jì)算結(jié)果
     * @param ls
     * @return
     */
     //求逆波蘭表達(dá)式的值
    public static int calcRevPolishNotation(String express){
        Stack<String> stack = new Stack<>();
        for (int i = 0; i <express.length() ;i++) {
            // 普通數(shù)值的處理
            if ((express.charAt(i) + "").matches("\\d")){
                stack.push(express.charAt(i) + "");
            // + - * / 運(yùn)算符的處理
            }else if ((express.charAt(i) + "").matches("[\\+\\-\\*\\/]")){
                String k1 = stack.pop();
                String k2 = stack.pop();
                // 計(jì)算結(jié)果
                int res = calcValue(k1, k2, (express.charAt(i) + ""));
                stack.push(res+"");
            }

        }
        return Integer.valueOf(stack.pop());
    }

     //根據(jù)運(yùn)算符計(jì)算結(jié)果
    private static int calcValue(String k1, String k2, String c) {
        switch(c){
            case "+":
                return Integer.valueOf(k1)+Integer.valueOf(k2);
            case "-":
                return Integer.valueOf(k2)-Integer.valueOf(k1);
            case "*":
                return Integer.valueOf(k1)*Integer.valueOf(k2);
            case "/":
                return Integer.valueOf(k2)/Integer.valueOf(k1);
            default:
                throw new RuntimeException("沒有該類型的運(yùn)算符！");
        }
    }

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

中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式主要用到了棧進(jìn)行運(yùn)算符處理，隊(duì)列進(jìn)行排序輸出，規(guī)則為：

1.數(shù)字直接入隊(duì)列
2.運(yùn)算符要與棧頂元素比較
?①棧為空直接入棧
?②運(yùn)算符優(yōu)先級大于棧頂元素優(yōu)先級則直接入棧
?③小于或等于則出棧入列，再與棧頂元素進(jìn)行比較，直到運(yùn)算符優(yōu)先級小于棧頂元
? 素優(yōu)先級后，操作符再入棧
3.操作符是 ( 則無條件入棧
4.操作符為 )，則依次出棧入列，直到匹配到第一個(為止，此操作符直接舍棄，(直接出棧舍棄

代碼實(shí)現(xiàn)(Java)

/**
     * 將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式（逆波蘭表達(dá)式）
     * @param express
     * @return
     */
    public static String transfer(String express){
        Stack<String> stack = new Stack<>();
        List<String> list= new ArrayList<>();
        for (int i=0;i<express.length();i++){
            if ((express.charAt(i)+"").matches("\\d")){
                list.add(express.charAt(i)+"");
            }else if((express.charAt(i)+"").matches("[\\+\\-\\*\\/]")){
                //如果stack為空
                if (stack.isEmpty()){
                    stack.push(express.charAt(i)+"");
                    continue;
                }
                //不為空

                //上一個元素不為（，且當(dāng)前運(yùn)算符優(yōu)先級小于上一個元素則，將比這個運(yùn)算符優(yōu)先級大的元素全部加入到隊(duì)列中
                while (!stack.isEmpty()&&!stack.lastElement().equals("(")&&!comparePriority(express.charAt(i)+"",stack.lastElement())){
                    list.add(stack.pop());
                }
                stack.push(express.charAt(i)+"");
            }else if(express.charAt(i)=='('){
                //遇到左小括號無條件加入
                stack.push(express.charAt(i) + "");
            }else if(express.charAt(i)==')'){
                //遇到右小括號，則尋找上一堆小括號，然后把中間的值全部放入隊(duì)列中
                while(!("(").equals(stack.lastElement())){
                    list.add(stack.pop());
                }
                //上述循環(huán)停止，這棧頂元素必為"("
                stack.pop();
            }
        }
        //將棧中剩余元素加入到隊(duì)列中
        while (!stack.isEmpty()){
            list.add(stack.pop());
        }
        StringBuffer stringBuffer = new StringBuffer();
        //變成字符串
        for (String s : list) {
            stringBuffer.append(s);
        }
        return stringBuffer.toString();
    }

    /**
     * 比較運(yùn)算符的優(yōu)先級
     * @param o1
     * @param o2
     * @return
     */
    public static boolean comparePriority(String o1,String o2){
        return getPriorityValue(o1)>getPriorityValue(o2);
    }

    /**
     * 獲得運(yùn)算符的優(yōu)先級
     * @param str
     * @return
     */
    private static int getPriorityValue(String str) {
        switch(str){
            case "+":
                return 1;
            case "-":
                return 1;
            case "*":
                return 2;
            case "/":
                return 2;
            default:
                throw new RuntimeException("沒有該類型的運(yùn)算符！");
        }
    }

轉(zhuǎn)載自：
原文作者：叫我不矜持
鏈接：http://www.itdecent.cn/p/649c12a80fe8
。