今天下午用 C# 写了一个简单的四则算术解释器 （Interpreter）。该解释器主要有两个功能：一是能够进行基本的四则运算，也即加减乘除；二是能够检测输入的语法错误，对于不合法的运算指令会提示错误以及给出错误的地方。晚上于是写这篇博文把思考的过程记录下来。
按：这是以前遇到的一个微软技术面试题，当时觉得比较麻烦，要涉及到使用 树 tree 等数据结构，所以一直保留在脑海中。今天下午碰巧拿到了传说中的 Dragon Book，于是尝试自己动手写写看。
花了2个小时写的这个解释器还是比较简单的，仅仅能够做四则运算。现在还不支持括号，以及一元运算符，比如负号运算符。源代码可以在这里下载：
附件:
Arithemic.rar 运行的主界面如下：
附件:
image_2.png 解释器也能够判断非法的输入：
附件:
image_4.png 现在这个解释器还非常原始。若是有 bug 发现，请提示出来，我会更正。：）
现在来解说下这个解释器的原理。
一、输入和输出输入是一个用字符串表达的四则运算，比如 1 + 2 * 3 。目的是试图去理解这个字符串表达的运算指令，然后计算出结果 7。之所以是一个解释器 Interpreter，而不是一个编译器 Compiler，是因为程序是去理解指令并且执行指令，而不是把指令编译成机器代码来运行；后者是编译器的目标。
在解释的过程中，要能够分辨出不合法的指令：比如非法的字符 abc，非法的数字 2.3.1.4，非法的运算指令 2 * + 3，还有等等。
整个程序可以分为两个部分：
第一个部分，是截取输入字符串，然后返回单元指令。比如，对于指令 1 + 2 * 3 – 4 / 5，就需要被分解成如下所示的单元指令集：
附件:
image_6.png 第二个部分，是把单元指令集（上图橙色包含部分）组成一个树结构，称之为 Abstract Syntax Tree。按照将来需要解释的顺序，优先执行的指令会放在树的叶的位置，最后执行的指令会是树的根 Root。
附件:
image_8.png 在上图所示的 Abstract Syntax Tree 中，最先执行的指令是位于树上最深的子树，也就是 * ，然后是第二级的 + 和 / ，最后执行的位于根的指令 – 。
二、截取单元指令 (Tokenize)因为程序比较简单，只有 2 种单元指令：NumToken 和 OpToken。
我定义了一个基本类，叫做 Token，然后 NumToken 和 OpToken 继承了该基本类。
Class Token：什么也没有，暂时是空壳子。
- internal abstract class Token
- {
- }
Class NumToken: 表述一个数。
- internal sealed class NumToken : Token
- {
- public double Value { get; }
- }
Class OpToken: 表述一个运算符。
- 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 类来实现的。这个类是 internal sealed，因为外界不需要知道它的存在。Tokenizer 会被 Intepreter 类所使用。
- internal sealed class Tokenizer
- {
- public Token[] Parse(string value);
- }
在 Parse 函数里面，扫描输入字符串，从第一个字符开始，一直到最后一个字符。空白字符会被忽略掉。
我们定义了个缓冲 buffer，用来存储已经扫描到的数字。若是遇到了一个非数字，就把缓冲区所有的存储的字节转变成 double 类型，然后保存下来。值得注意的是，对小数点的处理。若是缓冲区里面已经存在了一个小数点，遇到一个新的小数点就应该抛出错误。
每当扫描到一个操作符，比如 +, –, *, /，就把他们当作一个操作符存储起来。这里要注意的是，数字的正负号其实是一个一元操作符，是何数字分开保存的。
遇到其他没有定义的字符，就直接抛出错误。
