3.3 字首、中綴和字尾表達式
-
-
- 前言
- 基于三種表達式特點的定義
-
- 定義
- 示例
- 解釋
- 基于二叉樹定義
-
- 定義
- 解釋
- 示例
- 中綴表達式的歧義
- 三種表達式的計算方法
-
- 字首表達式
- 中綴表達式
- 字尾表達式
- 中綴表達式轉字尾表達式
-
- 思路
- 代碼
-
前言
我第一次接觸這三種表達式是在資料結構課程的二叉樹周遊部分，是以下面一部分内容是從二叉樹周遊角度來解釋這三種表達式。
基于三種表達式特點的定義
定義
- 字首表達式：在字首表達式中，操作符位于兩個操作數之前，操作數從從左到右順序出現。
- 中綴表達式：在中綴表達式中，每個二進制操作符出現在左操作數之後，右操作數之前。
- 字尾表達式：在字尾表達式中，操作符跟在兩個操作數之後，操作數從左到右出現。
示例
| 中綴 | 字首 | 字尾 |
|---|---|---|
| a*b+c/d | +*ab/cd | ab*cd/+ |
| a+b+c+d | ++++abcd | ab+c+d+ |
| a+b*c | +a*bc | abc*+ |
解釋
- 首先中綴表達式就是我們在數學課上正常學到的數學表達式。
- 注意在 字首表達式 和 字尾表達式 定義中兩個操作數這一概念。對于數學表達式 a+b*c 來說，+ 号的左操作數是a，+ 号的右操作數不是b，而是 b*c 的積，是以依據字首表達式的定義，+ 号應在 a 和 b*c 之前，而 b*c 又是一個數學表達式，是以 + 号應在a 和 b*c 的字首表達式之前。又因為操作數從從左到右順序出現，且 b*c 的結果就是一個操作數，是以 a 和 b*c 是都屬于操作數，是以 a 和 b*c 的中綴表達式應從左到右順序出現。字尾表達式同理。
基于二叉樹定義
定義
- 對一棵數學表達式樹分别進行中序、前序和後序周遊，結果便是表達式的中綴、字首和字尾形式。
- 前序周遊：先通路節點，再通路節點的左子樹，再通路節點的右子樹
- 中序周遊：先通路節點的左子樹，再通路節點，再通路節點的右子樹
- 後序周遊：先通路節點的左子樹，再通路節點的右子樹，再通路節點
解釋
- 數學表達式樹可以說就是存儲了一個數學表達式的二叉樹，在數學表達式樹中，左操作數是操作符的左子樹，右操作數是操作符的右子樹。
- 因為二叉樹有三種周遊方式，可以得出三種周遊結果。一個數學表達式樹在經過三種周遊後，傳回的結果是不同的，對不同的結果有不同的計算方式。
- 在本文中我們不需要關心數學表達式樹是如何建立的，也不太需要關心它對應的原數學表達式是什麼，因為一個數學表達式可以對應多棵數學表達式樹，一棵數學表達式樹在中序周遊下也可能會對應多個不同的數學表達式。
示例
中綴表達式的歧義
算術表達式樹如下：
中序周遊結果：x+y*z
而顯然樹對應的表達式還可能是：(x+y)*z。這樣就出現了歧義。
注意：前序、中序和後序周遊都隻是單純的按照一定的順序輸出樹中的節點元素。
前序周遊結果：*+xyz 等價的中綴表達式為 (x+y)*z
後序周遊結果：xy+z* 等價的中綴表達式為 (x+y)*z
前序和後序周遊不會出現歧義。
三種表達式的計算方法
字首表達式
-
求值思路
從右至左掃描字首表達式，遇到數字時，将數字壓入堆棧，遇到運算符時，彈出棧頂的兩個數，用運算符對他們做相應的計算，并将結果入棧；重複上述過程直到表達式最左端，最後運算得出的值即為表達式的結果。
-
示例
算數表達式的中綴形式：(1+2)*3-4
對應的字首表達式形式：-*+1 2 3 4
（1）從右至左掃描字首表達式，将4、3、2、1依次入棧
（2）遇到 + 運算符，彈出1和2，計算的結果為3，再将3壓入棧。
（3）掃描到*運算符，彈出3和3，計算結果為9，再将9壓入棧。
（4）最後掃描到 - 運算符，彈出9和4，計算9-4得結果5，5入棧。
（5）掃描完畢，棧中的資料5即為最後結果。、
中綴表達式
可以先處理優先級高的運算符，再處理優先級低的運算符。
因為中綴表達式的歧義，一般不使用中綴表達式進行計算。
字尾表達式
-
求值思路
從左到右掃描字尾表達式，遇到數字時，将數字壓入棧，遇到運算符時，彈出棧頂的兩個數，用運算符對它們做相應的計算，然後将結果入棧；重複上述過程直到表達式最右端，最後運算得出的值即為表達式的結果。
-
示例
算數表達式的中綴形式：(1+2)*3-4
對應的字尾表達式形式：1 2+3*4-
（1）從左至右掃描字尾表達式，将1和2壓入堆棧。
（2）遇到+運算符，彈出棧中的1和2（先入後出），計算1+2的值，得結果3，将3入棧
（3）将3入棧
（4）遇到運算符，彈出棧中3和3，計算3*3=9，将9入棧。
（5）将4入棧
（6）遇到-運算符，彈出棧中4和9，計算9-4=5，将5入棧。
（7）掃描結束，棧中即為算式最終結果。
中綴表達式轉字尾表達式
思路
- 初始化兩個棧：運算符棧s1和資料棧s2
- 從左至右掃描中綴表達式
- 遇到操作數時，将操作數壓入s2
-
遇到運算符時，比較其與s1棧頂運算符的優先級：
4.1 如果s1為空，或棧頂運算符為左括号“(”，則直接将此運算符入棧；
4.2 否則，若優先級比棧頂運算符高，也将運算符壓入s1；
4.3 否則，将s1棧頂的運算符彈出并壓入到s2中，然後再轉到4.1将此運算符與新的棧頂運算符相比較。
-
遇到括号時：
5.1 如果是左括号“(”，則直接壓入s1；
5.2 如果是右括号“)”，則依次彈出s1棧頂的運算符，并押入s2，直到遇到左括号為止，然後将這一對括号丢棄。
- 重複2-5步驟，直至掃描表達式結束
- 将s1中剩餘的運算符依次彈出并壓入s2，然後依次彈出s2中元素并輸出，結果即為字尾表達式。（主要做一個反序）
代碼
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
/**
* 實作中綴表達式轉換為字尾表達式
* @author dxt
*
*/
public class ExpressionConversion {
/**
* 将表達式expression中的數字和操作符提取出來，儲存到List中
* @param expression
* @return
*/
public static List<String> getListFromExpression(String expression){
//1. 定義一個List，存放中綴表達式 對應的資料和操作符
List<String> list = new ArrayList<String>();
//2. 周遊整個表達式字元串，将其中的元素進行分割，讓後儲存到list中
int index = 0; //指向字元串中的每個字元，輔助周遊的指針
char c = ' '; //用于儲存周遊到的第 index 個字元
while(index < expression.length()) {
//一個教訓：當一次循環不隻擷取一個字元時，将擷取字元的操作放到判斷分支中
if((c=expression.charAt(index)) < 48 || (c=expression.charAt(index)) > 57) { //ASIIC碼，非0-9，即預設為運算符
//直接放入list中
list.add(c + ""); //先轉為字元串再添加
index++;
}else { //否則就是數字，這時要處理多位數
String num = "";
while(index<expression.length() && (c=expression.charAt(index))>=48 && (c=expression.charAt(index))<=57) {
num = num+c; //自符串的拼接
index++;
}
list.add(num);
}
}
return list;
}
/**
* 傳回運算符的優先級
* @param opr
* @return
*/
public static int getPriority(String opr) {
if(opr.equals("+") || opr.equals("-")) {
return 1;
}else if(opr.equals("*") || opr.equals("/")) {
return 2;
}else {
throw new RuntimeException("該運算符不存在。");
}
}
/**
* 将中綴表達式轉換為字尾表達式
* @param list
* @return
*/
public static List<String> infixToPostfix(List<String> list) {
//1. 聲明一個符号棧 和 一個數棧（使用List替代數棧，因為數棧在程式中并沒有用到出棧操作）
Stack<String> s1 = new Stack<String>(); //一個符号棧
List<String> s2 = new ArrayList<String>();
//2. 周遊
for(String item : list) {
//2.1 如果是數，則直接入數棧
if(item.matches("\\d+")) {
s2.add(item);
} else if(item.equals("(")) { //2.2 如果是左括号，則直接入符号棧
s1.push(item);
} else if(item.equals(")")) {
//2.3 如果是右括号，則依次彈出s1棧頂的運算符，并将運算符壓入s2，直到遇到左括号，然後丢棄此對括号
while(!(s1.peek().equals("("))) {
s2.add(s1.pop());
}
s1.pop(); //丢棄左括号，同時右括号也不做儲存，此時便相當于删除了此對括号
} else {
//2.4 如果item是運算符，當s1不為空，且棧頂運算符優先級小于等于目前運算符時
while(!s1.isEmpty() && !(s1.peek().equals("(")) && getPriority(item) <= getPriority(s1.peek())) {
//将s1棧頂元素彈出，并押入s2
s2.add(s1.pop());
//通過循環使 item再與s1新的棧頂元素進行比較
}
//否則item入棧（當s1為空，或棧頂運算符優先級 大于 目前運算符時）
s1.push(item);
}
}
//3. 将s1中剩餘内容，添加到s2中
while(s1.size() != 0) {
s2.add(s1.pop());
}
//4. 由于我們使用 list 代替了棧，每次添加資料都是向list尾部添加的，是以可以直接傳回s2
return s2;
}
//測試
public static void main(String[] args) {
String exp = "(2+3)*4-6"; //字尾為 2 3 + 4 * 6 -
String exp1 = "1+((2+3)*4)-5";
List<String> list = getListFromExpression(exp);
System.out.println(list);
List<String> result = infixToPostfix(list);
System.out.println(result);
}
}
結果