建站
咨詢(xún)
售后
建站咨詢(xún)
新聞中心
按：這是以前遇到的一個(gè)微軟技術(shù)面試題，當(dāng)時(shí)覺(jué)得比較麻煩，要涉及到使用 樹(shù) tree 等數(shù)據(jù)結(jié)構(gòu)，所以一直保留在腦海中。今天下午碰巧拿到了傳說(shuō)中的 Dragon Book，于是嘗試自己動(dòng)手寫(xiě)寫(xiě)看。
創(chuàng)新互聯(lián)公司是一家專(zhuān)業(yè)提供噶爾企業(yè)網(wǎng)站建設(shè),專(zhuān)注與網(wǎng)站建設(shè)、網(wǎng)站制作、H5技術(shù)、小程序制作等業(yè)務(wù)。10年已為噶爾眾多企業(yè)、政府機(jī)構(gòu)等服務(wù)。創(chuàng)新互聯(lián)專(zhuān)業(yè)網(wǎng)站建設(shè)公司優(yōu)惠進(jìn)行中。
花了2個(gè)小時(shí)寫(xiě)的這個(gè)解釋器還是比較簡(jiǎn)單的，僅僅能夠做四則運(yùn)算。現(xiàn)在還不支持括號(hào)，以及一元運(yùn)算符，比如負(fù)號(hào)運(yùn)算符。源代碼可以在這里下載：http://files.cnblogs.com/yinyueyouge/Arithemic.7z
運(yùn)行的主界面如下：
解釋器也能夠判斷非法的輸入：
現(xiàn)在這個(gè)解釋器還非常原始。若是有 bug 發(fā)現(xiàn)，請(qǐng)?zhí)崾境鰜?lái)，我會(huì)更正。：）
現(xiàn)在來(lái)解說(shuō)下這個(gè)解釋器的原理。
一、輸入和輸出
輸入是一個(gè)用字符串表達(dá)的四則運(yùn)算，比如 1 + 2 * 3 。目的是試圖去理解這個(gè)字符串表達(dá)的運(yùn)算指令，然后計(jì)算出結(jié)果 7。之所以是一個(gè)解釋器 Interpreter，而不是一個(gè)編譯器 Compiler，是因?yàn)槌绦蚴侨ダ斫庵噶畈⑶覉?zhí)行指令，而不是把指令編譯成機(jī)器代碼來(lái)運(yùn)行；后者是編譯器的目標(biāo)。
在解釋的過(guò)程中，要能夠分辨出不合法的指令：比如非法的字符 abc，非法的數(shù)字 2.3.1.4，非法的運(yùn)算指令 2 * + 3，還有等等。
整個(gè)程序可以分為兩個(gè)部分：
第一個(gè)部分，是截取輸入字符串，然后返回單元指令。比如，對(duì)于指令 1 + 2 * 3 – 4 / 5，就需要被分解成如下所示的單元指令集：
第二個(gè)部分，是把單元指令集（上圖橙色包含部分）組成一個(gè)樹(shù)結(jié)構(gòu)，稱(chēng)之為 Abstract Syntax Tree。按照將來(lái)需要解釋的順序，優(yōu)先執(zhí)行的指令會(huì)放在樹(shù)的葉的位置，最后執(zhí)行的指令會(huì)是樹(shù)的根 Root。
在上圖所示的 Abstract Syntax Tree 中，最先執(zhí)行的指令是位于樹(shù)上最深的子樹(shù)，也就是 * ，然后是第二級(jí)的 + 和 / ，最后執(zhí)行的位于根的指令 – 。
二、截取單元指令 (Tokenize)
因?yàn)槌绦虮容^簡(jiǎn)單，只有 2 種單元指令：NumToken 和 OpToken。
我定義了一個(gè)基本類(lèi)，叫做 Token，然后 NumToken 和 OpToken 繼承了該基本類(lèi)。
Class Token：什么也沒(méi)有，暫時(shí)是空殼子。
Class NumToken: 表述一個(gè)數(shù)。
Class OpToken: 表述一個(gè)運(yùn)算符。
Op 和 Priority 是 2 個(gè) enum:
截取的算法相對(duì)來(lái)說(shuō)很簡(jiǎn)單，是由 Tokenizer 類(lèi)來(lái)實(shí)現(xiàn)的。這個(gè)類(lèi)是 internal sealed，因?yàn)橥饨绮恍枰浪拇嬖?。Tokenizer 會(huì)被 Intepreter 類(lèi)所使用。
在 Parse 函數(shù)里面，掃描輸入字符串，從第一個(gè)字符開(kāi)始，一直到最后一個(gè)字符?？瞻鬃址麜?huì)被忽略掉。
我們定義了個(gè)緩沖 buffer，用來(lái)存儲(chǔ)已經(jīng)掃描到的數(shù)字。若是遇到了一個(gè)非數(shù)字，就把緩沖區(qū)所有的存儲(chǔ)的字節(jié)轉(zhuǎn)變成 double 類(lèi)型，然后保存下來(lái)。值得注意的是，對(duì)小數(shù)點(diǎn)的處理。若是緩沖區(qū)里面已經(jīng)存在了一個(gè)小數(shù)點(diǎn)，遇到一個(gè)新的小數(shù)點(diǎn)就應(yīng)該拋出錯(cuò)誤。
每當(dāng)掃描到一個(gè)操作符，比如 +, –, *, /，就把他們當(dāng)作一個(gè)操作符存儲(chǔ)起來(lái)。這里要注意的是，數(shù)字的正負(fù)號(hào)其實(shí)是一個(gè)一元操作符，是何數(shù)字分開(kāi)保存的。
遇到其他沒(méi)有定義的字符，就直接拋出錯(cuò)誤。
三、創(chuàng)建 Abstract Syntax Tree
這里需要考慮到2個(gè)不同的正常情況：
1、不同級(jí)別的操作符：+和-的優(yōu)先等級(jí)比較低，×和/的優(yōu)先等級(jí)比較高
2、同級(jí)別的操作符，操作的順序。比如，+和-的優(yōu)先順序是從左往右。
從最簡(jiǎn)單的情況開(kāi)始考慮：分析 1 + 2 + 3 + 4
首先，AST 樹(shù)是空的， Root = NULL。
當(dāng)把 NumToken 1 插入樹(shù)的時(shí)候，簡(jiǎn)單的設(shè)置該 Token 為根即可。
當(dāng)把 OpToken + 插入樹(shù)的時(shí)候，我們就需要挪動(dòng)樹(shù)，把 + 設(shè)置成根：
當(dāng)把 NumToken 2 插入樹(shù)的時(shí)候，我們就把數(shù)字 2 插入樹(shù)的右側(cè)：
當(dāng)把 OpToken + 插入樹(shù)的時(shí)候（同級(jí)別的操作符，順序是左到右），我們就需要把最新的 OpToken 設(shè)置成根，當(dāng)前樹(shù)設(shè)置成新根的左側(cè)：
到這里為止，我們可以得出一個(gè)很重要的法則：插入一個(gè)新的操作符進(jìn)入 AST 樹(shù)的時(shí)候，若是樹(shù)的根是一個(gè)操作符，并且和此新操作符同級(jí)，運(yùn)算順序是由左至右的話，那么新的操作符會(huì)成為新的樹(shù)的根，現(xiàn)有的樹(shù)會(huì)成為新樹(shù)的左子樹(shù)。
實(shí)際上，整個(gè)解釋器的開(kāi)發(fā)，遵從“啟發(fā)式 heuristic ”的原理。整個(gè)解釋的過(guò)程可以分解成一條條的“規(guī)則”，我們需要做的是把規(guī)則全部“找”出來(lái)，并且把規(guī)則制定的盡可能完善。
好了，回到剛才的分析上。假設(shè)要插入的操作符不是 +，而是一個(gè)優(yōu)先權(quán)比較高的 * 呢？也就是，若是 1 + 2 * 3 的話，AST 會(huì)是什么樣子？
這種情況下，乘法運(yùn)算符必須移動(dòng)到樹(shù)的右子樹(shù)上，并且成為右子樹(shù)的根。原右子樹(shù)會(huì)成為新的右子樹(shù)的左子樹(shù)。
插入操作符的代碼實(shí)現(xiàn)如下：
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;
}
}插入數(shù)字 NumToken 怎么處理呢？ 這個(gè)很簡(jiǎn)單，NumToken總是成為右子樹(shù)。代碼如下（這里用到了線性遞歸，可以換成用尾端遞歸來(lái)提高效率）：
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()
);
}
}四、求運(yùn)算結(jié)果
當(dāng) AST 樹(shù)創(chuàng)建出來(lái)后，求運(yùn)算結(jié)果就很簡(jiǎn)單了，用線性遞歸即可。
求值（根）
若是遇到 NumToken，返回值
若是遇到 OpToken +，返回 求值（左子樹(shù)） + 求值（右子樹(shù)）
若是遇到 OpToken －，返回 求值（左子樹(shù)） - 求值（右子樹(shù)）
….
代碼如下：
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());
}后記：
這個(gè)解釋器還很原始。需要添加的功能有：
1、支持一元操作符 - 和 +，它們將具有最高優(yōu)先權(quán)
2、支持括號(hào)。
3、支持變量，也即需要一個(gè) Local Variable Table。。。
【編輯推薦】
- C# 4.0新特性dynamic作用淺析
- Visual C# 2010新特性之dynamic類(lèi)型
- C#中對(duì)DatagridView的部分常用操作
名稱(chēng)欄目：C#實(shí)例講解二叉樹(shù)原理與實(shí)現(xiàn)
網(wǎng)址分享：http://www.5511xx.com/article/dpojchj.html
