# C# - C# 中的一種分裂與合并表達式分析器 作者?[Vassili Kaplan](https://msdn.microsoft.com/zh-cn/magazine/mt149362?author=Vassili+Kaplan)?| 2015 年 10 月 | 獲取代碼：?[C#](https://msdn.microsoft.com/zh-cn/magazine/mt573716.aspx#)[VB](https://msdn.microsoft.com/zh-cn/magazine/mt573716.aspx#) 我曾經在《CVu 期刊》的 2015 年 5 月和 7 月的版次上發表過一種用于分析 C++ 中數學表達式的新算法（請參閱“參考”中的第 1 項和第 2 項）。我用了兩篇文章來闡述這種新算法，因為一位機敏的讀者 Silas S. Brown 在第一個算法實現中發現了一個 Bug，所以我不得不對其做些修改。衷心感謝這位讀者，這種算法變得更成熟了。從那以后，我還修正了一些較小的 Bug。如今我打算在 C# 中提供一種校正過的算法實現。 編寫代碼來分析一個數學表達式不太可能，但是用于此算法中的技術也可以應用到其他方案中，比如分析非標準的字符串。使用這種算法，還可以很輕松地定義新函數來做任何你想做的事情（例如，發出 Web 請求來訂購一份披薩）。通過小幅的調整，還可以為新自定義的腳本語言創建你自己的 C# 編譯器。而且，你可能會發現它本身就是一種很有趣的算法。 Edsger Dijkstra 算法，發表于 50 多年前的 1961 年，它常用于分析數學表達式（請參閱“參考”中的第 3 項）。不過有一種替代算法也挺好，盡管有著同樣的時間復雜度，但我個人認為它更易于實現和擴展。 請注意，對于函數工廠實現，我打算使用“虛擬構造函數”用語。此用語是由 James Coplien 引入 C++ 中的（請參閱“參考”中的第 4 項）。我希望你們也將能夠在 C# 世界里發現其使用樂趣。 ## 分裂與合并算法 圖 1?中的演示程序闡明了用以分析數學表達式的分裂與合并算法。 ? 圖 1 分裂與合并算法的演示運行 這種算法由兩個步驟組成。在第一步中，包含表達式的字符串分裂為一列“存儲單元”對象，其中每個“存儲單元”定義如下： ~~~ class Cell { ? internal Cell(double value, char action) ? { ??? Value = value; ??? Action = action; ? } ? internal double Value? { get; set; } ? internal char?? Action { get; set; } } ~~~ 此操作是一個可以是任何數學運算符的單一字符：“*”（乘）、“/”（除）、“+”（加）、“-”（減）或“^”（冪），或是一個表示表達式結尾的特殊字符，我將其硬編碼為“)”。 位于這列要合并的存儲單元中的最后一個元素總是有一個特殊的操作“)”，也就是沒有操作，不過可以使用任何其他符號或一個圓括號代替。 在第一步中，表達式分裂為標記，然后又轉換為存儲單元。所有標記均由一個數學表達式或一個圓括號分隔開。標記可以是一個實數或者是一個帶有函數名稱的字符串。后來定義的 ParserFunction 類負責要分析的字符串中的所有函數，或用于將一個字符串分析為一個數字。它也許會遞歸地調用整體字符串分析算法。如果要分析的字符串中沒有函數和圓括號，遞歸也將不存在。 在第二步中，將所有存儲單元合并在一起。我們首先來看第二步，因為它比第一步更加直白明確。 ## 合并一列存儲單元 此列存儲單元根據操作的優先級逐一合并，即數學運算符。這些優先級的計算如下： ~~~ static int GetPriority(char action) { ? switch (action) { ??? case '^': return 4; ??? case '*': ??? case '/': return 3; ??? case '+': ??? case '-': return 2; ? } ? return 0; } ~~~ 當且僅當左邊存儲單元的操作優先級不低于其相鄰的右邊存儲單元的操作優先級時，可以合并兩個存儲單元。 ~~~ static bool CanMergeCells(Cell leftCell, Cell rightCell) { ? return GetPriority(leftCell.Action) >= GetPriority(rightCell.Action); } ~~~ 合并存儲單元意味著將左邊存儲單元的操作應用到左右兩邊存儲單元的值。新的存儲單元將會有與右邊存儲單元相同的操作，如圖 2?所示。 圖 2 合并存儲單元的方法 ~~~ static void MergeCells(Cell leftCell, Cell rightCell) { ? switch (leftCell.Action) ? { ??? case '^': leftCell.Value = Math.Pow(leftCell.Value, rightCell.Value); ????? break; ??? case '*': leftCell.Value *= rightCell.Value; ????? break; ??? case '/': leftCell.Value /= rightCell.Value; ????? break; ??? case '+': leftCell.Value += rightCell.Value; ????? break; ??? case '-': leftCell.Value -= rightCell.Value; ????? break; ? } ? leftCell.Action = rightCell.Action; } ~~~ 例如，合并“存儲單元 (8, ‘-’)”和“存儲單元 (5, ‘+’)”將會產生新的“存儲單元 (8 – 5, ‘+’)”，即“存儲單元 (3, ‘+’)”。 但是，如果由于左邊存儲單元的優先級低于右邊存儲單元而導致兩個存儲單元無法合并，此時會出現什么情況？ 接下來出現的情況是臨時移動到其相鄰的右邊存儲單元以嘗試與相鄰的存儲單元（以及更多單元）一起遞歸地將其合并。只要右邊存儲單元和其相鄰的存儲單元合并，我就立即返回到原來的左邊存儲單元，并嘗試和新創建的右邊存儲單元一起重新將其合并，如圖 3?所示。 圖 3 合并一列存儲單元 ~~~ static double Merge(Cell current, ref int index, List<Cell> listToMerge, ??????????????????? bool mergeOneOnly = false) { ? while (index < listToMerge.Count) ? { ??? Cell next = listToMerge[index++]; ??? while (!CanMergeCells(current, next)) ??? { ????? Merge(next, ref index, listToMerge, true /* mergeOneOnly */); ??? } ??? MergeCells(current, next); ??? if (mergeOneOnly) ??? { ????? return current.Value; ??? } ? } ? return current.Value; } ~~~ 請注意，這種方法是從外部調用的，其 mergeOneOnly 參數設置為 False，因此在完成整個合并之前不會返回。相反，當遞歸地調用該合并方法時（即由于優先級問題，左右兩邊存儲單元無法合并時），mergeOneOnly 將設置為 True，因為我想在 MergeCells 方法中完成一個實際合并后，就立刻返回到原來的位置。 還需要注意從該“合并”方法返回的值是表達式的實際值。 ## 將一個表達式分裂為一列存儲單元 此算法的第一部分是將一個表達式分裂為一列存儲單元。在此步驟中，不考慮數學運算符的優先次序。首先，表達式分裂為一列標記。所有標記均由任何數學運算符或者由一個左括號或右括號分隔開。圓括號可能（但不是必須）有相關聯的函數，例如，“1- sin(1-2)”具有相關聯的函數，而“1- (1-2)”則沒有。 首先，讓我們來看一下當沒有函數或圓括號而在它們之間僅有一個包含實數和數學運算符的表達式時，將會出現什么情況。在這種情況下，我只創建了由一個實數和一個后續的操作組成的存儲單元。例如，分裂“3-2*4”就會產生一個由 3 個存儲單元組成的列表： ~~~ Split (“3-2*4”) = { Cell(3, ‘-’), Cell(2, ‘*‘), Cell(3, ‘)’) } ~~~ 最后一個存儲單元總是有一個特殊的 END_ARG 操作，我將其定義為： ~~~ const char END_ARG = ')'; ~~~ 它可以更改為任何其他內容，但是在該情況下同樣必須考慮相應的左括號 START_ARG，我將其定義為： ~~~ const char START_ARG = '('; ~~~ 在圓括號中，如果其中一個標記是函數或表達式，則整個分裂與合并算法將使用遞歸來應用到標記。例如，如果表達式是“(3-1)-1”，則圓括號中的整個算法將先應用到表達式： ~~~ Split(“(3-1)-1”) = Split( “[SplitAndMerge(“3-1”)] - 1”) = { Cell(2, ‘-’), Cell(1, ‘)’) } ~~~ 執行分裂的函數是 LoadAndCalculate，如圖 4?所示。 圖 4 LoadAndCalculate 方法 ~~~ public static double LoadAndCalculate(string data, ref int from, char to = END_LINE) { ? if (from >= data.Length || data[from] == to) ? { ??? throw new ArgumentException("Loaded invalid data: " + data); ? } ? List<Cell> listToMerge = new List<Cell>(16); ? StringBuilder item = new StringBuilder(); ? do // Main processing cycle of the first part. ? { ??? char ch = data[from++]; ??? if (StillCollecting(item.ToString(), ch, to)) ??? { // The char still belongs to the previous operand. ????? item.Append(ch); ????? if (from < data.Length && data[from] != to) ????? { ??????? continue; ????? } ??? } ??? // I am done getting the next token. The getValue() call below may ??? // recursively call loadAndCalculate(). This will happen if extracted ??? // item is a function or if the next item is starting with a START_ARG '(.' ??? ParserFunction func = new ParserFunction(data, ref from, item.ToString(), ch); ??? double value = func.GetValue(data, ref from); ??? char action = ValidAction(ch) ? ch ??????????????????????????????? ??: UpdateAction(data, ref from, ch, to); ??? listToMerge.Add(new Cell(value, action)); ??? item.Clear(); ? } while (from < data.Length && data[from] != to); ? if (from < data.Length && (data[from] == END_ARG || data[from] == to)) ? { // This happens when called recursively: move one char forward. ? from++; ? } ? Cell baseCell = listToMerge[0]; ? int index = 1; ? return Merge(baseCell, ref index, listToMerge); } ~~~ LoadAndCalculate 方法會將所有存儲單元添加到 listToMerge 列表，然后調用分析算法的第二部分，即合并函數。StringBuilder 項將保留當前標記，當從表達式的字符串中讀取字符后，StringBuilder 項就會立刻將字符逐一地添加到標記中。 StillCollecting 方法檢查是否仍在收集用于當前標記的字符。如果當前字符為 END_ARG 或者任何其他特殊的“to”字符（比如逗號，如果分析參數由逗號分隔；稍后我將使用冪函數來舉一個這樣的示例），則不會是這種情況。另外，如果當前字符是一個有效操作或 START_ARG，將不再收集標記： ~~~ static bool StillCollecting(string item, char ch, char to) { ? char stopCollecting = (to == END_ARG || to == END_LINE) ? ???????????????????????? END_ARG : to; ? return (item.Length == 0 && (ch == '-' || ch == END_ARG)) || ??????? !(ValidAction(ch) || ch == START_ARG || ch == stopCollecting); } static bool ValidAction(char ch) { ? return ch == '*' || ch == '/' || ch == '+' || ch == '-' || ch == '^'; } ~~~ 我知道只要我獲得在 ValidAction 方法中描述的數學運算符，或者由 START_ARG 或 END_ARG 常數定義的圓括號后，就會立刻結束收集當前標記。還有一種關于“-”標記的特殊情況，該標記用來表示以負號開頭的數字。 在分裂步驟的結尾，通過對整個算法求值的遞歸調用，刪除圓括號中的所有子表達式和所有函數調用。但是這些遞歸調用產生的操作總是帶有 END_ARG 操作，如果計算表達式不在要求值的表達式的結尾，這些操作在全局表達式范圍內都將是錯誤的。這就是在每次遞歸調用后操作需要進行更新的原因，比如： ~~~ char action = ValidAction(ch) ? ch ??????????????????????????????? : UpdateAction(data, ref from, ch); ~~~ 圖 5?中 updateAction 方法的代碼。 圖 5 更新操作的方法 ~~~ static char UpdateAction(string item, ref int from, char ch, char to) { ? if (from >= item.Length || item[from] == END_ARG || item[from] == to) ? { ??? return END_ARG; ? } ? int index = from; ? char res = ch; ? while (!ValidAction(res) && index < item.Length) ? { // Look to the next character in string until finding a valid action. ??? res = item[index++]; ? } ? from = ValidAction(res) ? index ????????????????????????? : index > from ? index - 1 ???????????????????????????????????????? : from; ? return res; } ~~~ 對提取標記的實際分析將包含在圖 4?的以下代碼中： ~~~ ParserFunction func = new ParserFunction(data, ref from, item.ToString(), ch); double value = func.GetValue(data, ref from); ~~~ 如果提取標記不是函數，該代碼將嘗試將其轉換為一個類似的替代函數。否則就會調用一個合適的、之前已注冊、可以輪流遞歸調用 LoadAndCalculate 方法的函數。 ## 用戶定義的函數和標準函數 我決定使用由 James Coplien 首次發表的虛擬構造函數用語來實現函數工廠（請參閱“參考”中的第 4 項）。在 C# 中，通常使用工廠方法來實現函數工廠（請參閱“參考”中的第 5 項），這種方法使用額外的工廠類來產生所需要的對象。不過 Coplien 的早期設計模式并不需要額外的工廠外層類，而是使用由同樣的類派生的實現成員 m_impl 即時構造新的對象來代替： ~~~ private ParserFunction m_impl; ~~~ 這種特殊的內部構造函數通過合適的類初始化該成員。創建的實現對象 m_impl 的實際類取決于輸入參數，如圖 6?所示。 圖 6 虛擬構造函數 ~~~ internal ParserFunction(string data, ref int from, string item, char ch) { ? if (item.Length == 0 && ch == Parser.START_ARG) ? { ??? // There is no function, just an expression in parentheses. ??? m_impl = s_idFunction; ??? return; ? } ? if (m_functions.TryGetValue(item, out m_impl)) ? { ??? // Function exists and is registered (e.g. pi, exp, etc.). ??? return; ? } ? // Function not found, will try to parse this as a number. ? s_strtodFunction.Item = item; ? m_impl = s_strtodFunction; } ~~~ 使用字典來保留所有分析器函數。此字典可以將函數的字符串名稱（比如“sin”）映射到實現此函數的實際對象： ~~~ private static Dictionary<string, ParserFunction> m_functions = ????? new Dictionary<string, ParserFunction>(); ~~~ 通過在基本 ParserFunction 類上調用以下方法，分析器的用戶可以添加任意多的函數： ~~~ public static void AddFunction(string name, ParserFunction function) { ? m_functions[name] = function; } ~~~ GetValue 方法在創建的 ParserFunction 上調用，但實際工作在實現函數中完成，這將會取代基類的求值方法： ~~~ public double GetValue(string data, ref int from) { ? return m_impl.Evaluate(data, ref from); } protected virtual double Evaluate(string data, ref int from) { ? // The real implementation will be in the derived classes. ? return 0; } ~~~ 函數實現類派生自 ParserFunction 類，將不會在圖 6?中使用內部構造函數。他們將改用基類的以下構造函數： ~~~ public ParserFunction() { ? m_impl = this; } ~~~ 在圖 6?中，兩個特殊的“標準”函數用在 ParserFunction 構造函數中： ~~~ private static IdentityFunction s_idFunction = new IdentityFunction(); private static StrtodFunction s_strtodFunction = new StrtodFunction(); ~~~ 第一個是標識函數，將調用該函數來分析無關聯函數的圓括號中的任何表達式： ~~~ class IdentityFunction : ParserFunction { ? protected override double Evaluate(string data, ref int from) ? { ??? return Parser.LoadAndCalculate(data, ref from, Parser.END_ARG); ? } } ~~~ 第二個函數是“catchall”，當沒有發現對應于最后一個提取標記的函數時會調用此函數。當提取標記既不是實數也不是實現的函數時，就會出現這種情況。在后一種情況下，將引發異常： ~~~ class StrtodFunction : ParserFunction { ? protected override double Evaluate(string data, ref int from) ? { ??? double num; ??? if (!Double.TryParse(Item, out num)) { ????? throw new ArgumentException("Could not parse token [" + Item + "]"); ??? } ??? return num; ? } ? public string Item { private get; set; } } ~~~ 用戶可以實現所有其他函數；最簡單的是 pi 函數： ~~~ class PiFunction : ParserFunction { ? protected override double Evaluate(string data, ref int from) ? { ??? return 3.141592653589793; ? } } ~~~ 更典型的實現是 exp 函數: ~~~ class ExpFunction : ParserFunction { ? protected override double Evaluate(string data, ref int from) ? { ??? double arg = Parser.LoadAndCalculate(data, ref from, Parser.END_ARG); ??? return Math.Exp(arg); ? } } ~~~ 之前我說過將使用冪函數來舉一個需要兩個自變量（由逗號分隔）的示例。下面介紹如何編寫需要多個自變量（由自定義的分隔符分隔）的函數： ~~~ class PowFunction : ParserFunction { ? protected override double Evaluate(string data, ref int from) ? { ??? double arg1 = Parser.LoadAndCalculate(data, ref from, ','); ??? double arg2 = Parser.LoadAndCalculate(data, ref from, Parser.END_ARG); ??? return Math.Pow(arg1, arg2); ? } } ~~~ 任何數量的函數都可以從用戶代碼添加到算法中，比如： ~~~ ParserFunction.AddFunction("pi",? new PiFunction()); ParserFunction.AddFunction("exp", new ExpFunction()); ParserFunction.AddFunction("pow", new PowFunction()); ~~~ ## 總結 如果 n 是表達式字符串中的字符數，則這里介紹的分裂與合并算法具有 O(n) 復雜度。之所以如此是因為在分裂步驟中僅讀取一次標記，并且在最差的情況下，合并步驟中將最多有 2(m - 1) – 1 個比較，其中 m 為第一步中創建的存儲單元的數量。 所以這種算法與 Dijkstra 算法有同樣的時間復雜度（請參閱“參考”中的第 3 項）。由于使用遞歸，因此與 Dijkstra 算法相比，這種算法稍微有一點劣勢。另一方面，恰恰由于遞歸，我相信分裂與合并算法更易于實現，并且通過自定義語法、函數和運算符，也更易于擴展。 ## 參考 1. V.Kaplan，“用于分析數學表達式的分離與合并算法，”*CVu*，27-2，2015 年 5月，[bit.ly/1Jb470l](http://bit.ly/1Jb470l) 2. V.Kaplan，“再論分裂與合并，”*CVu*，27-3，2015 年 7月，[bit.ly/1UYHmE9](http://bit.ly/1UYHmE9) 3. E.Dijkstra，Shunting-yard 算法，[bit.ly/1fEvvLI](http://bit.ly/1fEvvLI) 4. J.Coplien，“高級 C++ 編程樣式和用語”（第 140 頁），Addison-Wesley，1992 年 5. E.Gamma，R. Helm，R. Johnson 和 J. Vlissides，“設計模式： 可重復使用的面向對象的軟件元素”，Addison-Wesley 專業計算系列，1995 年 * * * Vassili Kaplan?*是一位前 Microsoft Lync 開發人員。他對 C# 和 C++ 編程充滿熱情。現居住于瑞士的蘇黎世，作為一名自由職業者供職于各銀行。你可以通過?[iLanguage.ch](http://ilanguage.ch/)*?與他聯系。