Is there a better way to implement this?

Question

I'm writing a calculator in Python (as an exercise), and there's one bit that I'm wondering about.

The program splits up the input into a list of numbers and operators. The result is then computed thusly:

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

This function looks through the list for arithmetic operators in order of decreasing precedence and then from left to right, and when it finds such an operator it calls the corresponding function on the neighboring list elements (the operands) and replaces the operator and operands in the list with the result of the operation. Once all of the operations have been executed, the list will contain a single element - the result of the computation.

However, this function doesn't behave the way it is intended to. The problem (I think) is that this function modifies the list (by assigning to slices) while it is iterating over it. I have already found a solution to this problem here (by restarting the inner for loop every time the list is modified), but the people who gave the solution seemed to think that there should usually be a better way to accomplish whatever this is needed for.

I was wondering if there is a better way to implement this algorithm that avoids the weird 'restarting the loop' thingy.

Thanks for any ideas!

Answer 1

You can manipulate the index if you use a while loop instead

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]

Answer 2

I think I'd go about it differently, and use a recursive function. Pop off operations and replace them with the result of their evaluation.

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)

Answer 3

I'm not sure what you mean by "restarting the loop" thingy. In this particular case, it seems to me that you should simply apply a function repeatedly to the expression until it has been reduced to a value. This is less efficient than it could be, but it works and is clear. So...

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)

Tested:

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

This could be made more efficient by not searching through the whole string repeatedly. That could be done by having a start_index parameter in find_op, and by having reduce_binary_infix return a new current index along with the reduced list.

This is also a bit more verbose than what you have, but I think it helps the code's readability -- not to mention its reusability.