使用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执行完指令后,就得到结果了,计算的全过程也就此结束了。

发表评论

电子邮件地址不会被公开。 必填项已用*标注