什么是波蘭表達式

早在1920年，波蘭科學(xué)家揚·武卡謝維奇就發(fā)明了一種不需要括號的表示法，可以用來表示一個計算表達式。即將操作符號寫在操作數(shù)之前，也就是前綴表達式，即波蘭式（Polish Notation, PN）。這種表達式直到1960年計算機出現(xiàn)后才發(fā)揮出其威力

比如2 + 3 * (5 - 1)這個表達式的前綴表達式為+ 2 * 3 - 5 1來表示。
閱讀這個表達式需要從左至右讀入表達式，如果一個操作符后面跟著兩個操作數(shù)時，則計算，然后將結(jié)果作為操作數(shù)替換這個操作符和兩個操作數(shù)，重復(fù)此步驟，直至所有操作符處理完畢。從左往右依次讀取，直到遇到- 5 1，做計算后，將表達式替換為+ 2 * 3 4，然后從左往右再次讀取，直到遇到* 3 4，做計算后將表達式替換為+ 2 12，然后從左往右依次讀取，讀到+ 2 12，計算得到14，到此結(jié)束。

可以看到，這種計算過程也相當(dāng)復(fù)雜，需要多次遍歷表達式，而且需要識別一個操作符后面跟著兩個操作數(shù)這種模式，相比而言，下文中的逆波蘭式要更為直接和簡單。

什么是逆波蘭表達式

即后綴表達式，更加廣為人知一些，和前綴表達式剛好相反，是將操作符號放置于操作數(shù)之后

比如2 + 3 * (5 - 1)用逆波蘭式來表示則是：2 3 5 1 - * +。
逆波蘭式的計算也是從左往右依次讀取，當(dāng)讀到操作符時，將之前的兩個操作數(shù)做計算，然后替換這兩個操作數(shù)和操作符，接著讀取，重復(fù)此步驟。對于這個表達式，讀到5 1 -，得到4，然后讀取乘號，取出前面的3和上一步的計算結(jié)果4，并計算，到12，接著讀取加號+，計算2 12 +得到14，計算結(jié)束。

上面這個步驟可以很容易的用棧來實現(xiàn)：
從左往右依次讀取表達式，如果是數(shù)字則將該數(shù)字壓棧，如果是符號，則將之前的兩個數(shù)字出棧，做計算后，將計算結(jié)果壓棧，直到表達式讀取結(jié)束。棧中剩下的一個數(shù)就是計算結(jié)果

實現(xiàn)：

 //計算后綴表達式
    public static int calculateHouzhui(List<String> list){
        Stack<String> s=new Stack<String>();
        for(String ob:list){
            if(!operator.contains(ob)){
                s.add(ob);
            }else{
                String b=s.pop();
                String a=s.pop();
                String value=calculate(a, b, ob)+"";
                s.add(value);
            }
        }
        return Integer.parseInt(s.pop());
    }
    public static int calculate(String a,String b,String operator){
        int aa=Integer.parseInt(a);
        int bb=Integer.parseInt(b);
        if(operator.equals("+")){
            return aa+bb;
        }else if(operator.equals("-")){
            return aa-bb;
        }else if(operator.equals("*")){
            return aa*bb;
        }else if(operator.equals("/")){
            return aa/bb;
        }
        return 0;
    }

View Code

  中綴表達式轉(zhuǎn)換為后綴表達式

 (1)當(dāng)讀到數(shù)字直接送至輸出隊列中
 (2)當(dāng)讀到運算符t時：
　　a. 將棧中所有優(yōu)先級高于或等于t的運算符彈出，送到輸出隊列中；
　　　　注：這句話不好理解，可以說成這樣，從棧頂開始，依次彈出操作符，如果操作符優(yōu)先級大于或者等于t，則送到輸出隊列，如果比它優(yōu)先級低的或者遇到了一個左括號就停止。并同時放這個運算符回到棧中
　　b. t進棧；
（3）讀到左括號時總是將它壓入棧中
（4）讀到右括號時，將靠近棧頂?shù)牡谝粋€左括號上面的運算符全部依次彈出，送至輸出隊列后，再丟棄左括號和當(dāng)前右括號
（5）中綴表達式全部讀完后，若棧中仍有運算符，將其送到輸出隊列中

 舉個栗子 中綴表達式：3+(2-5)*6/3

 后綴表達式轉(zhuǎn)中綴表達式

思路：和計算后綴表達式類似。從左往右依次讀取表達式，如果是數(shù)字則將該數(shù)字壓棧，如果是符號，則將之前的兩個數(shù)字出棧，拼接符號，并壓棧，記錄該符號棧，壓棧之前與之前記錄的操作符做比較。如果當(dāng)前操作符大于記錄值。則棧中表達式 需要加括號
舉個栗子：后綴表達式 3+(2-5)*6/3