本文是學習B站韓順平老師的數(shù)據(jù)結構與算法課程的筆記。關于中綴表達式轉逆波蘭表達式的代碼，和老師的不一樣，自己按照思路實現(xiàn)的。思路比較清晰，如果看老師的代碼有點懵逼的話，可以參考本文的代碼，個人感覺還是非常容易理解的(初步測試通過，不敢保證沒bug，若發(fā)現(xiàn)bug請聯(lián)系我，謝謝)。

一、是什么

如果要你實現(xiàn)一個計算器程序，會怎么做？即用戶輸入一串字符串，比如4 * 5 - 8 + 60 + 8 / 2，你會怎么計算這個操作結果？

要想實現(xiàn)這個功能，我們可以定義兩個棧，一個用來存放數(shù)字，一個用來存放操作符。遍歷字符串，如果遍歷到的字符是數(shù)字，存入存放數(shù)字的棧；如果遍歷到的字符是操作符，那么先判斷存放操作符的棧中是否已經(jīng)有操作符了，沒有就直接入棧，有的話，先比較當前操作符和棧中操作符的優(yōu)先級，如果當前操作符優(yōu)先級高于符號棧的操作符，直接入符號棧；如果當前操作符優(yōu)先級小于或等于棧中的操作符，那就從數(shù)字棧中pop出兩個數(shù)字，從操作符棧pop出操作符，進行計算，將計算后結果再入數(shù)字棧，同時將當前操作符入操作符棧；當字符串遍歷完了后，pop出數(shù)字棧的數(shù)字，即為最后的運算結果。

這個4 * 5 - 8 + 60 + 8 / 2字符串，就叫「中綴表達式」，對我們人來說，中綴表達式是符合習慣的，也是好理解的，但是對于計算機而言，就不太友好，因為計算的時候要去判斷操作符的優(yōu)先級。有一種叫「后綴表達式」的，也叫「逆波蘭表達式」，對計算機就十分友好，不需要判斷優(yōu)先級就可以計算。比如4 * 5 - 8 + 60 + 8 / 2對應的逆波蘭表達式就是4 5 * 8 - 60 + 8 2 / +。

二、中綴表達式轉逆波蘭表達式

「1、分析：」

從上面的轉換可以看出，逆波蘭表達式是已經(jīng)按照運算符優(yōu)先級排列了。首先是 4 * 5，所以逆波蘭表達式是4 5 *，表示4和5做乘法運算；然后減8，所以是8 -，表示和8做減法運算；再然后是60 +，表示和60做加法；然后是8 2 /，表示8和2相除；最后是一個加號，表示8和2相除的結果再與之前的計算結果相加。

「2、中綴轉逆波蘭表達式思路：」

看了上面的分析，人腦肯定是一下子就學會了，但是通過程序要怎么轉？思路如下：

「(1).」 初始化兩個棧，numStack用來存放中間計算步驟的結果，symbolStack用來存放操作符；

「(2).」 從左到右，遍歷中綴表達式；

「(3).」 如果遍歷到的是數(shù)字，push進numStack；

「(4).」 如果遍歷到的是操作符，比較與symbolStack棧頂操作符的優(yōu)先級：

• 如果symbolStack為空，直接入棧；
• 如果symbolStack棧頂是左括號，也直接入棧，
• 如果當前操作符優(yōu)先級高于棧頂操作符(左括號優(yōu)先級高于加減乘除)，也直接入棧；
• 如果當前操作符優(yōu)先級小于等于棧頂操作符，就將symbolStack棧頂?shù)牟僮鞣鹥op出，push到numStack中，然后再重復步驟(4)，讓當前操作符與symbolStack棧新的棧頂元素比較；

「(5).」 如果遇到右括號，則循環(huán)將symbolStack棧頂運算符pop出，push進numStack，直到遇到左括號為止，此時將這一對括號丟棄；

「(6).」 重復步驟(2)至步驟(5)，直到將表達式遍歷完；

「(7).」 將symbolStack棧中剩余的元素依次pop出并push到numStack中；

「(8).」 將numStack中的元素依次pop出，結果的逆序就是該中綴表達式的逆波蘭表達式。

「3、代碼實現(xiàn)：」

public class StackUtil {
 
 private StackUtil() {}
 
    /**
     * 中綴表達式轉逆波蘭表達式
     */
 public static String getReversePolandStr(String inPerffixStr) {
  Stack<String> numStack = new Stack<>();
  Stack<String> symbolStack = new Stack<>();
  List<String> list = splitStr(inPerffixStr);
  for (String string : list) {
   if (isNumber(string)) { // 數(shù)字直接入numStack棧，這里就是步驟三
    numStack.push(string);
   } else if (")".equals(string)) { // 遇到右括號進行步驟五
    step5(string, numStack, symbolStack);
   } else { // 遇到非數(shù)字非右括號的，進行步驟四
    step4(string, numStack, symbolStack);
   }
  }
  step7(numStack, symbolStack);
  return step8(numStack);
 }
 
 
 /**
  * 步驟八
  * @return
  */
 private static String step8(Stack<String> numStack) {
  StringBuilder result = new StringBuilder();
  List<String> tempList = new ArrayList<>();
  while (!numStack.isEmpty()) {
   tempList.add(numStack.pop());
  }
  for (int i=tempList.size()-1; i>=0; i--) {
   result.append(tempList.get(i)).append(" ");
  }
  return result.substring(0, result.length() - 1).toString();
 }


 /**
  * 步驟七
  * @param numStack
  * @param symbolStack
  */
 private static void step7(Stack<String> numStack, Stack<String> symbolStack) {
  while (!symbolStack.isEmpty()) {
   numStack.push(symbolStack.pop());
  }
 }


 /**
  * 步驟五
  * @param string
  * @param numStack
  * @param symbolStack
  */
 private static void step5(String string, Stack<String> numStack, Stack<String> symbolStack) {
  String symbol = "";
  while(!symbol.equals("(")){
   symbol = symbolStack.pop();
   if ("(".equals(symbol)) {
    break;
   }
   numStack.push(symbol);
  }
 }
 
 /**
  * 步驟四
  * @param string
  * @param numStack
  * @param symbolStack
  */
 private static void step4(String string, Stack<String> numStack, Stack<String> symbolStack) {
  if (symbolStack.isEmpty() || symbolStack.peek().equals("(")) {
   symbolStack.push(string);
  } else if (isSuperior(string, symbolStack.peek())) {
   symbolStack.push(string);
  } else {
   String top = symbolStack.pop();
   numStack.push(top);
   step4(string, numStack, symbolStack);
  }
 }
 
 
 /**
  * 判斷str1的優(yōu)先級是否高于str2
  * @param str1
  * @param str2
  * @return
  */
 private static boolean isSuperior(String str1, String str2) {
  String level0 = "(";
  String level1 = "*/";
  String level2 = "+-";
  if (level0.contains(str1) && (level1.contains(str2) || level2.contains(str2))) {
   return true;
  } else if (level1.contains(str1) && level2.contains(str2)){
   return true;
  } else {
   return false;
  }
 }
 
 
 /**
  * 傳入一個中綴表達式，將其數(shù)字和符號一個個的分割開來
  * 例如傳入的是：4.2*5.56-8+60+8.4/2.1
  * 輸出的應該是：[4.2, *, 5.56, -, 8, +, 60, +, 8.4, /, 2.1]
  * @param inPerffixStr
  * @return
  */
 private static List<String> splitStr(String inPerffixStr){
  inPerffixStr = inPerffixStr.replaceAll(" ", "");
  List<String> strList= new ArrayList<>();
  if (StringUtils.isBlank(inPerffixStr)) {
   return strList;
  }
  char[] chars = inPerffixStr.toCharArray();
  StringBuilder numBuilder = new StringBuilder();
  // 如果是小數(shù)點和數(shù)字，那就拼接起來，直到下一次遍歷到的不是小數(shù)點或數(shù)字時，
  // 就將上一次的拼接結果存到集合中，同時清空拼接的StringBuilder，并把本次遍歷到的符號也存到集合中，
  // 別忘了最后一個數(shù)字，需要單獨處理
  for (int i=0; i<chars.length; i++) {
   if(String.valueOf(chars[i]).equals(".")) {
    numBuilder.append(chars[i]);
   } else if (isNumber(String.valueOf(chars[i]))) {
    numBuilder.append(chars[i]);
   } else {
    strList.add(numBuilder.toString());
    numBuilder.delete(0, numBuilder.length());
    strList.add(String.valueOf(chars[i]));
   }
   if (i == chars.length - 1 && numBuilder.length() > 0) {
    strList.add(numBuilder.toString());
   }
  }
  return strList;
 }
 
 /**
  * 判斷傳入的字符串是否是數(shù)字
  * @param str
  * @return
  */
 private static boolean isNumber(String str) {
  Pattern pattern = Pattern.compile("^(\\-|\\+)?\\d+(\\.\\d+)?$");
  Matcher match = pattern.matcher(str);
  return match.find();
 }
 
 
 // 預期：4 5 * 8 - 60 + 8 2 / +
 public static void main(String[] args) {
  String str = "4*5-8+60+8/2";
        //String str = "1+(3-2)*4"; // 1 3 2 - 4 * +
  System.out.println(getReversePolandStr(str));
 }
}

三、計算逆波蘭表達式的結果

「1、思路：」

• 創(chuàng)建一個棧，用來存放數(shù)字；
• 遍歷逆波蘭表達式，如果是數(shù)字，直接入棧；
• 如果是符號，從棧中pop出兩個數(shù)，做相應的計算，將結果再入棧；
• 最后從棧中pop出來的就是最終結果。

「2、代碼實現(xiàn)：」

public class Calculator {

 /**
  * 傳入一個中綴表達式，計算結果
  * 
  * @param expression
  * @return
  */
 public static String calculate(String inPerffixStr) {
  // 1. 獲取逆波蘭表達式
  String reversePoland = StackUtil.getReversePolandStr(inPerffixStr);
  // 2. 將字符串轉成數(shù)組
  String[] strArr = reversePoland.split(" ");
  // 3. 創(chuàng)建一個棧，用來存數(shù)字
  Stack<String> numStack = new Stack<>();
  // 4. 遍歷數(shù)組，如果是數(shù)字，直接入棧，如果是符號，就從棧中pop出兩個數(shù)進行計算，計算結果再入棧
  for (String str : strArr) {
   if (StackUtil.isNumber(str)) {
    numStack.push(str);
   } else {
    String num1 = numStack.pop();
    String num2 = numStack.pop();
    numStack.push(calculate(num1, num2, str));
   }
  }
  return numStack.pop();
 }

 /**
  * @param num1
  * @param num2
  * @param str
  * @return
  */
 private static String calculate(String num1, String num2, String str) {
  String result = "";
  BigDecimal bigNum1 = new BigDecimal(num1);
  BigDecimal bigNum2 = new BigDecimal(num2);
  switch (str) {
  case "+":{
   result = bigNum1.add(bigNum2).toString();
   break;
  }
  case "-":{
   result = bigNum2.subtract(bigNum1).toString();
   break;
  }
  case "*":{
   result = bigNum1.multiply(bigNum2).toString();
   break;
  }
  case "/":{
   result = bigNum2.divide(bigNum1).toString();
   break;
  }
  }
  return result;
 }

 public static void main(String[] args) {
  String str = "4*(5-2)/2+3";
  System.out.println(calculate(str));
 }
}