C#實例講解二叉樹原理與實現
按：這是以前遇到的一個微軟技術面試題，當時覺得比較麻煩，要涉及到使用 樹 tree 等數據結構，所以一直保留在腦海中。今天下午碰巧拿到了傳說中的 Dragon Book，于是嘗試自己動手寫寫看。
花了2個小時寫的這個解釋器還是比較簡單的，僅僅能夠做四則運算?，F在還不支持括號，以及一元運算符，比如負號運算符。源代碼可以在這里下載：http://files.cnblogs.com/yinyueyouge/Arithemic.7z
運行的主界面如下：
解釋器也能夠判斷非法的輸入：
現在這個解釋器還非常原始。若是有 bug 發現，請提示出來，我會更正。：）
現在來解說下這個解釋器的原理。
一、輸入和輸出
輸入是一個用字符串表達的四則運算，比如 1 + 2 * 3 。目的是試圖去理解這個字符串表達的運算指令，然后計算出結果 7。之所以是一個解釋器 Interpreter，而不是一個編譯器 Compiler，是因為程序是去理解指令并且執行指令，而不是把指令編譯成機器代碼來運行；后者是編譯器的目標。
在解釋的過程中，要能夠分辨出不合法的指令：比如非法的字符 abc，非法的數字 2.3.1.4，非法的運算指令 2 * + 3，還有等等。
整個程序可以分為兩個部分：
第一個部分，是截取輸入字符串，然后返回單元指令。比如，對于指令 1 + 2 * 3 – 4 / 5，就需要被分解成如下所示的單元指令集：
第二個部分，是把單元指令集（上圖橙色包含部分）組成一個樹結構，稱之為 Abstract Syntax Tree。按照將來需要解釋的順序，優先執行的指令會放在樹的葉的位置，最后執行的指令會是樹的根 Root。
在上圖所示的 Abstract Syntax Tree 中，最先執行的指令是位于樹上最深的子樹，也就是 * ，然后是第二級的 + 和 / ，最后執行的位于根的指令 – 。
二、截取單元指令 (Tokenize)
因為程序比較簡單，只有 2 種單元指令：NumToken 和 OpToken。
我定義了一個基本類，叫做 Token，然后 NumToken 和 OpToken 繼承了該基本類。
Class Token：什么也沒有，暫時是空殼子。
internal abstract class Token |
Class NumToken: 表述一個數。
internal sealed class NumToken : Token |
Class OpToken: 表述一個運算符。
internal sealed class OpToken : Token |
Op 和 Priority 是 2 個 enum:
internal enum Op : int |
截取的算法相對來說很簡單，是由 Tokenizer 類來實現的。這個類是 internal sealed，因為外界不需要知道它的存在。Tokenizer 會被 Intepreter 類所使用。
internal sealed class Tokenizer |
在 Parse 函數里面，掃描輸入字符串，從第一個字符開始，一直到最后一個字符?？瞻鬃址麜缓雎缘簟?/P>
我們定義了個緩沖 buffer，用來存儲已經掃描到的數字。若是遇到了一個非數字，就把緩沖區所有的存儲的字節轉變成 double 類型，然后保存下來。值得注意的是，對小數點的處理。若是緩沖區里面已經存在了一個小數點，遇到一個新的小數點就應該拋出錯誤。
每當掃描到一個操作符，比如 +, –, *, /，就把他們當作一個操作符存儲起來。這里要注意的是，數字的正負號其實是一個一元操作符，是何數字分開保存的。
遇到其他沒有定義的字符，就直接拋出錯誤。
三、創建 Abstract Syntax Tree
這里需要考慮到2個不同的正常情況：
1、不同級別的操作符：+和-的優先等級比較低，×和/的優先等級比較高
2、同級別的操作符，操作的順序。比如，+和-的優先順序是從左往右。
從最簡單的情況開始考慮：分析 1 + 2 + 3 + 4
首先，AST 樹是空的， Root = NULL。
當把 NumToken 1 插入樹的時候，簡單的設置該 Token 為根即可。
當把 OpToken + 插入樹的時候，我們就需要挪動樹，把 + 設置成根：
當把 NumToken 2 插入樹的時候，我們就把數字 2 插入樹的右側：
當把 OpToken + 插入樹的時候（同級別的操作符，順序是左到右），我們就需要把最新的 OpToken 設置成根，當前樹設置成新根的左側：
到這里為止，我們可以得出一個很重要的法則：插入一個新的操作符進入 AST 樹的時候，若是樹的根是一個操作符，并且和此新操作符同級，運算順序是由左至右的話，那么新的操作符會成為新的樹的根，現有的樹會成為新樹的左子樹。
實際上，整個解釋器的開發，遵從“啟發式 heuristic ”的原理。整個解釋的過程可以分解成一條條的“規則”，我們需要做的是把規則全部“找”出來，并且把規則制定的盡可能完善。
好了，回到剛才的分析上。假設要插入的操作符不是 +，而是一個優先權比較高的 * 呢？也就是，若是 1 + 2 * 3 的話，AST 會是什么樣子？
這種情況下，乘法運算符必須移動到樹的右子樹上，并且成為右子樹的根。原右子樹會成為新的右子樹的左子樹。
插入操作符的代碼實現如下：
if (token is OpToken) {
if (root.Token is OpToken && root.RightChild == null) {
throw new ParseFailureException(
"The expression '{0} {1}' is not a valid arithmetic expression.",
root.Token.ToString(),
token.ToString()
);
}
if (root.Token is NumToken) {
Syntax newRoot = new Syntax(token);
newRoot.LeftChild = root;
root = newRoot;
return newRoot;
}
if (root.Token is OpToken) {
// Compare prioirty of the two operators
OpToken token1 = (OpToken)token;
OpToken token2 = (OpToken)root.Token;
if (token1.Prioirty <= token2.Prioirty) {
Syntax newRoot = new Syntax(token1);
newRoot.LeftChild = root;
root = newRoot;
return newRoot;
}
if (token1.Prioirty > token2.Prioirty) {
root.RightChild = Append(root.RightChild, token);
return root;
}
}
插入數字 NumToken 怎么處理呢？ 這個很簡單，NumToken總是成為右子樹。代碼如下（這里用到了線性遞歸，可以換成用尾端遞歸來提高效率）：
if (token is NumToken) {
if (root.Token is OpToken) {
if (root.RightChild == null) {
Syntax newNode = new Syntax(token);
root.RightChild = newNode;
return root;
} else {
root.RightChild = this.Append(root.RightChild, token);
return root;
}
} else {
throw new ParseFailureException(
"The expression '{0} {1}' is not a valid arithmetic expression.",
root.Token.ToString(),
token.ToString()
);
}
}
四、求運算結果
當 AST 樹創建出來后，求運算結果就很簡單了，用線性遞歸即可。
求值（根）
若是遇到 NumToken，返回值
若是遇到 OpToken +，返回 求值（左子樹） + 求值（右子樹）
若是遇到 OpToken －，返回 求值（左子樹） - 求值（右子樹）
….
代碼如下：
private double Eval(Syntax root) {
if (root == null) {
return 0;
}
if (root.Token is NumToken) {
NumToken token1 = (NumToken)root.Token;
return token1.Value;
}
if (root.Token is OpToken) {
OpToken token1 = (OpToken)root.Token;
if (root.RightChild == null && root.LeftChild == null) {
throw new ParseFailureException(
"The expression '{0}' cannot be a value.",
root.Token.ToString()
);
} else {
double lvalue = this.Eval(root.LeftChild);
double rvalue = this.Eval(root.RightChild);
switch (token1.Value) {
case Op.Plus:
return lvalue + rvalue;
case Op.Minus:
return lvalue - rvalue;
case Op.Multiply:
return lvalue * rvalue;
case Op.Divide:
return lvalue / rvalue;
default:
throw new ParseFailureException(
"The expression '{0} {1} {2}' cannot be a value.",
root.LeftChild.ToString(),
root.Token.ToString(),
root.RightChild.ToString()
);
}
}
}
throw new ParseFailureException("Unrecognized token: " +
root.Token.ToString());
}后記：
這個解釋器還很原始。需要添加的功能有：
1、支持一元操作符 - 和 +，它們將具有最高優先權
2、支持括號。
3、支持變量，也即需要一個 Local Variable Table。。。
【編輯推薦】
