首页 > 代码库 > [体验编译原理]编写简易计算器
[体验编译原理]编写简易计算器
Demo: CaculationTest
前言
有想过自己写一个计算器么？输入一些数学表达式就能自己计算解析生成结果。
如果没有，可以现在开始想想，也许你会发现自己计算要不了几秒钟的表达式，让程序计算却没这么简单。
假定
为了便于理解，我们现在简化需求，数据类型只有整数，运算符只有加减乘除，没有括号。运行结果如图所示：
解析过程
逐个分析表达式字符串的每一个char，将其解析为一系列的token。然后根据token代表的不同含义进行相应的操作，直到计算出最终结果。
（本例中并没有全部解析完token，再遍历token，而是边解析边进行操作。这样做效率稍微高一点，但不能直接查看解析出来的全部token。）
这和我们阅读也比较接近：我们从左往右依次读取信息，读的过程中，我们会根据上下文即前后组成，形成一定的语义，如“其实不忍”，你可能会理解为”他实在不忍心“，或者理解为”他其实是不忍心的“，这得依照你对上下文的理解去选择了。
对照刚才的比喻，可以得出，token是语义的基本组成，或者说对字符组成的一种抽象。程序中将token抽象为以下数据结构：
enum TokenType { Add,Sub, Mul,Div, Int, Start,End } class Token { public TokenType Type; public object Value; public Token(TokenType type , object value = http://www.mamicode.com/null) { Type = type; Value = value; } }
Token和表达式
Token必须解析为表达式才会有意义。有了表达式，我们才能计算出最终结果。一个表达式，是能表示明确意义的一个或一组token。
在C#中，我们有一元表达式，二元表达式；表达式中有不同的运算，如加减法；在此例中，所有的表达式都可以计算出某个值，而且表达式之间可以相互计算形成新的表达式，如”表达式（1*2）+表达式(2*3)”。基于此，有Expression类，也并不复杂：
abstract class Expression { public abstract int GetValue(); } class UnaryExpress : Expression { int _value; public UnaryExpress(int value) { _value = value; } public override int GetValue() { return _value; } } class BinaryExpression : Expression { TokenType _tokenType; int _left; int _right; public BinaryExpression(TokenType tokenType, Expression left, Expression right) { _tokenType = tokenType; _left = left.GetValue(); _right = right.GetValue(); } public override int GetValue() { switch (_tokenType) { case TokenType.Add: return _left + _right; case TokenType.Sub: return _left - _right; case TokenType.Mul: return _left * _right; case TokenType.Div: return _left / _right; default: throw new Exception("unexceptional token!"); } } }
此例中，并没有真正意义上的“一元表达式”，仅将数字看作它而已。二元表达式的值计算相对复杂，但类别也不多。
算法优先级
如果不算括号，恐怕对我们来说，用自己的“原始方式”解析表达式，最大的麻烦就是解决算法优先级的问题。
为什么“1+2*3” 不解析为1+2再乘以3呢，如何才能将其正确解析为2*3再和1相加呢？
首先我们需要顺序分析每个token, 表达式的解析顺序决定了最后的运算顺序，看下原代码中比较重要的这3个方法：
//解析加减 Expression ParseAddSub() { //左操作数为优先级较高的运算符 var l = ParseMulDiv(); while (_token.Type == TokenType.Add || _token.Type == TokenType.Sub) { var t = _token.Type; ParseToken(); var r = ParseMulDiv();//解析右操作数 l = new BinaryExpression(t, l, r); } return l; } //解析乘除 Expression ParseMulDiv() { var l = ParseUnary(); while (_token.Type == TokenType.Mul || _token.Type == TokenType.Div) { var t = _token.Type; ParseToken(); var r=ParseUnary(); l = new BinaryExpression(t, l, r); } return l; } //解析一元表达式（目前只有单个整数） Expression ParseUnary() { Expression ret = null; if (_token.Type == TokenType.Int) { ret= new UnaryExpress((int)_token.Value); } //解析完int后，移到下一个token处，即+-*/ ParseToken(); return ret; }
1*2+2*2，我们可以看作两个乘法表达式相加，所以，解析加法运算的左右操作符前，程序尝试读取其是否是乘法表达式。
如果是1+2*3呢，左操作符当乘法运算解析时，并没有匹配上，由最高优先级的一元表达式决定其值，返回1，所以左操作符就是1了，当解析到+时，程序尝 试解析右操作符，从优先级比加法高一级的乘除开始，往上搜索匹配。很明显，2*3命中了乘法表达式，计算出右操作数的结果后，再和1相加，结果就正确了。
练习
如果研究透了demo，可以尝试把括号，取模运算，一无表达式（正负号）。
扩展
在IL代码和LinqExpression API中，“表达式”，“二元表达式”，“赋值表达式”，“成员获取表达式（.运算）”等，都很常见，解析的表达后对应的操作也很多，新建实例，引用实 例，访问局部变量等，赋值等。有兴趣可以查看一下Dynamic Linq的原代码（后续章节中，我们会写一个简单易版的Dynamic Linq动态计算 IQueryable.Where(string)）。
[体验编译原理]编写简易计算器