資料結構之后綴運算式求值（java實作）
前記
? 今天在刷leet code的時候刷到了一道題，后綴運算式（逆波蘭運算式）求值，我花了一會兒寫了一下它的解法，但是今天我不談什么是后綴運算式，有興趣的同學可以去論壇上看看其他人聊后綴運算式的問題，單就解題來說，我用了最為常規的辦法，應該也是初學者最容易理解的方法寫的，故代碼數量較多，一定要讀下去哦！
圖解分析
首先我們拿出一個后綴運算式的例子，這里我直接用力扣上的測驗用例，
String[] expression = {"2", "1", "+", "3", "*"};
//其轉化為中綴運算式就是 ((2 + 1) * 3) = 9
對于后綴運算式求值，我們有這樣一個規則：
1. ==遇到數字則入堆疊，==
2. ==遇到算符則取出堆疊頂兩個數字進行計算，并將結果壓入堆疊中，==
我相信有很多同學會有疑惑為什么直接接給出了這個規則，怎么來的這個規則，其實我也會有這樣的疑惑，但是我覺得有可能是因為計算機的作業原理，堆疊的作業原理所知，以前的程式員可能就總結出了很多規律供我們使用，實際上我們不用事事都去追根溯源，要學會使用工具和思考，該深思的地方才去深思，避免重復造輪子，
通過理解規則我們首先能想到的是，這個題我們應該要用到堆疊（Stack），所以我嘗試用圖的方式來演示該作業程序，
第一步：
{“2”, “1”, “+”, “3”, “*”}
首先遍歷的是第一個元素 “2”，此時是數字，直接入堆疊，
第二步：
{“2”, “1”, “+”, “3”, “*”}
遍歷下一個元素 “1” 依舊是數字，也是直接入堆疊，
第三步：
{“2”, “1”, “+”, “3”, “*”}
繼續遍歷下一個元素 “+”，此時我們遇到了規則里面的第二個條件，不是數字了，我們將從堆疊中彈出兩個數字，進行運算，也就是==1 和 2==進行1+2=3，并將3入堆疊，
第四步：
{“2”, “1”, “+”, “3”, “*”}
遍歷到第四個元素 “3”，直接入堆疊，
第五步：
{“2”, “1”, “+”, “3”, “*”}
遍歷最后一個元素 “*”，此時又要從堆疊里面彈出兩個數字，進行運算，也就是3*3=9,再將9入堆疊，
當遍歷完鏈表中所有元素時，堆疊中的唯一的一個數字即為最終的運算結果，
接下來，我們準備進行代碼實作，
代碼實作
我們首先定義一個方法對彈出來的數字進行運算，
值得注意的是，在后綴運算式求值時，從堆疊中彈出來的數，越靠近堆疊底的數，就要作為被減數，被除數
代碼如下：
/**
* 該方法用于計算
*/
public static int cal(int num1,int num2,String oper){
int result = 0;
switch (oper){
case "+":
result = num1 + num2;
break;
case "-":
result = num2 - num1; //靠近堆疊底的做被減數
break;
case "*":
result = num1 * num2;
break;
case "/":
result = num2 / num1; //靠近堆疊底的做被除數
break;
default:
break;
}
return result;
}
然后還需要定義一個用于遍歷字符陣列，完成入堆疊彈堆疊操作的方法
代碼如下：
public static int calculate(List<String> ls){
Stack<String> stack = new Stack<>();
for (String l : ls) {
if (l.matches("-?\\d+")){//正則運算式匹配數字
stack.push(l);
}else{
String num1 = stack.pop();
String num2 = stack.pop();
int calculate = cal(Integer.parseInt(num1), Integer.parseInt(num2), l);
stack.push(String.valueOf(calculate));
}
}
return Integer.parseInt(stack.pop());
}
在對數字進行判別的時候我采用了正則運算式，并考慮到可能為多位數，負數的情況，不理解的同學可以去了解一下正則運算式，
最后就是測驗了：
@Test
public void test() {
//定義一個逆波蘭運算式
String[] surffixExpression = {"2", "1", "+", "3", "*"};
int result = calculate(surffixExpression);
System.out.println(result);
}
后記
至此，后綴運算式的求值就完成了，此方法我認為是初學者最容易理解的方法，不懂的同學可以多畫圖去理解，一邊畫圖一邊思考，演算法題畫圖還是很重要的，動起來，一起學習，
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/188387.html
標籤：其他