成人欧美一区二区三区的电影,日韩一级一欧美一级国产,国产成人国拍亚洲精品,无码人妻精品一区二区三区毛片,伊人久久无码大香线蕉综合

當提到表達式解析技術時，很多人第一反應可能是復雜且精細的遞歸下降方法。這種方法主要用于構建抽象語法樹（AST），雖然功能強大，能夠處理復雜的語法結構，但它通常需要較高的編程技巧和對語法分析的深入理解。對于初學者來說，這種方法可能顯得有些復雜。因此，我們的目標是從簡潔實用的角度出發(fā)，分享一種更適合初學者的表達式求值解析方法，即后綴表達式，也稱為逆波蘭表示法（Reverse Polish Notation, RPN）。RPN的優(yōu)點在于可以直接通過棧操作進行高效的求值，而不需要構建復雜的語法樹。
我們將從零開始，用純C#語言實現(xiàn)這種后綴表達式的轉換和求值方法。這種方法不僅易于理解和實現(xiàn)，而且在性能上也非常高效。通過這個過程，你將能夠快速掌握表達式解析的基本概念和實現(xiàn)技巧，為后續(xù)學習更復雜的解析技術打下堅實的基礎。

一、用程序寫一個計算器

在編程入門階段，實現(xiàn)一個簡單的計算器是一個非常有價值的學習案例。以下是一個簡單的示例：

• 輸入: 1
• 輸入: +
• 輸入: 2
  如果程序能夠返回3，那么恭喜你，你已經掌握了變量的基本類型（如數(shù)字和字符串的轉換）、基本操作符的使用（如+號求和），以及基本的輸入輸出操作。
  如果你能夠輕松實現(xiàn)上述簡單的計算器功能，那么不妨更進一步，思考如何實現(xiàn)更復雜的表達式計算，例如：

CSharp
1+2*(5-1)/(2+3)^2

應該如何用程序來實現(xiàn)呢？
這種表達式的解析和求值是一種常見的需求。在許多場景中，我們希望能夠輸入公式而不僅僅是一個數(shù)值，以此來實現(xiàn)更多的動態(tài)配置。例如，用戶可以自定義數(shù)據(jù)分析的規(guī)則和邏輯，自定義報表數(shù)據(jù)的展示，或者在開發(fā)過程中提高動態(tài)配置的靈活性，減少硬編碼，增強擴展性，實現(xiàn)某些插件化功能。
接下來，我們將從零開始，用純C#代碼實現(xiàn)數(shù)值表達式的處理。所有的代碼均為純C#實現(xiàn)，100%無第三方依賴，免費開源，方便學習交流。希望大家關注并點贊。

二、表達式基礎概念

在計算機科學中，表達式的求值是一個非常常見的任務。無論是簡單的計算器程序，還是復雜的編譯器設計，都離不開對表達式的解析和計算。我們首先來了解幾種常見的表達式類型。

2.1 中綴表達式

我們觀察公式:

"(4+2)*3"

在這個公式中，操作符（如+和）位于操作數(shù)（如4、2、3）的中間，將要計算的前后數(shù)值連接起來。我們稱這類公式為中綴表達式。中綴表達式是一種通用的算術或邏輯公式表示方法，操作符（如加號+、乘號等）位于它所連接的兩個操作數(shù)之間。我們日常使用的數(shù)學表達式大多是中綴表達式。這種對兩個操作數(shù)進行運算的稱為雙目運算符。如果操作符只負責運算一個操作數(shù)（如-1中的負號-），我們稱為單目運算符。

2.2 后綴(RPN)表達式

與中綴表達式不同，后綴表達式中的操作符位于操作數(shù)之后。例如，上述中綴表達式轉換為后綴表達式為：

"3 4 2 + *"

后綴表達式的計算步驟是從左往右依次檢查字符。如果是數(shù)字，則跳至下一位置；如果是操作符，則按操作符要求向前面位置取數(shù)進行計算，并將結果存儲在當前位置。最終留下的就是結果。
以"3 4 2 + *"為例，我們從左往右進行計算：

• 第一位是3，跳至下一位置
• 第二位是4，跳至下一位置
• 第三位是2，跳至下一位置
• 第四位是+，為雙目操作符，向前面第二和第三位置取數(shù)4、2，執(zhí)行+運算，得到6
• 合并第二、第三、第四位置為位置二
• 存儲計算結果6至位置2，此時原式變?yōu)?"3 6 *"
• 第三位是，為雙目操作符，向新的表達式前面第一和第二位置取數(shù)3和6，執(zhí)行運算，得到18

后綴表達式既不需要括號明確運算順序，也不需要預先知道操作符優(yōu)先級。這種無歧義的特點，特別適合計算機的存儲與執(zhí)行。除了中綴和后綴表達式外，還有前綴表達式，它們在各自的特定領域有其優(yōu)勢。
接下來，我們將詳細介紹如何將中綴表達式轉換為后綴表達式，以及如何對后綴表達式進行求值。

三、中綴表達式轉后綴表達式(RPN)

3.1 算符優(yōu)先級定義

為了理解中綴表達式，我們首先需要理解操作符的兩個屬性：操作目數(shù)和優(yōu)先級。

• 操作目數(shù)：操作符的操作目數(shù)決定了中綴表達式中操作符可以操作多少個操作數(shù)。如果操作目數(shù)與實際操作數(shù)字不匹配，則可視為表達式出錯。
• 優(yōu)先級：操作符的優(yōu)先級決定了中綴表達式中的運算規(guī)則。例如，乘除法優(yōu)先于加減法，因為乘除操作符的優(yōu)先級更高。類似地，我們可以定義冪運算的優(yōu)先級比乘除操作符更高，布爾運算符的優(yōu)先級最低等。如果操作優(yōu)先級相同，我們默認按照從左到右的順序執(zhí)行計算。
  此外，括號具有特殊的優(yōu)先級。在外部操作符識別時，括號需要單獨判定，但在運算時，其優(yōu)先級低于其他操作符。

在C#中，我們可以定義一個Dictionary<char, int>來存儲操作符的優(yōu)先級：

private static Dictionary<char, int> operatorPrecedence
= new()
{
    {'+', 1},
    {'-', 1},
    {'*', 2},
    {'/', 2},
    {'^', 3}, 
    {'(', 0}, // 特殊優(yōu)先級，外部單獨判定
    {')', 0}  // 特殊優(yōu)先級，外部單獨判定
};

接下來，我們需要實現(xiàn)兩個函數(shù)，分別用于判定一個字符是否為操作符，以及獲取操作符的優(yōu)先級：

// 判斷是否是操作符
private static bool IsOperator(char c)
{
    return operatorPrecedence.ContainsKey(c);
}
//獲取操作符優(yōu)先級
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>();

然后，我們開始逐個處理表達式中的字符：

• 如果當前字符是數(shù)字 0-9，直接將其添加到outputList中。
• 如果當前字符是左括號 (，直接將其壓入operatorStack棧中。
• 如果當前字符是右括號 )，從operatorStack棧中彈出操作符，并將其添加到outputList中，直到遇到左括號。遇到左括號后，將其從棧中彈出，但不添加到outputList中。
• 如果當前字符是操作符（如+、-、*、/），比較當前操作符和棧頂操作符的優(yōu)先級。如果棧頂操作符的優(yōu)先級大于或等于當前操作符的優(yōu)先級，將棧頂操作符彈出，并將其添加到outputList中。重復這個過程，直到棧頂操作符的優(yōu)先級小于當前操作符的優(yōu)先級。然后，將當前操作符壓入operatorStack棧中。

遍歷完表達式后，operatorStack棧中可能還有剩余的操作符。將這些操作符依次彈出，并添加到outputList中。最終，outputList中的內容就是后綴表達式。

3.3 手動試算

讓我們試算一下 "(4+2)*3":

• 第一個字符是"(", 那么壓入operatorStack棧中，此時狀態(tài)：

operatorStack：(
outputList: 空

• 第二個字符是4，直接加入outputList，此時狀態(tài)：

operatorStack：(
outputList: 4

• 第三個字符是+，比較棧頂操作符 (, +優(yōu)先級更高直接入棧，此時狀態(tài):

operatorStack：( +
outputList: 4

• 第四個字符是2，，直接加入outputList，此時狀態(tài)：

operatorStack：( +
outputList: 4 2

• 第五個字符是)，從operatorStack彈出操作符到outputList，直到左括號，此時狀態(tài)：

operatorStack：空
outputList: 4 2 +

• 第六個字符是*，此時棧為空，直接入棧，此時狀態(tài)：

operatorStack：*
outputList: 4 2 +

• 第七個字符是3，直接加入outputList，此時狀態(tài)：

operatorStack：*
outputList: 4 2 + 3

• 字符遍歷結束，operatorStack依此出棧加入outputList，此時狀態(tài)：

operatorStack：空
outputList: 4 2 + 3 *

3.4 詳細的代碼實現(xiàn)

按上述邏輯設計后，具體代碼實現(xiàn)如下：

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)) // 如果是數(shù)字，直接輸出
        {
            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)

后綴表達式的求解非常簡單。首先準備一個棧用來存放數(shù)字，然后逐個讀取表達式的每個部分。如果是數(shù)字，就壓入棧；如果是操作符，就從棧中彈出對應的操作數(shù)進行計算，然后將結果壓回棧。計算完成后，棧里剩下的最后一個數(shù)字就是表達式的結果。
以下是具體的代碼實現(xiàn)：

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)) // 如果是數(shù)字，壓入棧
        {
            stack.Push(number);
        }
        else // 如果是操作符
        {
            double b = stack.Pop(); // 彈出第二個操作數(shù)
            double a = stack.Pop(); // 彈出第一個操作數(shù)
            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("除數(shù)不能為零");
                    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#語言實現(xiàn)了一個簡單的表達式解析器。我們首先介紹了中綴表達式和后綴表達式的基本概念，然后詳細討論了如何將中綴表達式轉換為后綴表達式，以及如何對后綴表達式進行求值。這種方法不僅易于理解和實現(xiàn)，而且在性能上也非常高效，特別適合初學者學習和實踐。

轉自https://www.cnblogs.com/luojin765/p/19130514