文章目錄
- 前言
- 一、認識字首、中綴、字尾表達式
- 二、中綴表達式求值
- 2.1、中綴轉字尾計算（Java題解）
- 2.2、封裝計算接口（接2.1）
- 2.3、leetcode—150. 逆波蘭表達式求值（中等）
- 參考資料
前言
所有部落格檔案目錄索引：部落格目錄索引(持續更新)
一、認識字首、中綴、字尾表達式
在現實生活中我們計算的數學公式表達式就是中綴表達式，例如：(1 + 5) * 4 + 3 * 5
字尾表達式是什麼呢，就是将中綴表達式轉換成計算機能夠看得懂的式子（字尾表達式），接着讓計算機來根據這個字尾表達式來進行快速計算。
中綴表達式：(1 + 5) * 4 + 3 * 5
轉為字尾表達式：1, 5, +, 4, *, 3, 5, *, +
怎麼計算字尾表達式呢？可借助于棧這個資料結構來實作快速計算，主要邏輯是周遊一遍，遇到數字就入棧，遇到符号就出棧兩個，進行運算後入棧即可。
1 入棧 s = [1]
5 入棧 s = [1, 5]
+ 出棧計算和，入棧和 s=[6]
4 入棧 s=[6, 4]
* 出棧計算乘，入棧乘 s=[24]
3 入棧 s=[24, 3]
5 入棧 s=[24, 3, 5]
* 出棧計算乘，入棧乘 s=[24, 15]
+ 出棧計算和，入棧和 s=[39]
最後結果就是39。 字首表達式的話就不怎麼常用，其特點就是運算符在操作數之前，其被稱為波蘭表達式。
- 而字尾表達式是數字在前，符号在後，也就是逆波蘭表達式。
中綴表達式：a+b*c-(d+e)
字首表達式：-+a*bc+de 二、中綴表達式求值
2.1、中綴轉字尾計算（Java題解）
中綴表達式求值過程：中綴表達式(字元串) => 中綴表達式(List集合) => 字尾表達式(List集合) => 根據字尾表達式求值。
規則：
1、中綴表達式(字元串) => 中綴表達式(List集合)
速記流程：掃描一遍，非字元直接添加到集合，若是數字需要考慮多位數情況取到存儲到集合。
2、中綴表達式(List集合) => 字尾表達式(List集合)
所需結構：棧(存儲中間符号)、List集合(存儲字尾表達式)
額外：符号權重，+、-、*、/、(、)【1, 1, 2, 2, 0, 0】
速記流程：周遊一遍
1) 若是比對到數：直接添加到集合。
2) 若是比對到(，入棧。
3) 若是比對到)，開始出棧直至比對到(，整個出棧過程中将符号添加到集合中
4) 若是比對到符号，先找到所有棧中棧頂元素權重>=該符号的符号，若是有就出棧添加到集合，最後将目前符号入棧。
5) 周遊一遍結束後，若是棧中還有符号那麼就出棧添加到集合。
3、 字尾表達式(List集合) => 根據字尾表達式求值
速記流程：周遊一遍集合
1) 若是碰到數，入棧
2) 若是碰到符号，根據對應的符号出棧兩個元素值 pop(num2)、pop(num1)。注意出棧時，是先出棧的num2
若是+：num1 + num2；若是-：num1 - num2；若是*：num1 * num2；若是/：num1 / num2
測試：
"1+((2+3)*4)-5" => [1, +, (, (, 2, +, 3, ), *, 4, ), -, 5] => [1, 2, 3, +, 4, *, +, 5, -] => 16 代碼：
public class Calculator {
//字尾表達式(List集合) => 根據字尾表達式求值
private static Integer calculateSuffix(List<String> suffixList) {
//棧中臨時存儲元素值
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < suffixList.size(); i++) {
String s = suffixList.get(i);
if (!isOper(s)) {
//若是數字直接存儲到棧中
stack.push(Integer.valueOf(s));
}else {
int num2 = stack.pop();
int num1 = stack.pop();
int result = 0;
switch (s) {
case "+":
result = num1 + num2;
break;
case "-":
result = num1 - num2;
break;
case "*":
result = num1 * num2;
break;
case "/":
result = num1 / num2;
break;
default:
break;
}
stack.push(result);
}
}
return stack.isEmpty() ? 0 : stack.pop();
}
//中綴表達式(List集合) => 字尾表達式(List集合)
private static List<String> infixToSuffixExpr(List<String> infixList) {
//棧：存儲符号
Stack<String> stack = new Stack<>();
//結果集
List<String> result = new ArrayList<>();
for (int i = 0; i < infixList.size(); i++) {
String s = infixList.get(i);
//若是目前是數字：直接添加到集合
if (!isOper(s)) {
result.add(s);
}else if ("(".equals(s)){
//若是(，直接入棧
stack.push(s);
}else if(")".equals(s)) {
//若是)，比對到棧中的(，過程中的所有符号添加到集合
while (!stack.isEmpty() && !"(".equals(stack.peek())) {
result.add(stack.pop());
}
//将(從棧中移除
stack.pop();
}else {
//若是符号，首先将棧中所有權重>=目前符号的添加到集合
while (!stack.isEmpty() && Operation.getWeight(stack.peek()) >= Operation.getWeight(s)) {
result.add(stack.pop());
}
//目前符号入棧
stack.add(s);
}
}
//若是目前棧中還有符号，全部添加到集合中
while (!stack.isEmpty()) {
result.add(stack.pop());
}
return result;
}
//中綴表達式(字元串) => 中綴表達式(List集合)
private static List<String> toInfixList(String infixExpr) {
char[] chs = infixExpr.toCharArray();
List<String> result = new ArrayList<>();
for (int i = 0; i < chs.length;) {
char ch = chs[i];
//若是字元
if (isOper(ch)) {
result.add("" + ch);
i++;
}else {
//若是數字(考慮多種情況)
StringBuilder numStr = new StringBuilder();
while (i < chs.length && !isOper(chs[i])) {
numStr.append(chs[i++]);
}
result.add(numStr.toString());
}
}
return result;
}
private static boolean isOper(String str) {
if (str.length() == 1 && (str.charAt(0) >= '0' && str.charAt(0) <= '9')) return false;
return true;
}
private static boolean isOper(char ch) {
if (ch >= '0' && ch <= '9') return false;
return true;
}
}
//運算符号權重
class Operation{
private static int ADD = 1;
private static int SUB = 1;
private static int MUL = 2;
private static int DIV = 2;
public static int getWeight(String expr) {
if (expr == null) return 0;
int val = 0;
switch (expr) {
case "+":
val = ADD;
break;
case "-":
val = SUB;
break;
case "*":
val = MUL;
break;
case "/":
val = DIV;
break;
default:
break;
}
return val;
}
} 接着我們來測試下其中的一些計算過程：
public class Calculator {
public static void main(String[] args) {
//測試三個轉換
test();
}
public static void test() {
//中綴表達式
// String infixExpr = "1+((2+3)*4)-5";
String infixExpr = "(1+5)*4+3*5";
System.out.println("中綴表達式為：" + infixExpr);
//中綴表達式(字元串) => 中綴表達式(List集合)
List<String> infixList = toInfixList(infixExpr);
System.out.println("中綴表達式（List集合）：" + infixList);
//中綴表達式(List集合) => 字尾表達式(List集合)
List<String> suffixList = infixToSuffixExpr(infixList);
System.out.println("字尾表達式（List集合）：" + suffixList);
//字尾表達式(List集合) => 根據字尾表達式求值
Integer result = calculateSuffix(suffixList);
System.out.println("最終值：" + result);
}
} 
2.2、封裝計算接口（接2.1）
接着在上面的Calculator類中添加公共方法接口：
public class Calculator {
/**
* 對外暴露計算數學式子
* @param expr 中綴表達式
*/
public static int calculate(String expr) {
//去除空字元串
int index = 0;
char[] chs = expr.toCharArray();
for (int i = 0; i < expr.length(); i++) {
char c = expr.charAt(i);
if (c != ' ') chs[index++] = c;
}
expr = new String(chs, 0, index);
//中綴(字元串)=>中綴(集合)
List<String> infixList = toInfixList(expr);
//中綴表達式(List集合) => 字尾表達式(List集合)
List<String> suffixList = infixToSuffixExpr(infixList);
//字尾表達式(List集合) => 根據字尾表達式求值
Integer result = calculateSuffix(suffixList);
return result;
}
//...上面代碼
} 測試代碼：
class Test1{
public static void main(String[] args) {
//調用計算的接口方法
System.out.println(Calculator.calculate("(1 + 5) * 4 + 3 * 5"));
}
} 
2.3、leetcode—150. 逆波蘭表達式求值（中等）
題目連結：150. 逆波蘭表達式求值
題解：實際上就是在2.1中的求字尾表達式
複雜度分析：時間複雜度O(n)；空間複雜度O(n)
class Solution {
public int evalRPN(String[] tokens) {
Stack<Integer> stack = new Stack<>();
for (String token : tokens) {
if (!isOper(token)) {
stack.push(Integer.valueOf(token));
}else if ("+".equals(token)) {
stack.push(stack.pop() + stack.pop());
}else if ("-".equals(token)) {
stack.push(-stack.pop() + stack.pop());
}else if ("*".equals(token)) {
stack.push(stack.pop() * stack.pop());
}else {
int num2 = stack.pop();
int num1 = stack.pop();
stack.push(num1 / num2);
}
}
return stack.pop();
}
public boolean isOper(String token) {
if (token.length() == 1 && (token.charAt(0) < '0' || token.charAt(0) > '9')) return true;
return false;
}
}