Расширение древовидной структуры данных

Question

Я пытаюсь использовать Python для изменения некоторых текстовых строк с помощью модуля re (т.е. re.sub). Тем не менее, я думаю, что мой вопрос применим к другим языкам с реализациями регулярных выражений.

У меня есть несколько строк, которые представляют древовидные структуры данных. Они выглядят примерно так:

(A,B)-C-D
A-B-(C,D)
A-(B,C,D-(E,F,G,H,I))

Каждая буква представляет собой ветвь или ребро. Буквы в скобках обозначают ветви, входящие или выходящие из другой ветви.

Везде, где есть «простой» кортеж значений (кортеж, состоящий только из одной запятой, разделенной запятой), я хотел бы взять префикс (X-) или суффикс (-X) этого кортежа и применить его к каждому значений в кортеже.

При этом преобразовании вышеприведенные строки станут

(A-C,B-C)-D
A-(B-C,B-D)
A-(B,C,(D-E,D-F,D-G,D-H,D-I))

Повторное применение методологии в конечном итоге приведет к

(A-C-D,B-C-D)
(A-B-C,A-B-D)
(A-B,A-C,A-D-E,A-D-F,A-D-G,A-D-H,A-D-I)

Строки в этих кортежах представляют пути через дерево, начинающиеся с корня и заканчивающиеся на листе.

Буду признателен за любую помощь в выполнении этой задачи с использованием регулярных выражений (или других подходов).

Answer 1

Вы не можете сделать это с помощью регулярных выражений, потому что вам приходится иметь дело с вложенными структурами. Вместо этого вы можете использовать pyparsing nestedExpr

Answer 2

Проблема, которую вы описываете, заключается в перечислении путей в графе.

Вы описываете три графика

A   B
 \ /
  C
  |
  D

  A
  |
  B
 / \
C   D

   A
 / |  \
B  C    D
     // | \\
    E F G H I

и для каждого вы хотите перечислить пути.Это включает в себя распределение значения по произвольно вложенной структуре.Если бы это можно было сделать с помощью регулярных выражений, и я не уверен, что это возможно, это должно быть сделано, я полагаю, за несколько проходов .

Мой смысл вашей проблемы состоит в том, что ее лучше всего решить, проанализировав вашу строку в графовой структуре и затем перечислив пути.Если вы не хотите физически строить график, вы, вероятно, можете генерировать строки в пользовательских действиях для генератора синтаксического анализатора.

Решение на основе регулярных выражений должно знать, как обрабатывать оба

(A,B)-C

и

(A,B,C,D,E,F,G,H)-I

Вы можете сопоставить эти строки с

\([A-Z](,[A-Z])*\)-[A-Z]

, но как бы вы "распределили" по всем подсовпадениям без какой-либо логики?Так как эта логика нужна вам в любом случае, вы можете выполнить ее на реальной структуре графа.Вы также можете сделать это для самой строки, но было бы лучше сделать это под эгидой генератора синтаксического анализатора, который может обрабатывать контекстно-зависимые или контекстно-зависимые структуры.

Answer 3

После публикации моего комментария, ссылающегося на пример invRegex в pyparsing, я посмотрел немного ближе к вашему вводу, и выглядело так, как будто вы можете интерпретировать это как инфиксную запись, с ',' и '-' как бинарные операторы.В Pyparsing есть вспомогательный метод с неловким названием operatorPrecedence, который анализирует выражения в соответствии с приоритетом операторов с группировкой в ​​скобках.(В этом есть немного больше смысла, чем при использовании вспомогательного метода nestedExpr, который сопоставляет выражения, вложенные в символы группировки.) Итак, вот версия синтаксического анализатора с использованием operatorPrecedence:

data = """\
(A,B)-C-D 
A-B-(C,D) 
A-(B,C,D-(E,F,G,H,I))""".splitlines()


from pyparsing import alphas, oneOf, operatorPrecedence, opAssoc

node = oneOf(list(alphas))
graphExpr = operatorPrecedence(node,
    [
    ('-', 2, opAssoc.LEFT),
    (',', 2, opAssoc.LEFT),
    ])

for d in data:
    print graphExpr.parseString(d).asList()

Pyparsing фактически возвращает сложную структуру типа ParseResults, которая поддерживает доступ к анализируемым токенам в виде элементов в списке, элементов в dict или атрибутов в объекте.Вызывая asList, мы просто получаем элементы в простой форме списка.

Вывод вышеприведенного показывает, что мы находимся на правильном пути:

[[['A', ',', 'B'], '-', 'C', '-', 'D']]
[['A', '-', 'B', '-', ['C', ',', 'D']]]
[['A', '-', ['B', ',', 'C', ',', ['D', '-', ['E', ',', 'F', ',', 'G', ',', 'H', ',', 'I']]]]]

Pyparsing также позволяетВы должны прикрепить обратные вызовы или parse actions к отдельным выражениям, которые будут вызываться во время анализа.Например, это действие синтаксического анализа выполняет преобразование времени анализа в целое число:

def toInt(tokens):
    return int(tokens[0])
integer = Word(nums).setParseAction(toInt)

Когда значение возвращается в ParseResults, оно уже преобразовано в целое число.

Классы также могутбыть задан как действия синтаксического анализа, и объект ParseResults передается методу __init__ класса, а полученный объект возвращается.Мы можем указать действия разбора в operatorPrecedence, добавив действие разбора в качестве 4-го элемента в кортеж дескриптора каждого оператора.

Вот базовый класс для бинарных операторов:

class BinOp(object):
    def __init__(self, tokens):
        self.tokens = tokens
    def __str__(self):
        return self.__class__.__name__ + str(self.tokens[0][::2])
    __repr__ = __str__

Из этого базового класса,мы можем получить 2 подкласса, по одному для каждого оператора - и ,:

class Path(BinOp):
    pass

class Branch(BinOp):
    pass

и добавить их в кортежи определения оператора в operatorPrecedence:

node = oneOf(list(alphas))
graphExpr = operatorPrecedence(node,
    [
    ('-', 2, opAssoc.LEFT, Path),
    (',', 2, opAssoc.LEFT, Branch),
    ])


for d in data:
    print graphExpr.parseString(d).asList()

Это дает намвложенная структура объектов для каждой входной строки:

[Path[Branch['A', 'B'], 'C', 'D']]
[Path['A', 'B', Branch['C', 'D']]]
[Path['A', Branch['B', 'C', Path['D', Branch['E', 'F', 'G', 'H', 'I']]]]]

Создание путей из этой структуры оставлено в качестве упражнения для OP.(Инвертор Pyparsing Regex делает это с помощью путаницы генераторов - надеюсь, будет достаточно некоторой простой рекурсии.)