在Python中不使用递归对嵌套列表求和

Question

假设有一个Python列表，其中的元素要么是整数，要么是整数列表（我们不知道嵌套深度），如何找出列表中每个整数的总和？

如果列表只有一层嵌套，找到列表总和相对简单。但是如果嵌套有两层、三层或更多层呢？

我知道最好的方法是使用递归，但这是一项挑战，我必须在没有递归的情况下完成它。

请帮帮我！！

- thorium

---

你能否在你的问题中添加一些测试用例？这并不难解决，但我没有时间为你编写测试用例。 - John La Rooy

这听起来像是一道作业类型的问题，特别是有那样的任意限制。 - nerdwaller

想一想，这个问题本质上是将一个嵌套的列表展平。 - devnull

l = [1,[2,[3,[[[4]]]],5],6,[[7,8]],2] - thorium

Answer 1

L = [...]
while any(isinstance(i, list) for i in L):
   L = [j for i in L for j in (i if isinstance(i, list) else [i])]

result = sum(L)

基本上，您需要迭代外部列表并解包任何内部列表的第一层，直到没有内部列表为止。

- John La Rooy

Answer 2

一种大部分易读（并且可能高效，虽然我没有测试过）的逐步展开列表的方法：

from collections import deque

def iterative_flatten(li):
    nested = deque(li)
    res = []
    dq = deque()
    while nested or dq:
        x = dq.pop() if dq else nested.popleft()
        dq.extend(reversed(x)) if isinstance(x, list) else res.append(x)
    return res

使用双端队列避免list.pop(0)的恶劣O(n**2)行为。您可以通过创建反向副本并从末尾弹出来获得等效的结果，但如果只是使用双端队列和popleft，我觉得代码更容易理解一些。同样，如果要原地突变列表，则可以节省一两行代码，但速度要慢得多（由于相同的原因；从列表的头弹出是O(n)，因为必须移动底层数组中的每个元素）。

nested = [1,[[2,3],[[4,5],[6]]],[[[[7]]]]]

iterative_flatten(nested)
Out[116]: [1, 2, 3, 4, 5, 6, 7]

sum(iterative_flatten(nested))
Out[117]: 28

把它展成平面后，求和就变得非常简单了 :-)

- roippi

Answer 3

这里有一个解决方案：

from copy import deepcopy

def recursive_sum(int_list):
    #int_list = deepcopy(int_list)    use this line if don't want to modify original list
    ret = 0
    while len(int_list) > 0:
        elem = int_list.pop(0)
        if type(elem) == int:
            ret += elem
        elif type(elem) == list:
            int_list.extend(elem)
        else:
            raise ValueError
    return ret

testcase = [1,2,3,[4,5,[6,7,8,[9,10]]]]
print recursive_sum(testcase)    # print 55

基本上，它会弹出输入列表的第一个元素。如果是int，则添加到总和中；如果是List，则扩展到输入列表的末尾。

- ZZY