---

1. 前綴表達式(波蘭表達式)

????前綴表達式又稱波蘭表達式，前綴表達式的運算符位于操作數之前

舉例說明： (3+4)×5-6 對應的前綴表達式就是 - × + 3 4 5 6

1.1. 前綴表達式的計算機求值

????從右至左掃描表達式，遇到數字時，將數字壓入堆棧；遇到運算符時，彈出棧頂的兩個數，用運算符對它們做相應的計算（棧頂元素 和 次頂元素），并將結果入棧；重復上述過程直到表達式最左端，最后運算得出的值即為表達式的結果。

例如:
(3+4)×5-6 對應的前綴表達式就是 - × + 3 4 5 6 , 針對前綴表達式求值步驟如下:
????①從右至左掃描，將 6、5、4、3 壓入堆棧
????②遇到 + 運算符，因此彈出 3 和 4（3為棧頂元素，4為次頂元素），計算出 3 + 4 的值，得 7，再將 7 入棧
????③接下來是 × 運算符，因此彈出 7 和 5 ，計算出 7 × 5 = 35，將35入棧
????④最后是 - 運算符，計算出 35 - 6 的值，即 29 ，由此得出最終結果

2. 中綴表達式

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

????中綴表達式的求值是我們人最熟悉的，但是對計算機來說卻不好操作(前面我們講的案例就能看的這個問題)，因此，在計算結果時，往往會將中綴表達式轉成其它表達式來操作(一般轉成后綴表達式)

3. 后綴表達式(逆波蘭表達式)

????后綴表達式又稱逆波蘭表達式，與前綴表達式相似，只是運算符位于操作數之后

舉例說明：

正常表達式	后綴表達式
(3+4)×5-6	3 4 + 5 × 6 –
a+b	a b +
a+(b-c)	a b c - +
a+(b-c)*d	a b c - d * +
a+d*(b-c)	a d b c - * +
a=1+3	a 1 3 + =

3.1. 后綴表達式的計算機求值

????
????從左至右掃描表達式，遇到數字時，將數字壓入堆棧；遇到運算符時，彈出棧頂的兩個數，用運算符對它們做相應的計算（次頂元素 和 棧頂元素），并將結果入棧；重復上述過程直到表達式最右端，最后運算得出的值即為表達式的結果。

例如:
(3+4)×5-6 對應的后綴表達式就是 3 4 + 5 × 6 - , 針對后綴表達式求值步驟如下:

????①從左至右掃描，將3和4壓入堆棧；
????②遇到 + 運算符，因此彈出 4 和 3（4 為棧頂元素，3 為次頂元素），計算出 3 + 4 的值，得 7 ，再將 7 入棧；
????③將 5 入棧；
????④接下來是 × 運算符，因此彈出 5 和 7 ，計算出 7 × 5 = 35 ，將 35 入棧；
????⑤將 6 入棧；
????⑥最后是-運算符，計算出 35 - 6 的值，即 29 ，由此得出最終結果

---

3.2. 逆波蘭計算器的實現

????
完成一個逆波蘭計算器，要求完成如下任務:
????輸入一個逆波蘭表達式(后綴表達式)，使用棧(Stack), 計算其結果
????支持小括號和多位數整數(因為這里主要講的是數據結構，因此計算器進行簡化，只支持對整數的計算)

????
思路分析： 3.2. 小節已給出
????
代碼實現：

package stack;import java.util.ArrayList;
import java.util.List;
import java.util.Stack;public class PolandNotation {public static void main(String[] args) {// 定義一個逆波蘭表達式// (3+4)×5-6 --> "3 4 + 5 × 6 -"// 為了方便，逆波蘭表達式的數字和符號使用 空格 隔開String suffixExpression = "3 4 + 5 * 6 -";// 思路// 1.先將"3 4 + 5 × 6 -"放到ArrayList中// 2.將ArrayList傳遞給一個方法，利用棧，完成計算List<String> rpnList = getListString(suffixExpression);System.out.println("rpnList=" + rpnList);int res = calculate(rpnList);System.out.println("計算的結果是=" + res);}// 將一個逆波蘭表達式，依次將數據和運算符放入到ArrayList中public static List<String> getListString(String suffixExpression) {// 將suffixExpression分割String[] split = suffixExpression.split(" ");List<String> list = new ArrayList<String>();for (String ele : split) {list.add(ele);}return list;}// 完成對逆波蘭表達式的運算/*** 1.從左至右掃描，將3和4壓入堆棧；* 2.到 + 運算符，因此彈出 4 和 3（4 為棧頂元素，3 為次頂元素），計算出 3 + 4 的值，得 7 ，再將 7 入棧；* 3.將 5 入棧；* 4.接下來是 × 運算符，因此彈出 5 和 7 ，計算出 7 × 5 = 35 ，將 35 入棧；* 5.將 6 入棧；* 6.最后是-運算符，計算出 35 - 6 的值，即 29 ，由此得出最終結果*/public static int calculate(List<String> ls) {// 創建一個棧，只需要一個即可Stack<String> stack = new Stack<String>();// 遍歷 lsfor (String item : ls) {// 這里使用正則表達式來取出數if (item.matches("\\d+")) {// 匹配的是多位數// 入棧stack.push(item);} else {// pop出兩個數，并運算int num2 = Integer.parseInt(stack.pop());// 先pop出的數int num1 = Integer.parseInt(stack.pop());// 后pop出的數int res = 0;if (item.equals("+")) {res = num1 + num2;} else if (item.equals("-")) {res = num1 - num2;} else if (item.equals("*")) {res = num1 * num2;} else if (item.equals("/")) {res = num1 / num2;} else {throw new RuntimeException("運算符有誤");}// 把res入棧stack.push("" + res);}}// 最后留在stack中的數據就是運算結果return Integer.parseInt(stack.pop());}}

運行結果：

注：也可以計算多位數，讀者可自行測試

4. 中綴表達式 轉 后綴表達式

????從前面講的內容可以看出，后綴表達式適合計算機進行運算，但是人卻不太容易寫出來，尤其是表達式很長的情況下，因此在開發中，我們需要將 中綴表達式 轉成 后綴表達式。

4.1. 思路分析

????

具體步驟如下：

????1.初始化兩個棧：運算符棧s1和儲存中間結果的棧s2；
????2.從左至右掃描中綴表達式；
????3.遇到操作數時，將其壓s2；
????4.遇到運算符時，比較其與s1棧頂運算符的優先級：
??????（1）如果s1為空，或棧頂運算符為左括號“ ( ”，則直接將此運算符入棧；
??????（2）否則，若優先級比棧頂運算符的高，也將運算符壓入s1；
??????（3）否則，將s1棧頂的運算符彈出并壓入到s2中，再次轉到 4.(1) 與s1中新的棧頂運算符相比較；

????5.遇到括號時：
??????（1）如果是左括號“ ( ”，則直接壓入s1
??????（2） 如果是右括號“ ) ”，則依次彈出s1棧頂的運算符，并壓入s2，直到遇到左括號為止，此時將這一對括號丟棄
????6.重復步驟2至5，直到表達式的最右邊
????7.將s1中剩余的運算符依次彈出并壓入s2
????8.依次彈出s2中的元素并輸出，結果的逆序即為中綴表達式對應的后綴表達式

????
????

---

實例分析：
????下面，以中綴表達式：1 + ((2 + 3) * 4) - 5 為例，實現將其轉成后綴表達式。

①初始化兩個棧：運算符棧s1和儲存中間結果的棧s2；從左至右掃描中綴表達式；
②遇到操作數時，將其壓s2（首先掃描到 1 ）

③遇到運算符時，比較其與s1棧頂運算符的優先級：
????（1）如果s1為空，或棧頂運算符為左括號“ ( ”，則直接將此運算符入棧（將 + 直接入s1棧，后面連續遇到兩個" ( “，根據步驟5.(1)，同理，直接將兩個” ( "入s1棧）
????

④遇到操作數時，將其壓s2（掃描到 2 ）

⑤因為下一個掃描到 + 運算符，而 " ( " 不是運算符，故直接將 + 入s1棧

⑥遇到操作數時，將其壓s2（掃描到 3 ）

⑦根據5.(2)：如果是右括號“ ) ”，則依次彈出s1棧頂的運算符，并壓入s2，直到遇到左括號為止，此時將這一對括號丟棄

⑧因為下一個掃描到 * 運算符，而 " ( " 不是運算符，故直接將 * 入s1棧；

接著掃描到 4 ，直接入s2棧

⑨根據5.(2)：如果是右括號“ ) ”，則依次彈出s1棧頂的運算符，并壓入s2，直到遇到左括號為止，此時將這一對括號丟棄

⑩下一個掃描到 - 符號，由于 - 的優先級與 + 相同，故執行 4.(3)：將s1棧頂的運算符彈出并壓入到s2中，再次轉到 4.(1) 與s1中新的棧頂運算符相比較，由于原來的 + 入了s2棧，即s1棧為空，所以直接將 - 運算符入s1棧。

?下一個掃描到 5 ，入s2棧。這時已經到了表達式最右邊，掃描完畢

?執行步驟7：將s1中剩余的運算符依次彈出并壓入s2

?步驟8：依次彈出s2中的元素并輸出，結果的逆序即為中綴表達式對應的后綴表達式

- 5 + * 4 + 3 2 1 – > 1 2 3 + 4 * + 5 -

通過圖表來說明上述步驟：

????

4.2. 代碼實現

????

package stack;import java.util.ArrayList;
import java.util.List;
import java.util.Stack;public class PolandNotation {public static void main(String[] args) {// 完成將一個中綴表達式轉成后綴表達式的功能// 說明// 1.將 "1+((2+3)*4)-5" 轉成 "1 2 3 + 4 * + 5 -"// 2.先將 "1+((2+3)*4)-5" -->中綴表達式對應的List// 即 "1+((2+3)*4)-5"-->ArrayList[1,+,(,(,2,+,3,),*,4,),-,5]String expression = "1+((2+3)*4)-5";List<String> infixExpressionList = toInfixExpressionList(expression);System.out.println(infixExpressionList);System.out.println("中綴表達式對應的List" + infixExpressionList);// 3.中綴表達式對應的List --> 后綴表達式對應的List// 即將ArrayList[1,+,(,(,2,+,3,),*,4,),-,5] --> ArrayList[1,2,3,+,4,*,5,-]List<String> suffixExpressionList = parseSuffixExpressionList(infixExpressionList);System.out.println("后綴表達式對應的List" + suffixExpressionList);System.out.printf("expression = %d", calculate(suffixExpressionList));}// 方法：中綴表達式對應的List --> 后綴表達式對應的Listpublic static List<String> parseSuffixExpressionList(List<String> ls) {// 定義兩個棧Stack<String> s1 = new Stack<String>();// 符號棧// 說明：因為s2這個棧，再整個轉換過程中，沒有pop操作，而且后面我們還需要逆序輸出// 此方法比較麻煩，這里就不用Stack<String>,直接使用List<String> s2// Stack<String> s2 = new Stack<String>();//存儲中間結果的棧s2List<String> s2 = new ArrayList<String>();// 存儲中間結果的List2// 遍歷lsfor (String item : ls) {// 如果是一個數，加入s2if (item.matches("\\d+")) {s2.add(item);} else if (item.equals("(")) {s1.push(item);} else if (item.equals(")")) {// 如果是")"，則依次彈出s1棧頂的運算符，并壓入s2，直到遇到左括號為止，此時將這一對括號丟棄while (!s1.peek().equals("(")) {s2.add(s1.pop());}s1.pop();// 將"("彈出s1，消除小括號} else {// 當item的優先級小于s1棧頂運算符，將s1棧頂的運算符彈出并加入到s2中，再次轉到(4.1)與s1中新的棧頂運算符相比較// 問題：需要一個比較優先級高低的方法while (s1.size() != 0 && Operation.getValue(s1.peek()) >= Operation.getValue(item)) {s2.add(s1.pop());}// 將item壓入s1.push(item);}}// 將s1中剩余的運算符依次彈出并加入s2while (s1.size() != 0) {s2.add(s1.pop());}return s2;// 因為是存放到List，因此按順序輸出就是對應的后綴表達式}// 方法：將中綴表達式轉成對應的Listpublic static List<String> toInfixExpressionList(String s) {// 定義一個List,存放中綴表達式 對應內容List<String> ls = new ArrayList<String>();int i = 0;// 這是一個指針，用于遍歷中綴表達式字符串String str;// 對多位數的拼接char c;// 每遍歷到一個字符，就放入到cdo {// 如果c是一個非數字，需要加入到lsif ((c = s.charAt(i)) < 48 || (c = s.charAt(i)) > 57) {ls.add("" + c);i++;// i需要后移} else {// 如果是一個數，需要考慮多位數str = "";// 先將str置成"";while (i < s.length() && (c = s.charAt(i)) >= 48 && (c = s.charAt(i)) <= 57) {str += c;// 拼接i++;}ls.add(str);}} while (i < s.length());return ls;}// 將一個逆波蘭表達式，依次將數據和運算符放入到ArrayList中public static List<String> getListString(String suffixExpression) {// 將suffixExpression分割String[] split = suffixExpression.split(" ");List<String> list = new ArrayList<String>();for (String ele : split) {list.add(ele);}return list;}// 完成對逆波蘭表達式的運算/*** 1.從左至右掃描，將3和4壓入堆棧；* 2.到 + 運算符，因此彈出 4 和 3（4 為棧頂元素，3 為次頂元素），計算出 3 + 4 的值，得 7 ，再將 7 入棧；* 3.將 5 入棧；* 4.接下來是 × 運算符，因此彈出 5 和 7 ，計算出 7 × 5 = 35 ，將 35 入棧；* 5.將 6 入棧；* 6.最后是-運算符，計算出 35 - 6 的值，即 29 ，由此得出最終結果*/public static int calculate(List<String> ls) {// 創建一個棧，只需要一個即可Stack<String> stack = new Stack<String>();// 遍歷 lsfor (String item : ls) {// 這里使用正則表達式來取出數if (item.matches("\\d+")) {// 匹配的是多位數// 入棧stack.push(item);} else {// pop出兩個數，并運算int num2 = Integer.parseInt(stack.pop());// 先pop出的數int num1 = Integer.parseInt(stack.pop());// 后pop出的數int res = 0;if (item.equals("+")) {res = num1 + num2;} else if (item.equals("-")) {res = num1 - num2;} else if (item.equals("*")) {res = num1 * num2;} else if (item.equals("/")) {res = num1 / num2;} else {throw new RuntimeException("運算符有誤");}// 把res入棧stack.push("" + res);}}// 最后留在stack中的數據就是運算結果return Integer.parseInt(stack.pop());}}// 編寫一個類Operation，可以返回一個運算符對應的優先級
class Operation {private static int ADD = 1;private static int SUB = 2;private static int MUL = 3;private static int DIV = 4;// 寫一個方法，返回對應的優先級數字public static int getValue(String operation) {int result = 0;switch (operation) {case "+":result = ADD;case "-":result = SUB;case "*":result = MUL;case "/":result = DIV;break;default:System.out.println("不存在該運算符");break;}return result;}
}

運行結果：

5. 逆波蘭計算器的完整版

完整版的逆波蘭計算器，功能包括：
????①支持 + - * / ( )
????②多位數，支持小數,
????③兼容處理, 過濾任何空白字符，包括空格、制表符、換頁符

逆波蘭計算器完整版考慮的因素較多，但基本思路和前面一樣，也是使用到：中綴表達式轉后綴表達式。

代碼實現：

package stack;import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Stack;
import java.util.regex.Pattern;public class ReversePolishMultiCalc {/*** 匹配 + - * / ( ) 運算符*/static final String SYMBOL = "\\+|-|\\*|/|\\(|\\)";static final String LEFT = "(";static final String RIGHT = ")";static final String ADD = "+";static final String MINUS = "-";static final String TIMES = "*";static final String DIVISION = "/";/*** 加減 + -*/static final int LEVEL_01 = 1;/*** 乘除 * /*/static final int LEVEL_02 = 2;/*** 括號*/static final int LEVEL_HIGH = Integer.MAX_VALUE;static Stack<String> stack = new Stack<>();static List<String> data = Collections.synchronizedList(new ArrayList<String>());/*** 去除所有空白符* * @param s* @return*/public static String replaceAllBlank(String s) {// \\s+ 匹配任何空白字符，包括空格、制表符、換頁符等等, 等價于[ \f\n\r\t\v]return s.replaceAll("\\s+", "");}/*** 判斷是不是數字 int double long float* * @param s* @return*/public static boolean isNumber(String s) {Pattern pattern = Pattern.compile("^[-\\+]?[.\\d]*$");return pattern.matcher(s).matches();}/*** 判斷是不是運算符* * @param s* @return*/public static boolean isSymbol(String s) {return s.matches(SYMBOL);}/*** 匹配運算等級* * @param s* @return*/public static int calcLevel(String s) {if ("+".equals(s) || "-".equals(s)) {return LEVEL_01;} else if ("*".equals(s) || "/".equals(s)) {return LEVEL_02;}return LEVEL_HIGH;}/*** 匹配* * @param s* @throws Exception*/public static List<String> doMatch(String s) throws Exception {if (s == null || "".equals(s.trim()))throw new RuntimeException("data is empty");if (!isNumber(s.charAt(0) + ""))throw new RuntimeException("data illeagle,start not with a number");s = replaceAllBlank(s);String each;int start = 0;for (int i = 0; i < s.length(); i++) {if (isSymbol(s.charAt(i) + "")) {each = s.charAt(i) + "";// 棧為空，(操作符，或者 操作符優先級大于棧頂優先級 && 操作符優先級不是( )的優先級 及是 ) 不能直接入棧if (stack.isEmpty() || LEFT.equals(each)|| ((calcLevel(each) > calcLevel(stack.peek())) && calcLevel(each) < LEVEL_HIGH)) {stack.push(each);} else if (!stack.isEmpty() && calcLevel(each) <= calcLevel(stack.peek())) {// 棧非空，操作符優先級小于等于棧頂優先級時出棧入列，直到棧為空，或者遇到了(，最后操作符入棧while (!stack.isEmpty() && calcLevel(each) <= calcLevel(stack.peek())) {if (calcLevel(stack.peek()) == LEVEL_HIGH) {break;}data.add(stack.pop());}stack.push(each);} else if (RIGHT.equals(each)) {// ) 操作符，依次出棧入列直到空棧或者遇到了第一個)操作符，此時)出棧while (!stack.isEmpty() && LEVEL_HIGH >= calcLevel(stack.peek())) {if (LEVEL_HIGH == calcLevel(stack.peek())) {stack.pop();break;}data.add(stack.pop());}}start = i; // 前一個運算符的位置} else if (i == s.length() - 1 || isSymbol(s.charAt(i + 1) + "")) {each = start == 0 ? s.substring(start, i + 1) : s.substring(start + 1, i + 1);if (isNumber(each)) {data.add(each);continue;}throw new RuntimeException("data not match number");}}// 如果棧里還有元素，此時元素需要依次出棧入列，可以想象棧里剩下棧頂為/，棧底為+，應該依次出棧入列，可以直接翻轉整個stack 添加到隊列Collections.reverse(stack);data.addAll(new ArrayList<>(stack));System.out.println(data);return data;}/*** 算出結果* * @param list* @return*/public static Double doCalc(List<String> list) {Double d = 0d;if (list == null || list.isEmpty()) {return null;}if (list.size() == 1) {System.out.println(list);d = Double.valueOf(list.get(0));return d;}ArrayList<String> list1 = new ArrayList<>();for (int i = 0; i < list.size(); i++) {list1.add(list.get(i));if (isSymbol(list.get(i))) {Double d1 = doTheMath(list.get(i - 2), list.get(i - 1), list.get(i));list1.remove(i);list1.remove(i - 1);list1.set(i - 2, d1 + "");list1.addAll(list.subList(i + 1, list.size()));break;}}doCalc(list1);return d;}/*** 運算* * @param s1* @param s2* @param symbol* @return*/public static Double doTheMath(String s1, String s2, String symbol) {Double result;switch (symbol) {case ADD:result = Double.valueOf(s1) + Double.valueOf(s2);break;case MINUS:result = Double.valueOf(s1) - Double.valueOf(s2);break;case TIMES:result = Double.valueOf(s1) * Double.valueOf(s2);break;case DIVISION:result = Double.valueOf(s1) / Double.valueOf(s2);break;default:result = null;}return result;}public static void main(String[] args) {// String math = "9+(3-1)*3+10/2";String math = "12.8 + (2 - 3.55)*4+10/5.0";try {doCalc(doMatch(math));} catch (Exception e) {e.printStackTrace();}}}

運行結果：