使用python撸一个支持四则运算的计算器

代码地址：https://github.com/MakDon/toy_calculator
效果如下：


实现的功能为读入一个字符串格式的算式，然后输出数字格式的结果。

计算器主要包括如下几个部分：

1. 词法分析器
2. 语法分析器
3. 伪指令生成器
4. 伪VM

词法分析器

词法分析器对输入的文本进行分析，输出为一串token。如输入为

"1 + 2 + 3 + 5 + 7"

则输出为：

<class 'list'>:
 [['NUMBER', '1'], ['+', '+'], ['NUMBER', '2'], ['+', '+'], 
['NUMBER', '3'], ['+','+'], ['NUMBER', '5'], ['+', '+'], ['NUMBER', '7']]

此处实现的基本思路是，使用正则对字符串从头进行匹配，若匹配到结果，则截取为一个token，然后继续匹配；若一直匹配不到结果，则认为输入的串存在词法错误。使用的正则分别如下：

 {
    "NUMBER": r"([0-9]+\.)?[0-9]+",# 数字
    "+": r"\+",# 加号
    "-": r"-",# 减号
    "*": r"\*",# 乘号
    "/": r"/",# 除号
    "LBRA": r"\(",# 左括号
    "RBRA": r"\)",# 右括号
    "SEPARATOR": r"( |\n)"# 分隔符，此处使用空格与换行
}

 

语法分析器：

语法分析，是把词法分析器生成的token串，转换为抽象语法树（Abstract Syntax Tree，AST）。上节的token串生成的AST如下：

在此计算器中，我选择的是自顶向下的生成方式。四则运算语法如下：

Expr      ->    Term ExprTail
ExprTail  ->    + Term ExprTail
          |     - Term ExprTail
          |     null

Term      ->    Factor TermTail
TermTail  ->    * Factor TermTail
          |     / Factor TermTail
          |     null

Factor    ->    (Expr)
          |     num

reference:https://zhuanlan.zhihu.com/p/24035780

其中各个符号的含义与消除左递归的推导过程详见《编译原理》。

伪指令生成

上一节的语法分析器中，生成得到了AST。这一步的作用，则是把上一节得到的树，转化为顺序的指令序列。此处使用了递归的深度遍历的方法，此处生成的每条指令包括如下两个部分：

1. 操作：操作可以为入栈，或者是运算（加减乘除）。
2. 操作数：可选，当操作为入栈时，操作数是被入栈的数值。当操作为运算时为None。

上一节的AST可以生成如下指令：

[(PUSH,1), (PUSH,2), (+,None), (PUSH,3), (+,None), (PUSH,5), (+,None), (PUSH,7), (+,None)]

 

伪VM

伪VM的作用，为自行上一节生成的伪指令，最后返回结算的结果。伪VM维护一个栈，用于数值计算。获得指令序列后，开始顺序执行指令。当指令的操作为入栈时，把指令的操作数push入栈顶。当指令为运算时，pop出栈顶的两个数字，进行指令的运算，然后把运算结果push回栈顶。在指令序列执行完后，伪VM的栈内应有且只有一个数值，为计算结果。

在伪VM执行完指令后，就得到结果了，计算的全过程也就此结束了。