# Is there a better way to implement this?

### Tags:

#### calculator

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!

329

#### smackcrane

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.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)
``````
194

#### zeekay

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]
``````
33