Рекурсивные регулярные выражения в Python

Я обсуждал с коллегой простую проблему, которую его компания задавала во время интервью: «Учитывая строку, состоящую из открытых и закрытых скобок, определите, все ли скобки закрыты»

((())(())) -> Ok
()()  -> Ok
()()) -> Wrong
())( -> Wrong

Вы можете решить эту проблему с помощью счетчика, начинающегося с 0, и увеличивая на 1, когда вы встретились, ( и уменьшая на 1, когда вы встречались ). Сумма должна оставаться положительной или равной нулю, иначе это недопустимая строка. Базовая функция в python для проверки скобок может выглядеть так:

def check(val):
   counter = 0
   for c in val:
       if c == '(':
           counter += 1
       elif c == ')':
           counter -= 1
       else:
           raise AttributeError('invalid character in the argument')
       if counter < 0:
           return False
   return counter == 0:

Это не самый элегантный кусок кода на Python, но возможно ли сделать то же самое с регулярным выражением? И ответ ДА можем! 
Сейчас это невозможно сделать со встроенным пакетом re в Python, потому что он не поддерживает рекурсивный шаблон!

Чтобы решить эту проблему с помощью регулярного выражения в Python, вам необходимо установить regex package, который более совместим с PCRE .

В PCRE 4.0 и более поздних версиях введена рекурсия регулярных выражений, что позволяет повторно выполнить все или часть регулярного выражения для несопоставленного текста. Чтобы использовать рекурсивное регулярное выражение, вы используете (?R) или (?0). 
Когда обработчик регулярного выражения достигает значения (? R). Это говорит обработчику снова попытаться выполнить все регулярное выражение в текущей позиции в строке. Если вы хотите повторно выполнить определенную часть регулярного выражения, вы используете индекс группировки: (?1),(?2)

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

>>> import regex
>>> regex.search(r"(\w)((?R)|(\w?))\1", "kayak") is None
True
>>> regex.search(r"(\w)((?R)|(\w?))\1", "random") is None
False

Давайте проанализируем и разложим это регулярное выражение:

• (\w) соответствует одному буквенному символу. например: 'k'
• (\w)\1 соответствуют 2-ум одинаковым буквенным символам. \1 совпадает с тем же значением, что и (\w). Число 1 представляет положение группы. например: «аа» , «бб»
• (\w)(\w?)\1 соответствует 2-х или 3-х буквенным символам, где первый и последний равны. например: 'kak' , 'kk'
• (\w)(((\w)\4)|(\w?))\1 соответствует 3-м или 4-м символам палиндрома. Например: «Каак» или «Как»

С помощью (\w)(((\w)\4)|(\w?))\1 вы можете видеть, что мы повторяем ту же логику, чтобы добавить возможность сопоставлять палиндром на 1 символ длиннее, чем (\w)(\w?)\1. В идеале нам нужен способ сделать цикл или определить рекурсивный шаблон. Вы можете выразить, это с помощью ((?R)|(\w?)) которое применяет все регулярное выражение в текущей позиции или останавливаться, если 1 или 0 символов осталось обработать (\w?).

Вы можете играть с этим регулярным выражением по этой ссылке

Давайте вернемся к нашей первоначальной проблеме скобок. Используя то, что мы изучаем на примере палиндрома, мы можем написать регулярное выражение для его решения. 
Ответ ^(\((?1)*\))(?1)*$, давайте посмотрим на это регулярное выражение в действии:

>>> import regex
>>> regex.search(r"^(\((?1)*\))(?1)*$", "()()") is not None
True
>>> regex.search(r"^(\((?1)*\))(?1)*$", "(((()))())") is not None
True
>>> regex.search(r"^(\((?1)*\))(?1)*$", "()(") is not None
False
>>> regex.search(r"^(\((?1)*\))(?1)*$", "(((())())") is not None
False

Давайте проанализируем и разложим это регулярное выражение:

• ^ сопоставить с началом строки
• $ сопоставить с конецом строки
• (\(\)) сопоставлять открытые и закрывающие скобки ()
• (\((?R)?\)) сопоставлять скобки как ((()))
• (\((?R)*\)) сопоставлять скобки как (()()())
• (\((?1)*\))(?1)* матчим круглые скобки , как, (()()())(()) где ?1 находится в (\((?1)*\))
• ^(\((?1)*\))(?1)*$ мы добавляем ^ и $

Вы можете играть с этим регулярным выражением по этой ссылке

Если вы спросите о производительности, то код Python, который мы написали в начале, более производительный:

>>> import regex

>>> %timeit -n1000 check("(()())") 
1000 loops, best of 3: 1.81 µs per loop

>>> %timeit -n1000 regex.search(r"^(\((?1)*\))(?1)*$", "(()())")
1000 loops, best of 3: 13 µs per loop

>>> comp = regex.compile(r"^(\((?1)*\))(?1)*$")
>>> %timeit -n1000 comp.match("(()())")
1000 loops, best of 3: 7.49 µs per loop

Приведенный выше синтаксис является базой, на ipython которой позволяют выполнять timeit синтаксический сахар %timeit.

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

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