在 Java 中將中綴表達式轉換為後綴表達式
一、簡介
在本教程中，我們將討論將數學表達式的中綴表示法轉換為後綴表示法的演算法和程式碼。
2.Java中的表達式
像 Java 這樣的程式語言允許我們定義和使用不同的數學表達式。表達式可以透過變數、常數和運算子的組合來編寫。
Java 中一些常見的表達式類型包括算術表達式和邏輯表達式。
2.1.算術表達式
算術表達式包括加法(+)、減法(-)、乘法(*)、除法(/)和模(%)等運算子。這些運算子與變數或常數結合使用會產生算術評估：
int x = 100;
int y = 50;
int sum = x + y;
int prod = x * y;
int remainder = x % y;2.2.邏輯表達式
邏輯表達式使用邏輯運算子來取代先前使用的算術運算。最常見的邏輯運算子包括邏輯AND 、 OR, NOT,和XOR ：
boolean andResult = (true && false); // Logical AND
boolean orResult = (true || false); // Logical OR
boolean notResult = !false; // Logical NOT關係表達式主要用於基於比較的邏輯並產生布林值true或false ：
int x = 10;
int y = 8;
boolean bigger = x > y; // true3. 符號
編寫數學表達式有不同的可能方法。這些稱為符號，它們根據運算符和操作數的位置而變化。
3.1.中綴表示法
在中綴表示法表達式中，運算位於運算元之間，使其成為最常見的表達式表示法：
int sum = (a + b) + (c * d);這裡應該注意的是，運算子優先順序是中綴表達式中產生歧義的一個原因，並且扮演重要角色。括號在中綴表示法中很常見，用於強制優先權。
3.2.前綴表示法
前綴，也稱為波蘭表示法，是運算子位於運算元之前的表達式：
int result = * + ab - cd;3.3.後綴表示法
後綴或逆波蘭表示法意味著運算符應位於操作數之後：
int result = ab + cd - *;這裡我們應該注意，同一表達式的前綴和後綴表示法都消除了運算子優先權的明顯歧義，並消除了對括號的需要。出於同樣的原因，它們在表達評估中非常有效。
4. 問題陳述
現在我們已經回顧了數學表達式的不同符號的基礎知識，讓我們繼續討論問題陳述。
給定一個中綴表達式作為輸入，我們應該編寫一個演算法來轉換它並傳回同一表達式的後綴或逆波蘭表示法。
我們透過一個例子來理解：
Input: (a + b) * (c - d)
Output: ab+cd-*
Input: a+b*(c^de)^(f+g*h)-i
Output: abcd^e-fgh*+^*+i-上面的範例顯示輸入是中綴表達式，其中運算子始終位於一對運算元之間。輸出是相同的對應後綴表達式。我們可以假設輸入總是有效的中綴表達式；因此，無需進一步驗證。
5、解決方案
讓我們透過將問題分解為更小的步驟來建立我們的解決方案。
5.1.運算符和操作數
輸入將是中綴表達式的字串表示形式。在實作轉換邏輯之前，從運算元中確定運算子至關重要。
根據輸入範例，操作數可以是小寫或大寫英文字母：
private boolean isOperand(char ch) {
return (ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z');
}除上述運算元外，輸入還包含 2 個括號字元和 5 個運算子。
5.2.優先權和關聯性
我們還應該定義輸入中可能遇到的每個運算符的優先級，並為它們分配一個整數值。 ^（求冪）運算子具有最高優先權，其次是 *（乘）和 /（除），它們具有相似的優先權。最後，+（加法）和 -（減法）運算子的優先順序最低。
讓我們寫一個方法來模仿上面的邏輯：
int getPrecedenceScore(char ch) {
switch (ch) {
case '^':
return 3;
case '*':
case '/':
return 2;
case '+':
case '-':
return 1;
}
return -1;
}當掃描相同優先權的無括號運算子時，關聯性或掃描順序通常是從左到右。此規則的唯一例外是求冪運算符，其中假定順序是從右到左：
char associativity(char ch) {
if (ch == '^') {
return 'R';
}
return 'L';
}6. 轉換演算法
中綴表達式中的每個運算子都引用它周圍的運算元。相反，對於後綴一，每個運算子引用輸入字串中位於其先前的兩個運算元。
對於具有多個中綴運算的表達式，必須先將最內括號內的表達式轉換為後綴。這使我們能夠將它們視為外部操作的單一操作數。我們繼續這個過程並連續消除括號，直到整個表達式被轉換。在一組括號內，最後被消除的括號對是該組中的第一個運算。
這種後進先出行為暗示了堆疊資料結構的使用。
6.1.堆疊和優先權條件
我們將使用堆疊來追蹤我們的操作員。然而，我們需要定義一個規則來確定哪個運算子必須加入到後綴表達式中，以及哪個運算子需要保留在堆疊中以供將來使用。
如果目前符號是運算符，我們有兩個選擇。我們可以將其壓入堆疊或直接將其放入後綴表達式中。如果我們的堆疊是空的，也就是遇到第一個運算子時的情況，我們可以簡單地將目前運算子壓入堆疊。
另一方面，如果堆疊不為空，我們需要檢查優先權以確定運算子將走哪條路。如果目前字元的優先權高於棧頂的優先權，則需要將其壓入棧頂。例如，在 * 之後遇到+會導致將 + 壓入 * 上方的堆疊中。如果優先權分數也相等，且關聯性是預設的從左到右，我們將執行相同的操作。
我們可以將上面的邏輯濃縮為：
boolean operatorPrecedenceCondition(String infix, int i, Stack<Character> stack) {
return getPrecedenceScore(infix.charAt(i)) < getPrecedenceScore(stack.peek())
|| getPrecedenceScore(infix.charAt(i)) == getPrecedenceScore(stack.peek())
&& associativity(infix.charAt(i)) == 'L';
}6.2.掃描中綴表達式並轉換
現在我們已經設定了優先條件，我們來討論如何對中綴運算進行逐步掃描並正確轉換。
如果目前字元是操作數，我們將其添加到後綴結果中。如果當前字元是運算符，我們使用上面討論的比較邏輯並確定是否應該將其添加到堆疊或彈出。最後，當我們完成掃描輸入時，我們將堆疊中的所有內容彈出到後綴表達式中：
String infixToPostfix(String infix) {
StringBuilder result = new StringBuilder();
Stack<Character> stack = new Stack<>();
for (int i = 0; i < infix.length(); i++) {
char ch = infix.charAt(i);
if (isOperand(ch)) {
result.append(ch);
} else {
while (!stack.isEmpty() && (operatorPrecedenceCondition(infix, i, stack))) {
result.append(stack.pop());
}
stack.push(ch);
}
}
while (!stack.isEmpty()) {
result.append(stack.pop());
}
return result.toString();
}6.3.試運行範例
**讓我們使用第一個範例來理解該演算法： a + b * c – d.**我們遇到的第一個字元a,可以立即插入到最終結果中，因為它是一個操作數。但是，如果不遍歷與其關聯的第二個操作數（在本例中為b ），就無法插入 + 運算子。由於我們需要儲存 + 運算子以供將來參考，因此我們將其推送到堆疊中：
Symbol Result Stack
aa []
+ a [+]
b ab [+]當我們遇到b運算元時，我們將其推入後綴結果，即現在的a b.我們還不能從堆疊中彈出運算符 +，因為我們的輸入中有 * 運算子。正如我們在上一節中提到的，* 運算子比位於堆疊頂部的 + 具有更高的優先權。因此，這個新符號被推入堆疊頂部：
Symbol Result Stack
aa []
+ a [+]
b ab [+]
*
ab
[+,*]當遇到下一個運算元c,並將其加到結果中。當我們遇到最後一個符號 -（其優先權低於運算子 *）時，我們從堆疊中彈出元素並將其附加到後綴表達式，直到堆疊為空或堆疊頂部的優先權較低。現在的表達式是abc*+.當前運算子 – 被壓入堆疊：
Symbol Result Stack
aa []
+ a [+]
b ab [+]
*
ab
[+,*]
c
abc
[+,*]
-
abc*+ [-]
d
abc*+d- []最後，我們將最後一個操作數 d 附加到後綴操作並彈出堆疊。後綴運算的值為abc*+d-.
6.4.帶括號的轉換演算法
雖然上述演算法是正確的，但中綴表達式使用括號來解決運算子優先權引起的歧義。因此，處理輸入字串中括號的出現並相應地修改演算法至關重要。
當我們掃描左括號(時，我們將其壓入堆疊。並且，當我們遇到右括號時，所有運算子都需要從堆疊彈出到後綴表達式中。
讓我們透過調整括號來重寫程式碼：
String infixToPostfix(String infix) {
StringBuilder result = new StringBuilder();
Stack<Character> stack = new Stack<>();
for (int i = 0; i < infix.length(); i++) {
char ch = infix.charAt(i);
if (isOperand(ch)) {
result.append(ch);
} else if (ch == '(') {
stack.push(ch);
} else if (ch == ')') {
while (!stack.isEmpty() && stack.peek() != '(') {
result.append(stack.pop());
}
stack.pop();
} else {
while (!stack.isEmpty() && (operatorPrecedenceCondition(infix, i, stack))) {
result.append(stack.pop());
}
stack.push(ch);
}
}
while (!stack.isEmpty()) {
result.append(stack.pop());
}
return result.toString();
}讓我們以上面探討的相同範例（但有括號）進行一次演練：
Input: (a+b)*(cd)
Symbol Result Stack
(
[(]
aa [(]
+ a [(, +]
b ab [(, +]
) ab+ []
* ab+ [*]
( ab+ [*, (]
c ab+c [*, (]
- ab+c [*, (, -]
d ab+cd [*, (, -]
) ab+cd-* []我們應該注意到括號的位置如何改變求值以及對應的字尾表達式。
7. 其他想法
雖然中綴表達式在文本中更常見，但表達式的後綴表示法有許多好處。後綴表達式中不需要括號，因為由於運算元和運算子的順序排列，操作順序很清楚。此外，由於中綴運算中的運算子優先順序和結合性而可能出現的歧義在其後綴形式中被消除了。
這也使它們成為電腦程式中事實上的選擇，特別是在程式語言實作中。
八、結論
在本文中，我們討論了數學表達式的中綴、前綴和後綴表示法。我們專注於將中綴操作轉換為後綴操作的演算法，並看到了一些範例。
與往常一樣，本文的源代碼可以在 GitHub 上找到。