Рекурсия по списку списков без isinstance () - PullRequest
Новая
       18

Рекурсия по списку списков без isinstance ()

5 голосов
/ 04 мая 2011

Я только что прочитал "isinstance () считается вредным" , и это кажется разумным. Короче говоря, он утверждает, что избегает использования этой функции.

Что ж, сейчас я пишу программу, которая принимает входные данные, структурированные как дерево, и нуждается в информации о структуре дерева. Не успев реализовать графический интерфейс, я навязываю пользователю записать его в файл конфигурации (я знаю, что это плохой интерфейс, но график действительно плотный). Мои пользователи очень техничны, но не обязательно знают Python. Я решил, что файл будет содержать списки списков (списков списков и т. Д.), Представляющих входные деревья, а конечными элементами являются листовые узлы деревьев. Я думаю, что это намного лучше, чем навязывать пользователям синтаксис словарей.

Я планирую рекурсивно анализировать списки следующим образом (пропуская использование структуры дерева, давайте упростим и скажем, что каждый узел листа должен вызывать TreatLeafNode ()): 

def parseTree(input):
    if isinstance (input, list):
        for item in input:
            parseTree(item)
    else:
        treatLeafNode(item)

В свете этой статьи мне интересно, есть ли простой способ исправить это без использования isinstance () ...

Кто-нибудь знает один?

Ответы [ 5 ]

10 голосов
/ 04 мая 2011

Ваша ситуация одна из тех, где я бы использовал isinstance.Ваша структура данных хорошо ограничена, и вам нужно различать список, а не список.Используйте isinstance, чтобы узнать, является ли это списком.Вы не говорите, но я полагаю, что строки могут быть среди листьев вашего дерева, и они итерируемы как списки, так что различие между ними заключается в типизации уток.

5 голосов
/ 04 мая 2011

Вы можете использовать 

def parseTree(input):
    try:
        for item in input:
            parseTree(item)
    except TypeError:
        treatLeafNode(item)

Обратите внимание, что это также будет выполнять итерации по строкам.

2 голосов
/ 04 мая 2011

Что может работать лучше, так это инкапсулировать вашу древовидную структуру с помощью объекта Node, который может содержать значение и список дочерних элементов: 

class Node(object):
    def __init__(self, children=[], value=None):
        self.children = children
        self.value = value
    def isLeaf(self):
        return len(self.children) == 0

Теперь узел в явном виде является либо листом со значением, либо элементом с дочерними элементами (технически не листовые узлы также могут иметь значения в этом примере, но код вашего приложения может принять решение о том, что неконечные узлы никогда не имеют значений ). parseTree можно записать как: 

def parseTree(node):
    if node.isLeaf():
        treatLeafNode(node)
    else:
        for child in node.children:
            parseTree(child)

Обратите внимание, что это поиск в дереве по глубине.

Могут быть более удачные способы обернуть это так, что parseTree - это метод Node, но это должно дать вам представление. Конечно, у вас все еще есть проблема с тем, что вы просите пользователя написать код Python, который представляет собой списки списков в качестве входных данных, и проанализировать его в приведенной выше древовидной структуре, вам нужно будет использовать isinstance. Возможно, yaml был бы лучшим выбором языка описания, поскольку пользователи не могут затем вставить произвольный код Python в ваш ввод?

0 голосов
/ 04 мая 2011

Есть ли причина, по которой вы выбрали список списков в качестве предпочитаемой древовидной структуры? Я могу придумать много лучших способов написать один в конфигурационном файле. Предположим, вы пытаетесь кодировать: 

a
|-- b
|   |-- c
|   |-- d
|   |   |-- e
|   |   `-- f
|   `-- g
|       `-- h
|-- i
`-- j
    `-- k

Как насчет 

a: b, i, j
b: c, d, g
d: e, f
g: h
j: k

Вы можете легко разобрать это в словарь и соединить в дерево. На самом деле, я думаю, ConfigParser уже сделает это за вас.

Или как насчет: 

a
----b
--------c
--------d
------------e
------------f
--------g
------------h
----i
----j
--------k
0 голосов
/ 04 мая 2011

Как насчет использования yaml? Вам также не придется выполнять проверку и логику синтаксического анализа самостоятельно.

Дерево может выглядеть как 

- [[aMAN],[sTACK, OVER],[FLOW]]
- [[aMAN1],[sTACK1, OVER1],[FLOW1]]
- [[aMAN2],[sTACK2, OVER2],[FLOW2]]

Код для его анализа 

import yaml                    
f= open('test.yml')
test = yaml.load(f.read())
print test

Выход: 

[[['aMAN'], ['sTACK', 'OVER'], ['FLOW']], [['aMAN1'], ['sTACK1', 'OVER1'], ['FLOW1']], [['aMAN2'], ['sTACK2', 'OVER2'], ['FLOW2']]]
...