如何使用递归实现不遵循PEMDAS规则的多步算术运算求值

原有代码的问题 #

• 每次递归都重复遍历整个运算符序列做字符串到运算符函数的转换，逻辑冗余
• 错误使用pop()方法：默认弹出列表末尾元素，不符合从左到右取数、取运算符的要求，且pop会修改原输入列表，容易产生副作用
• 递归调用参数不符合函数定义：传入单独的两个数字而非数字列表、运算符列表，会直接触发参数结构不匹配的报错

正确实现代码 #

import operator as op

# 运算符映射表，避免每次重复判断
OP_MAP = {
    "+": op.add,
    "-": op.sub,
    "*": op.mul,
    "/": op.truediv
}

def evaluate_wo_pemdas(numbers, operator_sequence):
    # 递归终止条件：只剩一个数字，直接返回
    if len(numbers) == 1:
        return numbers[0]
    # 取第一个运算符、前两个数字做单次运算
    current_op = OP_MAP[operator_sequence[0]]
    step_result = current_op(numbers[0], numbers[1])
    # 构造新的数字列表：单次运算结果 + 剩余未参与运算的数字
    new_numbers = [step_result] + numbers[2:]
    # 构造新的运算符列表：剩余未使用的运算符
    new_operators = operator_sequence[1:]
    # 递归处理剩余的运算
    return evaluate_wo_pemdas(new_numbers, new_operators)

示例运行验证 #

输入numbers = [1, 2, 3, 4]、operator_sequence = ["/", "+", "*"]，运算过程为((1 / 2) + 3) * 4 = 14，调用函数输出结果如下：

print(evaluate_wo_pemdas([1,2,3,4], ["/", "+", "*"]))
# 输出：14.0

通用递归思路技巧 #

• 先确定终止条件：找到问题不需要继续拆分的最小场景，比如本题中只剩一个数字不需要运算就是终止条件，直接返回结果即可
• 拆分子问题：每次递归只处理最小一步的逻辑，把剩下的规模更小的同类问题交给下一层递归处理，本题中每次只算第一步运算，剩下的数字和运算符组成的新问题和原问题结构完全一致，直接递归调用即可
• 保证输入输出结构统一：递归函数的入参结构、出参类型要和原函数完全一致，不要随意修改入参结构
• 优先用无副作用的操作：比如用列表切片生成新列表传入递归，而不是用pop修改原列表，避免出现意料之外的错误

内容的提问来源于stack exchange，提问作者user268493