表达式求值

╰半夏微凉° 2022-05-06 06:28 317阅读 0赞

今天把表达式求值给搞定吧。

问题：给你个表达式，有加减乘除和小括号，让算出结果。

我们假定计算式是正确的，并且不会出现除数为0等错误。

py大法好啊，在保证可读性的前提下能压到一共就三十多行代码。

其实能压到不到三十行，但是代码就不好看了。。。。

计算函数：

def getvalue(a, b, op):
        if op == "+":return a+b
        elif op == "-":return a-b
        elif op == "*":return a*b
        else:return a/b

出栈一个运算符，两个数值，计算，将结果入data用于之后计算

def process(data, opt):
        operator = opt.pop()
        num2 = data.pop()
        num1 = data.pop()
        data.append(getvalue(num1, num2, operator))

比较符号优先级：  
乘除运算优先级比加减高。

op1优先级比op2高返回True，否则返回False

def compare(op1, op2):
        return op1 in ["*","/"] and op2 in ["+","-"]

主函数：

基本思路：

处理每个数字为一个整数，处理每一项为一个单独的数字，把括号内处理为一个单独的数字。

把式子处理为只有整数、加减的式子再最后计算。

def calculate(s):
        data = []#数据栈
        opt = []#操作符栈
        i = 0  #表达式遍历的索引
        while i < len(s):
            if s[i].isdigit():  # 数字,入栈data
                start = i
                while i+1  < len(s) and s[i + 1].isdigit():
                    i += 1
                data.append(int(s[start: i + 1]))  # i为最后一个数字字符的位置
            elif s[i] == ")":  # 右括号，opt出栈,data出栈并计算，结果入data，直到左括号
                while opt[-1] != "(":
                    process(data,opt)#优先级高的一定先弹出
                opt.pop()  # 出栈的一定是左括号
            elif not opt or opt[-1] == "(":opt.append(s[i])#栈空，或栈顶为左括号，入opt
            elif s[i]=="(" or compare(s[i],opt[-1]):opt.append(s[i])#左括号或比栈顶优先级高，入
            else: #优先级不比栈顶高，opt出栈同时data出栈并计算，计算结果入data
                while opt and not compare(s[i], opt[-1]):
                    if opt[-1] == "(":break  #遇到左括号，停止计算
                    process(data, opt)
                opt.append(s[i])
            i += 1  #索引后移
        while opt:
            process(data, opt)
        print(data.pop())