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

花了2個小時寫的這個解釋器還是比較簡單的，僅僅能夠做四則運(yùn)算?，F(xiàn)在還不支持括號，以及一元運(yùn)算符，比如負(fù)號運(yùn)算符。源代碼可以在這里下載：http://files.cnblogs.com/yinyueyouge/Arithemic.7z

運(yùn)行的主界面如下：

解釋器也能夠判斷非法的輸入：

現(xiàn)在這個解釋器還非常原始。若是有 bug 發(fā)現(xiàn)，請?zhí)崾境鰜?，我會更正。：?/P>

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

一、輸入和輸出

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

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

整個程序可以分為兩個部分：

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

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

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

二、截取單元指令 (Tokenize)

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

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

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

internal abstract class Token
{
} 

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

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

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

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

Op 和 Priority 是 2 個 enum:

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

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

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

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

我們定義了個緩沖 buffer，用來存儲已經(jīng)掃描到的數(shù)字。若是遇到了一個非數(shù)字，就把緩沖區(qū)所有的存儲的字節(jié)轉(zhuǎn)變成 double 類型，然后保存下來。值得注意的是，對小數(shù)點(diǎn)的處理。若是緩沖區(qū)里面已經(jīng)存在了一個小數(shù)點(diǎn)，遇到一個新的小數(shù)點(diǎn)就應(yīng)該拋出錯誤。

每當(dāng)掃描到一個操作符，比如 +, –, *, /，就把他們當(dāng)作一個操作符存儲起來。這里要注意的是，數(shù)字的正負(fù)號其實(shí)是一個一元操作符，是何數(shù)字分開保存的。

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

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

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

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

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

從最簡單的情況開始考慮：分析 1 + 2 + 3 + 4

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

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

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

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

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

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

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

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

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

插入操作符的代碼實(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 怎么處理呢？ 這個很簡單，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é)果就很簡單了，用線性遞歸即可。

求值（根）

若是遇到 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、支持一元操作符 - 和 +，它們將具有最高優(yōu)先權(quán)

2、支持括號。

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

【編輯推薦】

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