If i have nested list as below, how do i first access ['*', '5', '8'](innermost list) so that i can perform multiplication and then move on to next innermost list i.e ['*',[result_from_previous_step],'9'] and so on till outer most list is found
['*', ['*', ['*', '5', '8'], '9'], '10']
This seems some what like evaluating a tree to me but in bottom up fashion
The most straightforward solution is to write a recursive function that calls itself to evaluate the inner expressions.
# helper function to parse strings where necessary
def intorfloat(number):
if not isinstance(number, str): # already parsed
return number
try:
return int(number)
except ValueError:
return float(number)
# evaluates a simple expression (no subexpressions)
def evaluate2(operation, operand1, operand2):
operand1, operand2 = intorfloat(operand1), intorfloat(operand2)
if operation == "*":
return operand1 * operand2
elif operation == "+":
return operand1 + operand2
elif operation == "/":
# keep the result an int if possible
result1 = operand1 // operand2
result2 = float(operand1) / operand2
return result1 if result1 == result2 else result2
elif operation == "-":
return operand1 - operand2
# recursively evaluate an expression with subexpressions
def evaluate(expression):
operation, operand1, operand2 = expression
if isinstance(operand1, list):
operand1 = evaluate(operand1)
if isinstance(operand1, list):
operand2 = evaluate(operand2)
return evaluate2(operation, operand1, operand2)
An iterative solution is also possible; the advantage is that you can evaluate expressions of any depth. In this version, we keep descending into sublists until we find a leaf: an expression that doesn't have any subexpressions. Then we evaluate the leaf and replace it with its result, and start over from the beginning. Eventually the top-level expression has no subexpressions.
This algorithm actually modifies the expression, repeatedly simplifying it until it's trivial to evaluate it. (The recursive solution does not modify the expression.)
If the expression is deep, we may do a lot of unnecessary traversal to repeatedly find leaf nodes. We could create a stack to allow us to backtrack instead of having to start at the top each time, but we might as well just use the recursive solution at that point.
# uses intorfloat() and evaluate2() functions previously shown
def evaluate(expression):
while isinstance(expression[1], list) or isinstance(expression[2], list):
current = expression
container = None
while True: # find a leaf node
operation, operand1, operand2 = current
if isinstance(operand1, list):
container, slot = current, 1
current = operand1
elif isinstance(operand2, list):
container, slot = current, 2
current = operand2
else:
break
if container:
container[slot] = evaluate2(*current)
return evaluate2(*expression)
print evaluate(['*', ['*', ['*', '5', '8'], '9'], '10']) # 3600
operator module to perform mathematical operations
operator functions; I just didn't want to bamboozle him too much. :-)This is a rough solution of your problem
l = ['*', ['*', ['*', '5', '8'], '9'], '10']
def islist(l):
try:
l.append
return True
except AttributeError:
return False
def reduce(l):
if islist(l):
return recurse(l)
else:
return l
def recurse(l):
if not islist(l):
return l
first = reduce(l[0])
second = reduce(l[1])
third = reduce(l[2])
return "({} {} {})".format(second, first, third)
print recurse(l)
Which uses recursion. Python is not the best language to implement recursive algorithms, pure functional languages like Erlang are more powerful on such topics.
The major problems are the maximum number of recursive calls and the memory occupation, but for such a small list this works.
One problem you can have is how to tell apart lists and other things, which is not so simple. You can use isinstance() or try/except like I do. The collections module is not that helpful in this case because both lists and strings are sequences.
You may create your custome recursive function using eval to achieve this as:
def perform_operation(my_list):
temp_list = []
for item in my_list:
if isinstance(item, list):
item = perform_operation(item)
temp_list.append(item)
return eval('{} {} {}'.format(temp_list[1], temp_list[0], temp_list[2]))
Sample run:
>>> my_list = ['*', ['*', ['*', '5', '8'], '9'], '10']
>>> perform_operation(my_list)
3600
Note: Using eval is not safe as it executes the content of string no matter what it has. So, be sure regarding what you pass to it
Here's a "more Pythonic" and more easily extendable version of what kindall proposed above. It also does not assume that the numbers are integer.
import operator
def evaluate(expression):
if isinstance(expression, str):
return float(expression)
op, operand1, operand2 = expression
ops = {"*" : operator.mul,
"+" : operator.add,
"/" : operator.truediv,
"-" : operator.sub}
return ops[op](evaluate(operand1), evaluate(operand2))
evaluate(['*', ['*', ['*', '5', '8'], '9'], '10'])
