这个实现方式有更好的方法吗？

Question

我将为您翻译有关IT技术的内容。以下是需要翻译的内容：

我正在使用Python编写一个计算器（作为练习），有一点让我感到困惑。

程序将输入分解成数字和运算符的列表。然后按照以下方式计算结果：

import operator
ops = {'+' : operator.add,                      # operators and corresponding functions
       '-' : operator.sub,
       '*' : operator.mul,
       '/' : operator.truediv,
       '%' : operator.mod}
precedence = [['*', '/', '%'], ['+', '-']]      # order of precedence for operators

def evaluate(exp):
  for oplist in precedence:                     # search for operators first in order of precedence
    for op in exp:                              # then from left to right
      if op in oplist:
        index = exp.index(op)
        result = ops[op](exp[index - 1], exp[index + 1])
                                                # compute the result of the operation
        exp[index - 1:index + 2] = [result]
                                                # replace operation and operands with result
  return exp[0]

# for example,
evaluate([2, '+', 3, '+', 4, '+', 5])
# should return 14

这个函数按照优先级从高到低的顺序，从左到右遍历列表，查找算术运算符，当它找到这样的运算符时，就调用相应的函数处理相邻的列表元素（操作数），并用操作结果替换列表中的运算符和操作数。一旦所有操作都执行完毕，列表将只包含一个元素 - 计算结果。

然而，这个函数的行为并不像预期的那样。问题（我认为）是这个函数在迭代列表时修改了列表（通过对切片进行赋值）。我已经在这里找到了解决这个问题的方法（通过在每次修改列表时重启内部for循环），但给出解决方案的人似乎认为通常应该有更好的方法来完成所需的任务。

我想知道是否有更好的方式来实现这个算法，以避免奇怪的“重启循环”操作。

感谢您提供的任何想法！

- smackcrane

---

请查看该网址：https://dev59.com/cEnSa4cB1Zd3GeqPQbuV。 - Rumple Stiltskin

这个问题更适合于codereview.stackexchange.com，您想将其迁移到那里吗？ - Tim Post

啊，我没有考虑到那个。当然，谢谢。 - smackcrane

Answer 1

如果使用 while 循环，您可以操作索引。

def evaluate(exp):
    for oplist in precedence:  # search for operators first in order of precedence
        idx = 0
        while idx < len(exp):
            op = exp[idx]
            if op in oplist:
                result = ops[op](exp[idx - 1], exp[idx + 1])
                exp[idx - 1:idx + 2] = [result]
                idx -= 1       # move index back since list is shortened by 2
            else:
                idx += 1
    return exp[0]

- John La Rooy

Answer 2

我认为我会采用不同的方法，使用递归函数。弹出操作并用其评估结果替换它们。

import operator

ops = {
    '+' : operator.add,
    '-' : operator.sub,
    '*' : operator.mul,
    '/' : operator.truediv,
    '%' : operator.mod,
}

precedence = [
    set(['*', '/', '%']),
    set(['+', '-']),
]

def evaluate(expr):
    # if len == 3 then just return result of expression
    if len(expr) == 3:
        l, op, r = expr
        return ops[op](l, r)
    else:
        for op_list in precedence:
            for op in expr:
                if op in op_list:
                    # find index of first operation
                    idx = expr.index(op)-1
                    # pop off and evaluate first matching operation in expr
                    result = evaluate([expr.pop(idx) for i in range(3)])
                    # insert result back into expr
                    expr.insert(idx, result)
                    return evaluate(expr)

- Zach Kelling

---

+1 对于最容易理解的解决方案。但是不高效，因为在给定运算符的情况下，您对整个表达式进行了两次线性搜索相同的运算符，一次是 if op in expr，然后是 idx = expr.index(op)-1。我会将整个单运算符搜索嵌套在 try-except 块中，因为如果 op 不在 expr 中，expr.index(op) 会引发错误。 - machine yearning

谢谢！我确实在追求可读性，但你说得很好 :) - Zach Kelling

这是一个不错的解决方案，但对于像2-3+4这样的表达式，相等优先级的集合是必要的。如果它在搜索“+”之前搜索“-”，那么2-3+4=2-7=-5，这是不正确的。当运算符具有相等的优先级时，必须将它们作为一组进行搜索。 - smackcrane

@discipulus 当然，我想当初认为这不重要是有些愚蠢的。我会将答案调整为像原问题一样搜索运算符组。 - Zach Kelling

Answer 3

我不确定你所说的“重启循环”的意思。在这种情况下，我认为你只需要对表达式反复应用函数，直到它被简化为一个值。虽然这种方法不够高效，但它是可行的并且易于理解。因此...

def find_op(tokens, oplist):
    for i, token in enumerate(tokens):
        if token in oplist:
            return i
    else:
        return -1

def reduce_binary_infix(tokens, i, ops):
    op = ops[tokens[i]]
    tokens[i - 1: i + 2] = [op(tokens[i - 1], tokens[i + 1])]
    return tokens

def evaluate(tokens, ops, precedence):
    for prec in precedence:
        index = find_op(tokens, prec)
        while index >= 0:
            tokens = reduce_binary_infix(tokens, index, ops)
            index = find_op(tokens, prec)
    return tokens

print evaluate([2, '+', 3, '+', 4, '+', 5], ops, precedence)

已测试：

>>> print evaluate([2, '+', 3, '+', 4, '+', 5], ops, precedence)
[14]

通过不重复搜索整个字符串，可以使其更加高效。这可以通过在find_op中添加一个start_index参数，并使reduce_binary_infix返回一个新的当前索引和减少后的列表来实现。

相比你所拥有的代码，这也有点啰嗦，但我认为它有助于提高代码的可读性——更不用说其可重用性了。

- senderle