22張圖帶你深入剖析前綴、中綴、後綴表達式以及表達式求值
深入剖析前綴、中綴、後綴表達式以及表達式求值
前言
在本篇文章當中主要跟大家介紹以下幾點
- 前綴、中綴和後綴表達式。
- 如何將中綴表達式轉化成後綴表達式。
- 如何使用後綴表達式進行求值。
表達式求值這是一個比較經典的電腦系統基礎問題，但是整個過程比較抽象，本文主要通過圖解的方法幫助大家理解這個問題。
表達式介紹
後綴表達式也稱作逆波蘭表達式，前綴表達式也稱作波蘭表達式，這個是因為這是由波蘭數學家楊-武卡謝維奇提出來的，用於簡化命題邏輯的一種方法。
中綴表達式
我們常見的數學表達式就是中綴表達式，比如說：\(1 + 2\)，像這種我們從小到大經常見到的表達式就叫做中綴表達式，這個表達式的特點就是將運算符（加減乘除）放在兩個操作數（數字）中間。
後綴表達式
後綴表達式和中綴表達式的最大區別就是，他不是將運算符放在操作數中間，而是將運算符放在操作數後面，比如上面的中綴表達式\(1 + 2\)轉化成後綴表達式就為\(12+\)。
前綴表達式
前綴表達式就是將運算符放在操作數的前面，比如上面的中綴表達式\(1 + 2\)轉化成前綴表達式之後為\(+12\)。
表達式之間轉化的例子
上面的表達式還是比較簡單，可能不足以幫助大家好好理解表達式之間的轉化過程。
中綴表達式：\(A + B * (C – D) – E / F\)
現在我們來將上面的中綴表達式轉化成後綴表達式，我們的第一個計算的部分如下（括弧裡面的優先計算）：
根據我們的轉化原理：將運算符放在操作數後面，
上面的得到的後綴表達式繼續進行轉化（現在需要計算\(B\)乘以後面的那個部分）：
繼續進行轉化（從左往後進行計算）：
繼續進行轉化（除法的優先順序比減法高）：
得到最終的結果：
程式如何將中綴表達式轉化成後綴表達式
將中綴表達式轉化成後綴表達式有以下幾條規則（下面的棧是存儲操作符的棧，而且只存儲操作符）：
- 從左到右進行遍歷。
- 遇到操作數，直接加入到後綴表達式當中。
- 遇到界限符。遇到「(」直接入棧，遇到「)」則依次彈出棧內運算符並加入後綴表達式，直到彈出「(」 為止，注意:「(」 不加入後綴表達式。
- 遇到運算符。依次彈出棧中優先順序高於或等於當前運算符的所有運算符，並加入後綴表達式，若碰到「(」或棧空則停止。之後再把當前運算符入棧。
現在我們根據上面的規則來將上文當中的中綴表達式轉化成後綴表達式。
- 遍歷到\(A\)，根據第二條規則，將\(A\)加入到後綴表達式當中，當前的後綴表達式為：\(A\)。
- 現在遍歷到加號，根據前面的規則需要彈出棧裡面優先順序大的運算符，再將加號加入到棧中，當前的後綴表達式為\(A\)。
- 遍歷到\(B\)，直接加入到後綴表達式當中，目前的後綴表達式為\(AB\)。
- 遍歷到\(*\)，根據規則直接將其加入到棧中，當前後綴表達式為\(AB\)。
- 遍歷到\((\)，根據規則直接將其加入到棧中，當前後綴表達式為\(AB\)。
-
遍歷到\(C\)，則直接將其加入到後綴表達式當中，當前後綴表達式為\(ABC\)。
-
遍歷到\(-\)，根據規則將其加入到棧中，當前後綴表達式為\(ABC\)。
-
遍歷到\(D\)，則將其直接加入到後綴表達式當中，當前的後綴表達式為\(ABCD\)。
-
遍歷到\()\)，則需要將棧中的符號彈出，直到遇到\((\)，當前的後綴表達式為\(ABCD-\)。
- 遍歷到\(-\)，需要將棧中優先順序大於等於\(-\)的運算符彈出，則當前的後綴表達式為\(ABCD-*+\)，再將\(-\)壓入棧中。
-
遍歷到\(E\)，直接將數字加入到後綴表達式當中，則當前的後綴表達式為\(ABCD-*+E\)。
-
遍歷到\(/\)，將棧中優先順序大於等於\(/\)的運算符，再將\(/\)壓入到棧中，當前的後綴表達式為\(ABCD-*+E\)。
- 遍歷到\(F\)，直接將其加入到後綴表達式當中，則當前的後綴表達式為\(ABCD-*+EF\)。
- 最終將棧中所有的運算符都彈出，得到的後綴表達式為\(ABCD-*+EF/-\)。
經過上面的過程就可以將一個中綴表達式轉成後綴表達式了，大家如果想要程式碼實現，只需要在遍曆數據的時候根據上面四個規則一個個進行判斷即可，程式並不困難，就是邏輯稍微有點多，需要考慮更多的問題，在寫程式碼的時候需要細緻一點。
後綴表達式求值
在前文當中我們已經得到了表達式\(A + B * (C – D) – E / F\)的後綴表達式為\(ABCD-*+EF/-\)。現在我們需要將這個後綴表達式進行求值。根據後綴表達式求值主要有以下兩條規則：
- 如果遇到數字直接將其加入到數字棧。
- 如果遇到操作符直接從操作數棧彈出兩個數據進行對應的運算，再將運算結果加入到棧中。
現在我們進行後綴表達式的求值過程;
- 首先前面四個\(ABCD\)都是數字，根據上面提到的第一條規則，我們都需要將數字壓入到棧當中，因此遍歷四個數字之後，情況如下：
- 現在遍歷到\(-\)，我們需要將\(D\)和\(C\)彈出，然後進行\(-\)操作的運算，再將結果壓入棧中。
- 現在遍歷到\(*\)，我們需要將\(C-D=M\)和\(B\)彈出，進行乘法運算，然後將結果壓入棧中。
- 現在我們遍歷到\(+\)，需要將棧中剩餘的兩個數彈出，進行加法運算，在將結果壓棧。
- 遍歷\(EF\)都需要將這兩個數壓入到棧當中。
- 現在遍歷到\(/\)，需要進行除法運算，在將得到的結果壓入到棧中。
- 最後遍歷到\(-\)，將棧中的兩個數彈出棧，進行減法運算得到最後的結果。
相信經過上面過程你對後綴表達式求值的過程已經非常清楚了。
程式碼實現
在LeetCode中有一道題就是根據後綴表達式求值——劍指 Offer II 036. 後綴表達式
根據 逆波蘭表示法，求該後綴表達式的計算結果。
有效的算符包括
+、-、*、/。每個運算對象可以是整數，也可以是另一個逆波蘭表達式。說明：
- 整數除法只保留整數部分。
- 給定逆波蘭表達式總是有效的。換句話說，表達式總會得出有效數值且不存在除數為 0 的情況。
示例 1：
輸入：tokens = [“2″,”1″,”+”,”3″,”*”]
輸出：9
解釋：該算式轉化為常見的中綴算術表達式為：((2 + 1) * 3) = 9示例 2：
輸入：tokens = [“4″,”13″,”5″,”/”,”+”]
輸出：6
解釋：該算式轉化為常見的中綴算術表達式為：(4 + (13 / 5)) = 6
上面問題的程式碼如下：
class Solution {
public int evalRPN(String[] tokens) {
Stack<Integer> stack = new Stack<>();
for (String token : tokens) {
switch (token) {
case "+": {
int a = stack.pop();
int b = stack.pop();
stack.push(b + a);
break;
}
case "-": {
int a = stack.pop();
int b = stack.pop();
stack.push(b - a);
break;
}
case "*": {
int a = stack.pop();
int b = stack.pop();
stack.push(b * a);
break;
}
case "/": {
int a = stack.pop();
int b = stack.pop();
stack.push(b / a);
break;
}
default:
stack.push(Integer.parseInt(token));
break;
}
}
return stack.pop();
}
}
總結
本文主要給大家介紹了如何將中綴表達式轉化成後綴表達式，以及程式碼根據後綴表達式求值。本文所談到的問題可能相對於其他問題來說邏輯上可能更加複雜，需要大家自己閱讀和根據文字和圖進行理解。
以上就是本文所有的內容了，希望大家有所收穫，我是LeHung，我們下期再見！！！（記得點贊收藏哦！）
更多精彩內容合集可訪問項目：//github.com/Chang-LeHung/CSCore
關注公眾號：一無是處的研究僧，了解更多電腦（Java、Python、電腦系統基礎、演算法與數據結構）知識。
