Is there a better way to implement this?

Question

I am writing a calculator in Python (as an exercise), and there is one bit that I am interested in.

The program breaks the input into a list of numbers and operators. The result is then calculated as follows:

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 scans the list for arithmetic operators in decreasing order of priority, and then from left to right, and when it finds such an operator, it calls the corresponding function in neighboring list elements (operands) and replaces the operator and operands in the list with the result of the operation. When all operations are completed, the list will contain one element - the result of the calculation.

However, this function does not behave as it is intended. The problem (I think) is that this function modifies the list (assigning slices) while it iterates over it. I already found a solution to this problem here (by restarting the inner for loop each time the list is changed), but the people who gave the solution should think that there usually should be a better way to accomplish everything that is needed for this.

I was wondering if there is a better way to implement this algorithm that avoids the weird “loop restart”.

Thanks for any ideas!

Answer 1

I think it will go differently and use a recursive function. Turn the operations over 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 2

You can manipulate the index by using a while 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 3

I'm not sure what you mean by "restarting the loop." In this particular case, it seems to me that you just need to re-apply the function to the expression until it is reduced to a value. This is less effective than it could be, but it works and is understandable. So that...

 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 can be made more efficient without repeating the whole chain. This can be done using the start_index parameter in find_op and by reduce_binary_infix return the new current index along with the reduced list.

It is also a little more verbose than what you have, but I think it helps the readability of the code - not to mention its reuse.