從零開始:C#實現計算表達式解析與求值——以后綴表達式為例
當提到表達式解析技術時，很多人第一反應可能是復雜且精細的遞歸下降方法。這種方法主要用于構建抽象語法樹（AST），雖然功能強大，能夠處理復雜的語法結構，但它通常需要較高的編程技巧和對語法分析的深入理解。對于初學者來說，這種方法可能顯得有些復雜。因此，我們的目標是從簡潔實用的角度出發，分享一種更適合初學者的表達式求值解析方法，即后綴表達式，也稱為逆波蘭表示法（Reverse Polish Notation, RPN）。RPN的優點在于可以直接通過棧操作進行高效的求值，而不需要構建復雜的語法樹。
我們將從零開始，用純C#語言實現這種后綴表達式的轉換和求值方法。這種方法不僅易于理解和實現，而且在性能上也非常高效。通過這個過程，你將能夠快速掌握表達式解析的基本概念和實現技巧，為后續學習更復雜的解析技術打下堅實的基礎。
一、用程序寫一個計算器
在編程入門階段，實現一個簡單的計算器是一個非常有價值的學習案例。以下是一個簡單的示例：
- 輸入: 1
- 輸入: +
- 輸入: 2
如果程序能夠返回3，那么恭喜你，你已經掌握了變量的基本類型（如數字和字符串的轉換）、基本操作符的使用（如+號求和），以及基本的輸入輸出操作。
如果你能夠輕松實現上述簡單的計算器功能，那么不妨更進一步，思考如何實現更復雜的表達式計算，例如：
CSharp
1+2*(5-1)/(2+3)^2
應該如何用程序來實現呢？
這種表達式的解析和求值是一種常見的需求。在許多場景中，我們希望能夠輸入公式而不僅僅是一個數值，以此來實現更多的動態配置。例如，用戶可以自定義數據分析的規則和邏輯，自定義報表數據的展示，或者在開發過程中提高動態配置的靈活性，減少硬編碼，增強擴展性，實現某些插件化功能。
接下來，我們將從零開始，用純C#代碼實現數值表達式的處理。所有的代碼均為純C#實現，100%無第三方依賴，免費開源，方便學習交流。希望大家關注并點贊。
二、表達式基礎概念
在計算機科學中，表達式的求值是一個非常常見的任務。無論是簡單的計算器程序，還是復雜的編譯器設計，都離不開對表達式的解析和計算。我們首先來了解幾種常見的表達式類型。
2.1 中綴表達式
我們觀察公式:
"(4+2)*3"
在這個公式中，操作符（如+和）位于操作數（如4、2、3）的中間，將要計算的前后數值連接起來。我們稱這類公式為中綴表達式。中綴表達式是一種通用的算術或邏輯公式表示方法，操作符（如加號+、乘號等）位于它所連接的兩個操作數之間。我們日常使用的數學表達式大多是中綴表達式。這種對兩個操作數進行運算的稱為雙目運算符。如果操作符只負責運算一個操作數（如-1中的負號-），我們稱為單目運算符。
2.2 后綴(RPN)表達式
與中綴表達式不同，后綴表達式中的操作符位于操作數之后。例如，上述中綴表達式轉換為后綴表達式為：
"3 4 2 + *"
后綴表達式的計算步驟是從左往右依次檢查字符。如果是數字，則跳至下一位置；如果是操作符，則按操作符要求向前面位置取數進行計算，并將結果存儲在當前位置。最終留下的就是結果。
以"3 4 2 + *"為例，我們從左往右進行計算：
- 第一位是3，跳至下一位置
- 第二位是4，跳至下一位置
- 第三位是2，跳至下一位置
- 第四位是+，為雙目操作符，向前面第二和第三位置取數4、2，執行+運算，得到6
- 合并第二、第三、第四位置為位置二
- 存儲計算結果6至位置2，此時原式變為 "3 6 *"
- 第三位是，為雙目操作符，向新的表達式前面第一和第二位置取數3和6，執行運算，得到18
后綴表達式既不需要括號明確運算順序，也不需要預先知道操作符優先級。這種無歧義的特點，特別適合計算機的存儲與執行。除了中綴和后綴表達式外，還有前綴表達式，它們在各自的特定領域有其優勢。
接下來，我們將詳細介紹如何將中綴表達式轉換為后綴表達式，以及如何對后綴表達式進行求值。
三、中綴表達式轉后綴表達式(RPN)
3.1 算符優先級定義
為了理解中綴表達式，我們首先需要理解操作符的兩個屬性：操作目數和優先級。
- 操作目數：操作符的操作目數決定了中綴表達式中操作符可以操作多少個操作數。如果操作目數與實際操作數字不匹配，則可視為表達式出錯。
- 優先級：操作符的優先級決定了中綴表達式中的運算規則。例如，乘除法優先于加減法，因為乘除操作符的優先級更高。類似地，我們可以定義冪運算的優先級比乘除操作符更高，布爾運算符的優先級最低等。如果操作優先級相同，我們默認按照從左到右的順序執行計算。
此外，括號具有特殊的優先級。在外部操作符識別時，括號需要單獨判定，但在運算時，其優先級低于其他操作符。
在C#中，我們可以定義一個Dictionary<char, int>來存儲操作符的優先級：
private static Dictionary<char, int> operatorPrecedence
= new()
{
{'+', 1},
{'-', 1},
{'*', 2},
{'/', 2},
{'^', 3},
{'(', 0}, // 特殊優先級，外部單獨判定
{')', 0} // 特殊優先級，外部單獨判定
};
接下來，我們需要實現兩個函數，分別用于判定一個字符是否為操作符，以及獲取操作符的優先級：
// 判斷是否是操作符
private static bool IsOperator(char c)
{
return operatorPrecedence.ContainsKey(c);
}
//獲取操作符優先級
private static int GetPrecedence(char c)
{
return operatorPrecedence[c];
}
3.2 轉換流程
在開始轉換之前，我們需要準備一個棧operatorStack，用來臨時存放操作符（如+、-、*、/），以及一個列表outputList，用來存放最終的后綴表達式：
Stack<char> operatorStack = new Stack<char>();
List<string> outputList = new List<string>();
然后，我們開始逐個處理表達式中的字符：
- 如果當前字符是數字 0-9，直接將其添加到outputList中。
- 如果當前字符是左括號 (，直接將其壓入operatorStack棧中。
- 如果當前字符是右括號 )，從operatorStack棧中彈出操作符，并將其添加到outputList中，直到遇到左括號。遇到左括號后，將其從棧中彈出，但不添加到outputList中。
- 如果當前字符是操作符（如+、-、*、/），比較當前操作符和棧頂操作符的優先級。如果棧頂操作符的優先級大于或等于當前操作符的優先級，將棧頂操作符彈出，并將其添加到outputList中。重復這個過程，直到棧頂操作符的優先級小于當前操作符的優先級。然后，將當前操作符壓入operatorStack棧中。
遍歷完表達式后，operatorStack棧中可能還有剩余的操作符。將這些操作符依次彈出，并添加到outputList中。最終，outputList中的內容就是后綴表達式。
3.3 手動試算
讓我們試算一下 "(4+2)*3":
- 第一個字符是"(", 那么壓入operatorStack棧中，此時狀態：
operatorStack：(
outputList: 空
- 第二個字符是4，直接加入outputList，此時狀態：
operatorStack：(
outputList: 4
- 第三個字符是+，比較棧頂操作符 (, +優先級更高直接入棧，此時狀態:
operatorStack：( +
outputList: 4
- 第四個字符是2，，直接加入outputList，此時狀態：
operatorStack：( +
outputList: 4 2
- 第五個字符是)，從operatorStack彈出操作符到outputList，直到左括號，此時狀態：
operatorStack：空
outputList: 4 2 +
- 第六個字符是*，此時棧為空，直接入棧，此時狀態：
operatorStack：*
outputList: 4 2 +
- 第七個字符是3，直接加入outputList，此時狀態：
operatorStack：*
outputList: 4 2 + 3
- 字符遍歷結束，operatorStack依此出棧加入outputList，此時狀態：
operatorStack：空
outputList: 4 2 + 3 *
3.4 詳細的代碼實現
按上述邏輯設計后，具體代碼實現如下：
public static List<string> InfixToPostfix(string expression)
{
Stack<char> operatorStack = new Stack<char>();
List<string> outputList = new List<string>();
foreach (char c in expression) //遍歷每個字符
{
if (char.IsDigit(c)) // 如果是數字，直接輸出
{
outputList.Add(c.ToString());
}
else if (c == '(') // 左括號，直接壓入棧
{
operatorStack.Push(c);
}
else if (c == ')') // 右括號，彈出操作符直到遇到左括號
{
while (operatorStack.Count > 0 && operatorStack.Peek() != '(')
{
outputList.Add(operatorStack.Pop().ToString());
}
if (operatorStack.Count > 0 && operatorStack.Peek() == '(')
{
operatorStack.Pop(); // 彈出左括號
}
}
else if (IsOperator(c)) // 操作符
{
while (operatorStack.Count > 0 && GetPrecedence(operatorStack.Peek()) >= GetPrecedence(c))
{
outputList.Add(operatorStack.Pop().ToString());
}
operatorStack.Push(c);
}
}
// 將棧中剩余的操作符依次彈出并輸出
while (operatorStack.Count > 0)
{
outputList.Add(operatorStack.Pop().ToString());
}
return outputList;
}
最后返回的List
四、后綴表達式求解(RPN)
后綴表達式的求解非常簡單。首先準備一個棧用來存放數字，然后逐個讀取表達式的每個部分。如果是數字，就壓入棧；如果是操作符，就從棧中彈出對應的操作數進行計算，然后將結果壓回棧。計算完成后，棧里剩下的最后一個數字就是表達式的結果。
以下是具體的代碼實現：
public static double EvaluatePostfix(IList<string> postfix)
{
Stack<double> stack = new Stack<double>();
foreach (string token in postfix)
{
if (double.TryParse(token, out double number)) // 如果是數字，壓入棧
{
stack.Push(number);
}
else // 如果是操作符
{
double b = stack.Pop(); // 彈出第二個操作數
double a = stack.Pop(); // 彈出第一個操作數
switch (token)
{
case "+":
stack.Push(a + b);
break;
case "-":
stack.Push(a - b);
break;
case "*":
stack.Push(a * b);
break;
case "^":
stack.Push(Math.Pow(a,b));
break;
case "/":
if (b == 0)
throw new DivideByZeroException("除數不能為零");
stack.Push(a / b);
break;
default:
throw new ArgumentException("無效的操作符: " + token);
}
}
}
return stack.Pop(); // 棧中剩下的最后一個元素就是結果
}
輸入之前的案例效果如下：
輸入: 1+2*(5-1)/(2+3)^2
輸出: 1 2 5 1 - * 2 3 + 2 ^ / +
求值: 1.32
五、最后
通過上述內容，我們從零開始，用純C#語言實現了一個簡單的表達式解析器。我們首先介紹了中綴表達式和后綴表達式的基本概念，然后詳細討論了如何將中綴表達式轉換為后綴表達式，以及如何對后綴表達式進行求值。這種方法不僅易于理解和實現，而且在性能上也非常高效，特別適合初學者學習和實踐。希望這篇文章對你有所幫助，也歡迎大家在學習過程中提出問題和建議，歡迎隨時交流！
本文中代碼項目已在倉庫完全開源了！點個 Star ??支持一下！代碼倉庫地址 https://github.com/LdotJdot/RPN
其他項目可關注微信公眾號，發送消息 “TDS”,"Json"即可查看
感謝您的耐心閱讀，希望各位從零開始的新朋友和老朋友有所收獲！如果你對這篇文章的內容有任何建議或想法，歡迎隨時交流！關注微信公眾號‘螢火初芒’
浙公網安備 33010602011771號