按：這是以前遇到的一個(gè)微軟技術(shù)面試題，當(dāng)時(shí)覺得比較麻煩，要涉及到使用 樹 tree 等數(shù)據(jù)結(jié)構(gòu)，所以一直保留在腦海中。今天下午碰巧拿到了傳說中的 Dragon Book，于是嘗試自己動(dòng)手寫寫看。

花了2個(gè)小時(shí)寫的這個(gè)解釋器還是比較簡(jiǎn)單的，僅僅能夠做四則運(yùn)算?，F(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í)崾境鰜?，我?huì)更正。：）

現(xiàn)在來解說下這個(gè)解釋器的原理。

一、輸入和輸出

輸入是一個(gè)用字符串表達(dá)的四則運(yùn)算，比如 1 + 2 * 3 。目的是試圖去理解這個(gè)字符串表達(dá)的運(yùn)算指令，然后計(jì)算出結(jié)果 7。之所以是一個(gè)解釋器 Interpreter，而不是一個(gè)編譯器 Compiler，是因?yàn)槌绦蚴侨ダ斫庵噶畈⑶覉?zhí)行指令，而不是把指令編譯成機(jī)器代碼來運(yùn)行；后者是編譯器的目標(biāo)。

在解釋的過程中，要能夠分辨出不合法的指令：比如非法的字符 abc，非法的數(shù)字 2.3.1.4，非法的運(yùn)算指令 2 * + 3，還有等等。

整個(gè)程序可以分為兩個(gè)部分：

第一個(gè)部分，是截取輸入字符串，然后返回單元指令。比如，對(duì)于指令 1 + 2 * 3 – 4 / 5，就需要被分解成如下所示的單元指令集：

第二個(gè)部分，是把單元指令集（上圖橙色包含部分）組成一個(gè)樹結(jié)構(gòu)，稱之為 Abstract Syntax Tree。按照將來需要解釋的順序，優(yōu)先執(zhí)行的指令會(huì)放在樹的葉的位置，最后執(zhí)行的指令會(huì)是樹的根 Root。

在上圖所示的 Abstract Syntax Tree 中，最先執(zhí)行的指令是位于樹上最深的子樹，也就是 * ，然后是第二級(jí)的 + 和 / ，最后執(zhí)行的位于根的指令 – 。

二、截取單元指令 (Tokenize)

因?yàn)槌绦虮容^簡(jiǎn)單，只有 2 種單元指令：NumToken 和 OpToken。

我定義了一個(gè)基本類，叫做 Token，然后 NumToken 和 OpToken 繼承了該基本類。

Class Token：什么也沒有，暫時(shí)是空殼子。

internal abstract class Token
{
} 

Class NumToken: 表述一個(gè)數(shù)。

internal sealed class NumToken : Token
{
    public double Value { get; }
} 

Class OpToken: 表述一個(gè)運(yùn)算符。

internal sealed class OpToken : Token
{
    public Op Value { get; }
    public Prioirty Prioirty { get; }
}

Op 和 Priority 是 2 個(gè) enum:

internal enum Op : int
{
    Plus = '+',
    Minus = '-',
    Multiply = '*',
    Divide = '/'
}
internal enum Prioirty
{
    Lv2 = 2,
    Lv1 = 1,
    Lv0 = 0
} 

截取的算法相對(duì)來說很簡(jiǎn)單，是由 Tokenizer 類來實(shí)現(xiàn)的。這個(gè)類是 internal sealed，因?yàn)橥饨绮恍枰浪拇嬖?。Tokenizer 會(huì)被 Intepreter 類所使用。

internal sealed class Tokenizer
{
    public Token[] Parse(string value);
}
 

在 Parse 函數(shù)里面，掃描輸入字符串，從第一個(gè)字符開始，一直到最后一個(gè)字符。空白字符會(huì)被忽略掉。

我們定義了個(gè)緩沖 buffer，用來存儲(chǔ)已經(jīng)掃描到的數(shù)字。若是遇到了一個(gè)非數(shù)字，就把緩沖區(qū)所有的存儲(chǔ)的字節(jié)轉(zhuǎn)變成 double 類型，然后保存下來。值得注意的是，對(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ǔ)起來。這里要注意的是，數(shù)字的正負(fù)號(hào)其實(shí)是一個(gè)一元操作符，是何數(shù)字分開保存的。

遇到其他沒有定義的字符，就直接拋出錯(cuò)誤。

三、創(chuàng)建 Abstract Syntax Tree

這里需要考慮到2個(gè)不同的正常情況：

1、不同級(jí)別的操作符：+和-的優(yōu)先等級(jí)比較低，×和/的優(yōu)先等級(jí)比較高

2、同級(jí)別的操作符，操作的順序。比如，+和-的優(yōu)先順序是從左往右。

從最簡(jiǎn)單的情況開始考慮：分析 1 + 2 + 3 + 4

首先，AST 樹是空的， Root = NULL。

當(dāng)把 NumToken 1 插入樹的時(shí)候，簡(jiǎn)單的設(shè)置該 Token 為根即可。

當(dāng)把 OpToken + 插入樹的時(shí)候，我們就需要挪動(dòng)樹，把 + 設(shè)置成根：

當(dāng)把 NumToken 2 插入樹的時(shí)候，我們就把數(shù)字 2 插入樹的右側(cè)：

當(dāng)把 OpToken + 插入樹的時(shí)候（同級(jí)別的操作符，順序是左到右），我們就需要把最新的 OpToken 設(shè)置成根，當(dāng)前樹設(shè)置成新根的左側(cè)：

到這里為止，我們可以得出一個(gè)很重要的法則：插入一個(gè)新的操作符進(jìn)入 AST 樹的時(shí)候，若是樹的根是一個(gè)操作符，并且和此新操作符同級(jí)，運(yùn)算順序是由左至右的話，那么新的操作符會(huì)成為新的樹的根，現(xiàn)有的樹會(huì)成為新樹的左子樹。

實(shí)際上，整個(gè)解釋器的開發(fā)，遵從“啟發(fā)式 heuristic ”的原理。整個(gè)解釋的過程可以分解成一條條的“規(guī)則”，我們需要做的是把規(guī)則全部“找”出來，并且把規(guī)則制定的盡可能完善。

好了，回到剛才的分析上。假設(shè)要插入的操作符不是 +，而是一個(gè)優(yōu)先權(quán)比較高的 * 呢？也就是，若是 1 + 2 * 3 的話，AST 會(huì)是什么樣子？

這種情況下，乘法運(yùn)算符必須移動(dòng)到樹的右子樹上，并且成為右子樹的根。原右子樹會(huì)成為新的右子樹的左子樹。

插入操作符的代碼實(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總是成為右子樹。代碼如下（這里用到了線性遞歸，可以換成用尾端遞歸來提高效率）：

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 樹創(chuàng)建出來后，求運(yùn)算結(jié)果就很簡(jiǎn)單了，用線性遞歸即可。

求值（根）

若是遇到 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());
}

后記：

這個(gè)解釋器還很原始。需要添加的功能有：

1、支持一元操作符 - 和 +，它們將具有最高優(yōu)先權(quán)

2、支持括號(hào)。

3、支持變量，也即需要一個(gè) Local Variable Table。。。

【編輯推薦】

1. C# 4.0新特性dynamic作用淺析
2. Visual C# 2010新特性之dynamic類型
3. C#中對(duì)DatagridView的部分常用操作