四则运算表达式求值

思路阐明

应用双栈来实现——寄存数值的栈 nums 与寄存运算符的栈 ops.

算法步骤

1. 对原始表达式字符串 exp 进行预处理, 将其转为一个元素对应一个数值或运算符的列表 explist.
2. 遍历 explist , 每个元素顺次压入对应的栈中. 每次压入后, 判断以后两栈顶是否可进行乘除运算. 栈顶可进行乘除运算的充要条件是, ops 栈顶为 <*> ,</> 之一, 且 nums 中的元素比 ops 中的元素恰好多一个. 如果能够运算, 则运算, 并将运算后果压回 nums 中.
3. explist 遍历完之后, 所有乘除运算都已进行, 此时 ops 中只剩加法与减法, 接下来开始另一个循环, 始终运算即可. 最初 nums 中残余的惟一元素即为表达式的值.

代码

def operation(a, b, op: str):
    """
    计算一次运算的后果
    :param a: val
    :param b: val
    :param op: 运算符
    :return: val
    """if op =='+':
        return a+b
    elif op == '-':
        return a-b
    elif op == '*':
        return a*b
    elif op == '/':
        return a/b
    else:
        raise Exception('运算符不正确')


def exp_str2list(exp: str):
    """
    将表达式 exp:str 转成 list, 每个元素对应一个数 <num> 或运算符 <op>.
    已知 exp 是规范的四则运算表达式字符串.
    :param exp: str, 表达式
    :return: list
    """opset = {'+','-','*','/'}  # 运算符汇合
    flag = -1
    explist = list()
    for i, char in enumerate(exp):  # 对表达式字符串中的每个字符
        if char in opset:  # 若 char 是运算符
            explist.append(exp[flag+1:i])  # 上一个运算符到以后运算符两头为数字, 保留到 explist
            flag = i  # 更新 flag 到以后 op 地位
            explist.append(char)  # 以后 op 亦退出 explist
    explist.append(exp[flag+1:])
    return explist


def calculate_expression(exp: str):
    """
    表达式求值. 计算字符串 exp 所代表的表达式的值, 返回一个数值
        已知 exp 是规范的四则运算表达式字符串, 且不含括号.
    :param exp: str, 表达式
    :return: val
    """opset = {'+','-','*','/'}
    nums = list()  # 数栈
    ops = list()  # 运算符栈
    explist = exp_str2list(exp)
    print(explist)
    for e in explist:
        # e 入栈
        if e in opset:  # 若 e 是运算符
            ops.append(e)
        else:
            nums.append(eval(e))
        # 若 e 是优先级高的乘除法, 且
        # nums 与 ops 恰好匹配, 栈顶能够进行一次计算, 运算后果压入回 nums
        if ops and ops[-1] in {'*', '/'} and len(nums) == len(ops) + 1:
            op = ops.pop()
            y = nums.pop()
            x = nums.pop()
            nums.append(operation(x, y, op))
    # 此时 explist 中元素已全副遍历, 同时乘除法均已被运算, 双栈只剩加减法有待运算. 家喻户晓, 加减法遵从结合律, 接下来一路算到底即可.
    while ops:
        op = ops.pop()
        y = nums.pop()
        x = nums.pop()
        x_op_y = operation(x, y, op)
        nums.append(x_op_y)

    return nums[0]


if __name__ == '__main__':
    exp = '1*43+542+532*432'
    print(calculate_expression(exp))
    print(eval(exp))

参考资料

1. CSDN: 表达式求值——————Python 大法好！https://blog.csdn.net/Hpuer_R…