文章目录

一时兴起想到要写段有美感的代码（不过感觉没有实现这个目标嘛╮(╯_╰)╭），然后就想到要实现一下四则运算。
于是过了大概一个星期，写了三个版本。
第一版完全是我自己想到的思路，主要就是函数递归，遇到后面优先级高的情况就把后面的部分递归计算，否则就顺序计算下去。
第二版是按照当年数据结构课上教的方法写的，用了符号栈和数据栈作为辅助。
第三版是按照编译原理课语法分析的思路来写的，用的是LL(1)是语法，主要也是通过函数递归实现，但是和第一版不同的是各种情况分散在多个非终结符对应的函数中实现。
现在想到的就这三个，以后有新的想法会继续更新。
代码地址：http://t.cn/RyGzXB3

这里贴一段第二版的主要代码（这个版本的实现最简洁）

#用符号栈和数字栈实现
def calculate(list):#这里传入的list是处理后的算式，已经分离了数值和操作符
    list.append('@')#辅助符号‘@’
    i = 0
    nums,op=[],['@']#数字栈和符号栈
    while i < len(list):
        if type(list[i]) != type(''):#数值
            nums.append(list[i])
            i+=1
        elif op[-1] in '(@' and list[i] in ')@':#左右括号抵消，首尾‘@’抵消
            op.pop()
            i+=1
        elif op[-1]=='+' and list[i] in '+-)@':#先加
            nums.append(nums.pop()+nums.pop())
            op.pop()
        elif op[-1]=='-' and list[i] in '+-)@':#先减
            nums.append(-nums.pop()+nums.pop())
            op.pop()
        elif op[-1]=='*' and list[i] in '+-*/)@':#先乘
            nums.append(nums.pop()*nums.pop())
            op.pop()
        elif op[-1]=='/' and list[i] in '+-*/)@':#先除
            nums.append(1/nums.pop()*nums.pop())
            op.pop()
        else:#优先级更高，压入符号栈
            op.append(list[i])
            i+=1
    return nums[-1]