Looping through nested lists and keeping track of it

Question

Example

input:  [1, '+', [4, '*', [3, '*', 7]], '/', 2]  
output:  43

input:  [[1, '+', 3], '*', [2, '+', 4]] 
output:  24

The number of nested lists is unknown

I'm not sure how to approach this. I've looked up other looping nested lists posts (iterate python nested lists efficiently & Python - Iterating through list of list) but they don't really work in this case since there's order of operations with the brackets.

I had thought of using recursion but I don't know how I would code it if it had like an enormous amount of nested loops and I'm not sure how to keep track of everything and finding the deepest list.
Thanks

EDIT: oops, sorry, didn't make it clear. Trying to essentially do a math expression based on what the list contains. It could contain * + - / and % and we have to do it based on order of operations.

EDIT2: How to apply order of operations and parenthesis priority to something like this?

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

def do_math(equation):
    if isinstance(equation, list):
        op = ops[equation[1]]
        return op(do_math(equation[0]), do_math(equation[2]))
    else:
        return equation

print (do_math([1, '+', [4, '*', [3, '*', 7]], '/', 2]))

What do the empty strings mean in the list? Implicit multiplication? — Christian Dean, Jul 09 '17 at 21:55

trincot · Answer 1 · 2017-07-10T07:45:01.403

1

You could use a recursive function, which maintains a stack of operations still to execute once the next operator found has a lower priority. As long as operators have increasing priority, it adds these together with the left-side value to a stack.

The use of named tuples and the operator functions is not absolutely required, but makes the code a bit more readable:

from operator import mul, truediv, mod, sub, add
from collections import namedtuple

Oper = namedtuple('Oper', 'f, prio')
HalfExpr = namedtuple('HalfExpr', 'value, oper')
ops = {
    "*": Oper(f=mul,     prio=1),
    "/": Oper(f=truediv, prio=1),
    "%": Oper(f=mod,     prio=1),
    "-": Oper(f=sub,     prio=2),
    "+": Oper(f=add,     prio=2)
}

def calc(expr):
    if not isinstance(expr, list):
        return expr
    stack = []
    for i in range(0, len(expr), 2):
        oper = ops[expr[i+1]] if i+1 < len(expr) else ops['+'] 
        value = calc(expr[i])
        while len(stack) and stack[-1].oper.prio <= oper.prio:
            a = stack.pop()
            value = a.oper.f(a.value, value)
        stack.append(HalfExpr(value, oper))
    return stack[0].value

print(calc([1, '+', [4, '*', [3, '+', 7]], '/', 2]))

See it run on repl.it

edited Jul 10 '17 at 07:45

answered Jul 09 '17 at 22:02

trincot

317,000
35
244
286

This can be simplified if you use the [`operator`](https://docs.python.org/3.5/library/operator.html) module. – Christian Dean Jul 09 '17 at 22:03
Thanks, @ChristianDean, I added that as alternative. – trincot Jul 09 '17 at 22:10
Hmm... I came to the same code as you did, but both our results seem to be off. The correct result of the expression is `43.0`, but both our functions are giving the result `41`. – Christian Dean Jul 09 '17 at 22:24
there's typo or miscalculation? [1, '+', [4, '*', [3, '+', 7]], '/', 2] == 1 + (4 * (3 + 7)) / 2 => 21 – thefalsehuman Jul 09 '17 at 22:40
I previously hadn't noticed you had multiple operators at the same array level. In your edited question you added the requirement of executing them with a given order of priority. I have updated my answer to deal with that. – trincot Jul 10 '17 at 07:40

Looping through nested lists and keeping track of it

1 Answers1