如何解析一個公式在C＃中建立一棵樹？

Question

如果我有一個公式：

A = 2+3*5-6/3+2 

我怎麼能建立的公式與節點的一棵樹，那麼我可以很容易地根據自下而上的樹，從左到右計算結果。

有人請提供所需解析器或一些參考的樣本？

Answer 1

有到分析許多可能的策略。

如果你想自己編寫解析代碼，那麼一個好的策略是Recursive descent parser。這並不難，因爲我自己寫了一個C＃語言。

如果您想使用解析器生成器工具，您可以使用傳統的GNU flex/bison組合或google的「C＃解析器生成器」來查找C＃，因此您不必使用C編寫。這將生成一個LALR parser。

Answer 2

如果只是算術，you can leverage javascript within C# to "eval" the string。如果你想構建一個合適的解析器，你需要創建一個語法，從該語法生成​​一個解析器，然後構建一個解釋器來處理解析器的輸出。該GOLD Parsing System是非常有用的任務，並有.NET engines, including C#。其他選項包括ANTLR Parser Generator和LEX and YACC。

如果你真的想推出自己的產品，那裏有很多資源。黃金解析系統頁面其實有很多的信息，它已經：

• Left-to-Right Derivation Parsing
• Deterministic Finite Automata

等等

Answer 3

如果是簡單的數學表達式，那麼一種方法是將其轉換爲反向波蘭表示法。在這種表示法中，計算表達式是相當容易的，因爲表示法將樹「線性化」（進入堆棧）。然後真正的任務解析並轉換成RPN符號（這實際上很容易）。

[http://en.wikipedia.org/wiki/Reverse_Polish_notation#Example]

曾經使用RPN，因爲它是很容易計算的非常古老的計算器。