仅通过仅提供"left()"和"right()"作为命令来使用光标在嵌套列表中手动导航？

Question

Event尽管我用python写作，但我认为抽象概念对我和其他人来说更有趣。因此，如果你喜欢，请使用伪代码：）

我有一个清单，里面有我的一个班的项目。让我们在这里用字符串和数字来做，这真的不重要。它嵌套到任何深度。（它实际上不是一个列表，而是一个基于列表的容器类。）

示例：[1，2，3，[‘a’，‘b’，‘c’]4[’d’，‘e’，[1000200300]]5，[’a’，’b’，’c’]，6]

请注意，两个[a'，'b'，'c']实际上是同一个容器。如果你改变了一个，你就改变了另一个。容器和项目可以编辑，项目可以插入，最重要的容器可以多次使用。为了避免冗余，不可能使列表变平（我认为！），因为您失去了在一个容器中插入项目的能力，而它会自动显示在所有其他容器中。

问题：对于前端（只是带有python"cmd"模块的命令行），我希望使用始终指向当前项的光标浏览此结构，以便可以读取或编辑它。光标可以向左和向右移动（用户的观点），并且应该表现为列表不是嵌套列表而是平面列表。

对于一个人来说，这是非常容易做到的。你只需要假装上面的列表中的子列表不存在，然后从左到右再回来。

例如，如果你在上面的列表中的"3"位置，向右走，你会得到"a"作为下一个项目，然后是"b"、"c"，再是"4"等。或者，如果你从"300"向右走，你会得到下一个"5"。

向后看：如果你从"6"向左走，下一个是"c"。如果你从"5"向左走，就是"300"。

那么原则上我该怎么做呢？我有一个方法，但它是错误的，问题已经太长了，我担心大多数人不会读它：（.我可以稍后发布。

p.S。即使很难抗拒：这个问题的答案不是"你为什么要这样做，为什么要这样组织你的数据，为什么不先[压平列表|超出我想象的东西]？问题正是我在这里描述的，没有其他问题。数据是按照问题的性质以这种方式结构化的。

Answer 1

一个解决方案是存储当前索引和/或深度信息，并使用它遍历嵌套列表。但这似乎是一个需要进行大量复杂分叉的解决方案——测试列表末尾等等。相反，我想出了一个折衷方案。我没有将列表列表扁平化，而是创建了一个生成器，在列表中创建一个扁平的索引列表：

def enumerate_nested(nested, indices):
    for i, item in enumerate(nested):
        if isinstance(item, collections.Iterable) and not isinstance(item, basestring):
            for new_indices in enumerate_nested(item, indices + (i,)):
                yield new_indices
        else:
            yield indices + (i,)

然后是一个简单的函数，它基于索引元组从列表列表中提取最里面的项：

def tuple_index(nested_list, index_tuple):
    for i in index_tuple:
        nested_list = nested_list[i]
    return nested_list

现在，您所要做的就是以任何您喜欢的方式遍历平面索引列表。

>>> indices = list(enumerate_nested(l, tuple()))
>>> print l
[1, 2, 3, ['a', 'b', 'c'], 4, ['d', 'e', [100, 200, 300]], 5, ['a', 'b', 'c'], 6]
>>> for i in indices:
...     print tuple_index(l, i),
... 
1 2 3 a b c 4 d e 100 200 300 5 a b c 6

---

由于我在ideone上的评论中发布的基于堆栈的解决方案接受了这个答案，并且最好不要使用外部粘贴框作为答案代码，请注意，这个答案也包含我的基于堆栈解决方案。

Answer 2

我会让光标有一堆数组的索引。

示例：

[1, 2, 3, ['a', 'b', 'c'], 4 ]

如果光标位于1（索引0处），则光标的位置为[0]。

如果光标位于2（索引1处），则光标的位置为[1]。

如果光标位于"a"（最外层的索引3和第二层的索引0），则光标的位置将为[3，0]。

如果光标位于"b"（最外层的索引3和第二层的索引1），则光标的位置将为[3，1]。

等等。

要将光标向右移动，只需增加该位置最右侧的索引即可。因此，当你从"b"到"c"时，它将从[3，1]增加到[3，2]。如果索引超出范围，则从索引堆栈中弹出最右边的值并增加最右边的数值。所以，如果你从"c"到4，你就从[3，2]到[4]。

移动时，如果遇到嵌套数组的位置，请输入它。因此，如果从3（索引[2]处）向右移动，则输入数组中的第一个元素['a'，'b'，'c']，即索引[3，0]处。

向左移动与向右移动正好相反。

Answer 3

虽然我喜欢扁平化索引列表的想法，但这使得在迭代嵌套列表时无法修改任何子列表的长度。如果这不是你需要的功能，我会同意的。

否则，我还会将指向列表的指针实现为索引元组，并依赖递归。首先，这里有一个类，它实现right()并通过deref()读取指针的值。（我使用None来表示列表末尾以外的指针。）我将把它作为如何实现left()和分配给元素的练习。如果将当前指向的元素替换为另一个列表，则必须决定您想要的行为。祝你好运

def islist(seq):
    return isinstance(seq, (list, tuple))
class nav:
    def __init__(self, seq):
        self.seq = seq
        self.ptr = self.first()
    def __nonzero__(self):
        return bool(self.ptr)
    def right(self):
        """Advance the nav to the next position"""
        self.ptr = self.next()
    def first(self, seq=None):
        """pointer to the first element of a (possibly empty) sequence"""
        if seq is None: seq = self.seq
        if not islist(seq): return ()
        return (0,) + self.first(seq[0]) if seq else None
    def next(self, ptr=None, seq=None):
        """Return the next pointer"""
        if ptr is None: ptr = self.ptr
        if seq is None: seq = self.seq
        subnext = None if len(ptr) == 1 else self.next(ptr[1:], seq[ptr[0]])
        if subnext is not None: return (ptr[0],) + subnext
        ind = ptr[0]+1
        return None if ind >= len(seq) else (ind,) + self.first(seq[ind])
    def deref(self, ptr=None, seq=None):
        """Dereference given pointer"""
        if ptr is None: ptr = self.ptr
        if seq is None: seq = self.seq
        if not ptr: return None
        subseq = seq[ptr[0]]
        return subseq if len(ptr) == 1 else self.deref(ptr[1:], subseq)
abc = ['a', 'b', 'c']
a = [1, 2, 3, abc, 4, ['d', 'e', [100, 200, 300]], 5, abc, 6]
n = nav(a)
while n:
    print n.ptr, n.deref()
    n.right()

Answer 4

本质上，我会将自己的解决方案建立在递归的基础上。我将用以下内容扩展容器类：

1. cursor_position-存储高亮显示元素（或包含高亮显示元素的元素的元素，或任何级别的递归）的索引的属性
2. repr_with_cursor-此方法应返回容器内容的可打印版本，该版本已高亮显示当前选定的项目
3. mov_right-当光标向右移动时，应调用此方法。返回元素中光标的新索引，如果光标位于当前容器的"外部"（如果移动到容器中的最后一个元素），则返回None
4. mov_left-伊德姆，但向左

递归的工作方式是，对于每个方法，根据突出显示的方法的类型，您应该有两种不同的行为：

• 如果光标位于容器上，它应该调用"pointed"容器的方法
• 如果光标位于非容器上，它应该执行"实际操作"

编辑我有半个小时的空闲时间，所以我整理了一个实现我想法的示例课。它的功能并不完整（例如，当它到达最大容器的任一端时，它不能很好地处理，并且要求类的每个实例在最大序列中只使用一次），但它足以演示这个概念在人们评论之前，我会重复一遍：这是概念验证代码，它还没有准备好使用

#!/usr/bin/env python
# -*- coding: utf-8  -*-
class C(list):
    def __init__(self, *args):
        self.cursor_position = None
        super(C, self).__init__(*args)
    def _pointed(self):
        '''Return currently pointed item'''
        if self.cursor_position == None:
            return None
        return self[self.cursor_position]
    def _recursable(self):
        '''Return True if pointed item is a container [C class]'''
        return (type(self._pointed()) == C)
    def init_pointer(self, end):
        '''
        Recursively set the pointers of containers in a way to point to the
        first non-container item of the nested hierarchy.
        '''
        assert end in ('left', 'right')
        val = 0 if end == 'left' else len(self)-1
        self.cursor_position = val
        if self._recursable():
            self.pointed._init_pointer(end)
    def repr_with_cursor(self):
        '''
        Return a representation of the container with highlighted item.
        '''
        composite = '['
        for i, elem in enumerate(self):
            if type(elem) == C:
                composite += elem.repr_with_cursor()
            else:
                if i != self.cursor_position:
                    composite += str(elem)
                else:
                    composite += '**' + str(elem) + '**'
            if i != len(self)-1:
                composite += ', '
        composite += ']'
        return composite
    def mov_right(self):
        '''
        Move pointer to the right.
        '''
        if self._recursable():
            if self._pointed().mov_right() == -1:
                if self.cursor_position != len(self)-1:
                    self.cursor_position += 1
        else:
            if self.cursor_position != len(self)-1:
                self.cursor_position += 1
                if self._recursable():
                    self._pointed().init_pointer('left')
            else:
                self.cursor_position = None
                return -1
    def mov_left(self):
        '''
        Move pointer to the left.
        '''
        if self._recursable():
            if self._pointed().mov_left() == -1:
                if self.cursor_position != 0:
                    self.cursor_position -= 1
        else:
            if self.cursor_position != 0:
                self.cursor_position -= 1
                if self._recursable():
                    self._pointed().init_pointer('right')
            else:
                self.cursor_position = None
                return -1

一个简单的测试脚本：

# Create the nested structure
LevelOne = C(('I say',))
LevelTwo = C(('Hello', 'Bye', 'Ciao'))
LevelOne.append(LevelTwo)
LevelOne.append('!')
LevelOne.init_pointer('left')
# The container's content can be seen as both a regualar list or a
# special container.
print(LevelOne)
print(LevelOne.repr_with_cursor())
print('---')
# Showcase the effect of moving the cursor to right
for i in range(5):
    print(LevelOne.repr_with_cursor())
    LevelOne.mov_right()
print('---')
# Showcase the effect of moving the cursor to left
LevelOne.init_pointer('right')
for i in range(5):
    print(LevelOne.repr_with_cursor())
    LevelOne.mov_left()

它输出：

['I say', ['Hello', 'Bye', 'Ciao'], '!']
[**I say**, [Hello, Bye, Ciao], !]
---
[**I say**, [Hello, Bye, Ciao], !]
[I say, [**Hello**, Bye, Ciao], !]
[I say, [Hello, **Bye**, Ciao], !]
[I say, [Hello, Bye, **Ciao**], !]
[I say, [Hello, Bye, Ciao], **!**]
---
[I say, [Hello, Bye, Ciao], **!**]
[I say, [Hello, Bye, **Ciao**], !]
[I say, [Hello, **Bye**, Ciao], !]
[I say, [**Hello**, Bye, Ciao], !]
[**I say**, [Hello, Bye, Ciao], !]

有趣的问题！我今天最喜欢的操作系统问题！：）