展平链表中'next'和'prev'链接

Question

我有一个表示数据结构遍历的字符串列表。我想把链表遍历压缩成更紧凑的表示形式。要做到这一点，我想计算相邻的next和prev链接的数量，并将它们折叠成一个整数。

下面是我想做的转换的例子:

['modules']                                   -->  ['modules']
['modules', 'next']                           -->  ['modules', 1]
['modules', 'prev']                           -->  ['modules', -1]
['modules', 'next', 'next', 'next', 'txt']    -->  ['modules', 3, 'txt']
['modules', 'next', 'prev', 'next', 'txt']    -->  ['modules', 1, 'txt']
['super_blocks', 'next', 's_inodes', 'next']  -->  ['super_blocks', 1, 's_inodes', 1]

每个next链路计数为+1，每个prev链路计数为-1。相邻的next s和prev s相互抵消。他们可以按任何顺序来。

我有一个工作的解决方案，但我正在努力寻找一个令人满意的优雅和python的解决方案。

Answer 1

您可以使用生成器:

def links(seq):
    it = iter(seq)
    while True:
        el = next(it)
        cnt = 0
        try:
            while el in ['prev', 'next']:
                cnt += (1 if el == 'next' else -1)
                el = next(it)
        finally:
            if cnt != 0:
                yield cnt
        yield el
print list(links(['modules', 'next', 'prev', 'next', 'txt']))

值得注意的是，包含相等数量的next和prev的序列被完全删除。如果这是您想要的，则很容易更改代码以产生0(我认为这方面的要求有点不清楚)。

Answer 2

如何:

def convert(ls):
    last = None
    for x in ls:
        if x == 'prev': x = -1
        if x == 'next': x = +1
        if isinstance(x, int) and isinstance(last, int):
            x += last
        elif last:  # last is not None if you want zeroes
            yield last
        last = x
    yield last

Answer 3

这是我想到的最直接的方法。对于理解、调试和将来的维护来说，直接是一种有价值的品质。

def process(l):
    result = []
    count = 0
    keepCount = False
    for s in l:
        if s == "next":
            count += 1
            keepCount = True
        elif s == "prev":
            count -= 1
            keepCount = True
        else:
            if keepCount:
                result.append(count)
                count = 0
                keepCount = False
            result.append(s)
        # end if
    # end for
    if keepCount:
        result.append(count)
    return result
# end process()

我确实更喜欢NPE对生成器的使用。(我的可以通过改变'result.append()'到'yield'轻松转换)他的(原始)答案几乎与我的相同，但我在下一个/前一个标记相邻的情况下包含了0计数。

Answer 4

加一点reduce()怎么样?

def collapse(lst):
    was_link = [False] # No nonlocal in Python 2.x :(
    def step(lst, item):
        val = { 'prev': -1, 'next': 1 }.get(item)
        if was_link[0] and val:
            lst[-1] += val
        else:
            lst.append(val or item)
        was_link[0] = bool(val)
        return lst
    return reduce(step, [[]] + lst)