python - 使用 ArrayStack 递归地展平嵌套列表

Question

编写一个迭代函数，将嵌套列表展平，同时使用一个 ArrayStack 及其定义的方法保留其值的从左到右的顺序。也就是说，您不应该直接访问实现中的底层数组。不要使用任何辅助函数或更改函数签名。

此外，不要创建除ArrayStack.

前任）

lst = [ [[[0]]], [1, 2], 3, [4, [5, 6, [7]], 8], 9]
lst_flat = flatten_list(lst)
print(lst_flat)
# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

我用递归解决了上面的问题（我知道它不需要递归），但我想知道如何以更优化的方式用递归解决这个问题？因为，我认为我的实现在时间和空间使用方面非常薄弱。

这是我的代码：

def flatten_list(lst):
    s = ArrayStack()
    for i in range(len(lst)-1, -1, -1):
        if isinstance(lst[i], int):
            s.push(lst[i])
            lst.pop()
        else:
            for val in reversed(flatten_list(lst.pop())):
                s.push(val)
    while not s.is_empty():
        lst.append(s.pop())
    return lst

这是ArrayStack我使用的实现

class ArrayStack:
    def __init__(self):
        self.data = ArrayList()

    def __len__(self):
        return len(self.data)

    def is_empty(self):
        return len(self) == 0

    def push(self, val):
        self.data.append(val)

    def top(self):
        if (self.is_empty()):
            raise Exception("Stack is empty")
        return self.data[-1]

    def pop(self):
        if (self.is_empty()):
            raise Exception("Stack is empty")
        return self.data.pop()

标签： pythonarraysnested-lists