Введение

Регулярные выражения используются для сжатого описания некоторого множества строк с помощью шаблонов, без необходимости перечисления всех элементов этого множества или явного написания функции для проверки. Большинство символов соответствуют сами себе («a» соответствует «a» и т. д.). Исключения из этого правила называются метасимволами: +-*/()^$.!?{}[]\|.

Термин «Регулярные выражения» является переводом с английского словосочетания "Regular expressions". Перевод не очень точно отражает смысл, правильнее было бы «шаблонные выражения». Регулярное выражение, или коротко «регулярка», состоит из обычных символов и специальных командных последовательностей. Например, \d задаёт любую цифру, а \d+ — задает любую последовательность из одной или более цифр.

Работа с регулярками реализована во всех современных языках программирования. Однако существует несколько «диалектов», поэтому функционал регулярных выражений может различаться от языка к языку. В некоторых языках программирования регулярками пользоваться очень удобно (например, в питоне), в некоторых — не слишком (например, в C++).

Примеры регулярных выражений

Сила и ответственность

Регулярные выражения, или коротко, регулярки — это очень мощный инструмент. Но использовать их следует с умом и осторожностью, и только там, где они действительно приносят пользу, а не вред. Во-первых, плохо написанные регулярные выражения работают медленно. Во-вторых, их зачастую очень сложно читать, особенно если регулярка написана не лично тобой пять минут назад. В-третьих, очень часто даже небольшое изменение задачи (того, что требуется найти) приводит к значительному изменению выражения. Поэтому про регулярки часто говорят, что это write only code (код, который только пишут с нуля, но не читают и не правят). А также шутят: Некоторые люди, когда сталкиваются с проблемой, думают «Я знаю, я решу её с помощью регулярных выражений.» Теперь у них две проблемы.

Вот пример write-only регулярки (для проверки валидности e-mail адреса (не надо так делать!!!)):
(?:[a-z0-9!#$%&'*+/=?^_`{|}~-]+(?:\.[a-z0-9!#$%&'*+/=?^_`{|}~-]+)*|"(?:[\x01-\x08\x0b\x0c\x0e-\x1f\x21\x23-\x5b\x5d-\x7f]|
\\[\x01-\x09\x0b\x0c\x0e-\x7f])*")@(?:(?:[a-z0-9](?:[a-z0-9-]*[a-z0-9])?\.)+[a-z0-9](?:[a-z0-9-]*[a-z0-9])?|\[(?:(?:25[0-5]|
2[0-4][0-9]|[01]?[0-9][0-9]?)\.){3}(?:25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9]?|[a-z0-9-]*[a-z0-9]:
(?:[\x01-\x08\x0b\x0c\x0e-\x1f\x21-\x5a\x53-\x7f]|\\[\x01-\x09\x0b\x0c\x0e-\x7f])+)\])

А вот здесь более точная регулярка для проверки корректности email адреса стандарту RFC822. Если вдруг будете проверять email, то не делайте так! :) Если адрес вводит пользователь, то пусть вводит почти что угодно, лишь бы там была собака. Надёжнее всего отправить туда письмо и убедиться, что пользователь может его получить.

Документация и ссылки

• Оригинальная документация: https://docs.python.org/3/library/re.html;
• Очень подробный и обстоятельный материал: https://www.regular-expressions.info/;
• Разные сложные трюки и тонкости с примерами: http://www.rexegg.com/;
• Весьма приличный текст на русском с примерами;
• Викиучебник;
• Он-лайн отладка регулярок https://regex101.com (не забудьте поставить галочку Python в разделе FLAVOR слева);
• Он-лайн визуализация регулярок https://www.debuggex.com/ (не забудьте выбрать Python);
• Могущественный текстовый редактор Sublime text 3, в котором очень удобный поиск по регуляркам;
• Если вы используете Linux/Mac, то регулярки там можно использовать в командной строке с grep, в Vim/Emacs/...;

Основы синтаксиса

Любая строка (в которой нет символов .^$*+?{}[]\|()) сама по себе является регулярным выражением. Так, выражению Хаха будет соответствовать строка “Хаха” и только она. Регулярные выражения являются регистрозависимыми, поэтому строка “хаха” (с маленькой буквы) уже не будет соответствовать выражению выше. Подобно строкам в языке Python, регулярные выражения имеют спецсимволы .^$*+?{}[]\|(), которые в регулярках являются управляющими конструкциями. Для написания их просто как символов требуется их экранировать, для чего нужно поставить перед ними знак \. Так же, как и в питоне, в регулярных выражения выражение \n соответствует концу строки, а \t — табуляции.

Шаблоны, соответствующие одному символу

.

м.л.ко

\d

СУ\d\d

\D

926\D123

\s

бор\sода

\S

\S123

\w

\w\w\w

\W

сом\W

[..]

[0-9][0-9A-Fa-f]

[eyuoia]

[\s\d]

[^..]

<[^>]>

\d≈[0-9], \D≈[^0-9], 
\w≈[0-9a-zA-Zа-яА-ЯёЁ]
\s≈[ \f\n\r\t\v]

[abc-], [-1]

[*[(+\\\]\t]

\b

\bвал

\bвал\b

\B

\Bвал

\Bвал\B

Разминка — 1

Квантификаторы (указание количества повторений)

\d{4}

\d{2,4}

\d{3,}

\d{,2}

валы?

СУ\d*

a\)+

\(.*\)

\(.*?\)

Жадность в регулярках и границы найденного шаблона

Как указано выше, по умолчанию квантификаторы жадные. Скажем, шаблон \d+ захватывает максимально возможное количество цифр. Поэтому можно быть уверенным, что перед найденным шаблоном не идёт цифра, и после не идёт цифра. Однако если в шаблоне есть не жадные части (например, явный текст), то всё становится гораздо сложнее: шаблону 1\d+9 в строке 0001555559000 соответствует 1555559. Про жадность и лень будут подробности ниже.

Пересечение подстрок

В обычной ситуации регулярки позволяют найти только непересекающиеся шаблоны. Вместе с проблемой границы слова это делает их использование в некоторых случаях более сложным. Например, если мы решим искать e-mail адреса при помощи регулярки \w+@\w+, может найтись вот что:
foo@boo@goo@moo@roo@zoo
То есть это с одной стороны и не e-mail, а с другой стороны это не все подстроки вида текст-собака-текст, так как boo@goo и moo@roo пропущены.

Разминка — 2

Регулярки в реальной жизни

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

Другой пример задач — это задачи валидации. Например, валидация номера машины, номера телефона, номера паспорта, валидация числа, email'а и т.п. Такие задачи требуют строгой проверки, они должны пропускать все правильные, и не пропускать ни одну неправильную. В таких задачах будут тесты на все возможные отклонения.

The Greedy Trap, The Lazy Trap, The Ugly Trap

Сравним поведение жадного и ленивого квантивикатора:

Регулярки в питоне

Функции для работы с регулярками живут в модуле re. Основные функции:

Пример использования всех основных функций

import re

match = re.search(r'\d\d\D\d\d', r'Телефон 123-12-12')
print(match.group(0) if match else 'Not found')
# -> 23-12
match = re.search(r'\d\d\D\d\d', r'Телефон 1231212')
print(match.group(0) if match else 'Not found')
# -> Not found

match = re.fullmatch(r'\d\d\D\d\d', r'12-12')
print('YES' if match else 'NO')
# -> YES
match = re.fullmatch(r'\d\d\D\d\d', r'Т. 12-12')
print('YES' if match else 'NO')
# -> NO

print(re.split(r'\W+', 'Где, скажите мне, мои очки??!'))
# -> ['Где', 'скажите', 'мне', 'мои', 'очки', '']

print(re.findall(r'\d\d\.\d\d\.\d{4}',
                 r'Эта строка написана 19.01.2018, а могла бы и 01.09.2017'))
# -> ['19.01.2018', '01.09.2017']

for m in re.finditer(r'\d\d\.\d\d\.\d{4}', r'Эта строка написана 19.01.2018, а могла бы и 01.09.2017'):
    print('Дата', m.group(0), 'начинается с позиции', m.start())
# -> Дата 19.01.2018 начинается с позиции 20
# -> Дата 01.09.2017 начинается с позиции 45

print(re.sub(r'\d\d\.\d\d\.\d{4}',
             r'DD.MM.YYYY',
             r'Эта строка написана 19.01.2018, а могла бы и 01.09.2017'))
# -> Эта строка написана DD.MM.YYYY, а могла бы и DD.MM.YYYY

Тонкости экранирования в питоне ('\\\\\\\\foo')

Так как символ \ в питоновских строках также необходимо экранировать, то в результате в шаблонах могут возникать конструкции вида '\\\\par'. Первый слеш означает, что следующий за ним символ нужно оставить «как есть». Третий также. В результате с точки зрения питона '\\\\' означает просто два слеша \\. Теперь с точки зрения движка регулярных выражений, первый слеш экранирует второй. Тем самым как шаблон для регулярки '\\\\par' означает просто текст \par. Для того, чтобы не было таких нагромождений слешей, перед открывающей кавычкой нужно поставить символ r, что скажет питону «не рассматривай \ как экранирующий символ (кроме случаев экранирования открывающей кавычки)». Соответственно можно будет писать r'\\par'.

Использование дополнительных флагов в питоне

import re
print(re.findall(r'\d+', '12 + ٦٧'))
# -> ['12', '٦٧']
print(re.findall(r'\w+', 'Hello, мир!'))
# -> ['Hello', 'мир']
print(re.findall(r'\d+', '12 + ٦٧', flags=re.ASCII))
# -> ['12']
print(re.findall(r'\w+', 'Hello, мир!', flags=re.ASCII))
# -> ['Hello']
print(re.findall(r'[уеыаоэяию]+', 'ОООО ааааа ррррр ЫЫЫЫ яяяя'))
# -> ['ааааа', 'яяяя']
print(re.findall(r'[уеыаоэяию]+', 'ОООО ааааа ррррр ЫЫЫЫ яяяя', flags=re.IGNORECASE))
# -> ['ОООО', 'ааааа', 'ЫЫЫЫ', 'яяяя']

text = r"""
Торт
с вишней1
вишней2
"""
print(re.findall(r'Торт.с', text))
# -> []
print(re.findall(r'Торт.с', text, flags=re.DOTALL))
# -> ['Торт\nс']
print(re.findall(r'виш\w+', text, flags=re.MULTILINE))
# -> ['вишней1', 'вишней2']
print(re.findall(r'^виш\w+', text, flags=re.MULTILINE))
# -> ['вишней2']

Написание и тестирование регулярных выражений

Для написания и тестирования регулярных выражений удобно использовать сервис https://regex101.com (не забудьте поставить галочку Python в разделе FLAVOR слева) или текстовый редактор Sublime text 3.

Замечание по вводу-выводу

Прочитать весь текст разом из стандартного ввода можно при помощи строчек

import sys
text = sys.stdin.read()

text = open('input.txt', encoding='utf-8').read()

В тестах не будет излишнего занудства. То есть сокращения \d, \w можно использовать достаточно вольно, если не написано обратного. Специально злые сценарии будут только в задачах на валидацию.

Скобочные группы (?:...) и перечисления |

Перечисления (операция «ИЛИ»)

Чтобы проверить, удовлетворяет ли строка хотя бы одному из шаблонов, можно воспользоваться аналогом оператора or, который записывается с помощью символа |. Так, некоторая строка подходит к регулярному выражению A|B тогда и только тогда, когда она подходит хотя бы к одному из регулярных выражений A или B. Например, отдельные овощи в тексте можно искать при помощи шаблона морковк|св[её]кл|картошк|редиск.

Скобочные группы (группировка плюс квантификаторы)

Зачастую шаблон состоит из нескольких повторяющихся групп. Так, MAC-адрес сетевого устройства обычно записывается как шесть групп из двух шестнадцатиричных цифр, разделённых символами - или :. Например, 01:23:45:67:89:ab. Каждый отдельный символ можно задать как [0-9a-fA-F], и можно весь шаблон записать так:

[0-9a-fA-F]{2}[:-][0-9a-fA-F]{2}[:-][0-9a-fA-F]{2}[:-][0-9a-fA-F]{2}[:-][0-9a-fA-F]{2}[:-][0-9a-fA-F]{2}

Ситуация становится гораздо сложнее, когда количество групп заранее не зафиксировано. Чтобы разрешить эту проблему в синтаксисе регулярных выражений есть группировка (?:...). Можно писать круглые скобки и без значков ?:, однако от этого у группировки значительно меняется смысл, регулярка начинает работать гораздо медленнее. Об этом будет написано ниже. Итак, если REGEXP — шаблон, то (?:REGEXP) — эквивалентный ему шаблон. Разница только в том, что теперь к (?:REGEXP) можно применять квантификаторы, указывая, сколько именно раз должна повториться группа. Например, шаблон для поиска MAC-адреса, можно записать так:

[0-9a-fA-F]{2}(?:[:-][0-9a-fA-F]{2}){5}

Скобки плюс перечисления

Также скобки (?:...) позволяют локализовать часть шаблона, внутри которой происходит перечисление.
Например, шаблон (?:он|тот) (?:шёл|плыл) соответствует каждой из строк «он шёл», «он плыл», «тот шёл», «тот плыл», и является синонимом он шёл|он плыл|тот шёл|тот плыл.

Ещё примеры

(?:[а-я][а-я]\d\d)+

(?:[а-я]+\d+)+

(?:\+7|8)(?:-\d{2,3}){4}

(?:[Хх][аоеи]+)+

\b(?:[Хх][аоеи]+)+\b

Группирующие скобки (...) и match-объекты в питоне

Match-объекты

Если функции re.search, re.fullmatch не находят соответствие шаблону в строке, то они возвращают None, функция re.finditer возващает пустой итератор. Однако если соответствие найдено, то возвращается match-объект. Эта штука содержит в себе кучу полезной информации о соответствии шаблону. В отличие от предыдущих функций, re.findall возвращает «простой и понятный» список соответствий. Полный набор атрибутов match-объекта можно посмотреть в документации, а здесь приведём самое полезное.

Группирующие скобки (...)

Если в шаблоне регулярного выражения встречаются скобки (...) без ?:, то они становятся группирующими. В match-объекте, который возвращают re.search, re.fullmatch и re.finditer, по каждой такой группе можно получить ту же информацию, что и по всему шаблону. А именно часть подстроки, которая соответствует (...), а также индексы начала и окончания в исходной строке. Достаточно часто это бывает полезно.

import re
pattern = r'\s*([А-Яа-яЁё]+)(\d+)\s*'
string = r'---   Опять45   ---'
match = re.search(pattern, string)
print(f'Найдена подстрока >{match.group(0)}< с позиции {match.start(0)} до {match.end(0)}')
print(f'Группа букв >{match.group(1)}< с позиции {match.start(1)} до {match.end(1)}')
print(f'Группа цифр >{match.group(2)}< с позиции {match.start(2)} до {match.end(2)}')
###
# Найдена подстрока >   Опять45   < с позиции 3 до 16
# Группа букв >Опять< с позиции 6 до 11
# Группа цифр >45< с позиции 11 до 13

Тонкости со скобками и нумерацией групп.

Если к группирующим скобкам применён квантификатор (то есть указано число повторений), то подгруппа в match-объекте будет создана только для последнего соответствия. Например, если бы в примере выше квантификаторы были снаружи от скобок '\s*([А-Яа-яЁё])+(\d)+\s*', то вывод был бы таким:

Найдена подстрока >   Опять45   < с позиции 3 до 16
Группа букв >ь< с позиции 10 до 11
Группа цифр >5< с позиции 12 до 13

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

import re
pattern = r'((\d)(\d))((\d)(\d))'
string = r'123456789'
match = re.search(pattern, string)
print(f'Найдена подстрока >{match.group(0)}< с позиции {match.start(0)} до {match.end(0)}')
for i in range(1, match.groups()+1):
    print(f'Группа №{i} >{match.group(i)}< с позиции {match.start(i)} до {match.end(i)}')
###
Найдена подстрока >1234< с позиции 0 до 4
Группа №1 >12< с позиции 0 до 2
Группа №2 >1< с позиции 0 до 1
Группа №3 >2< с позиции 1 до 2
Группа №4 >34< с позиции 2 до 4
Группа №5 >3< с позиции 2 до 3
Группа №6 >4< с позиции 3 до 4

Группы и re.findall

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

import re
print(re.findall(r'([a-z]+)(\d*)', r'foo3, im12, go, 24buz42'))
# -> [('foo', '3'), ('im', '12'), ('go', ''), ('buz', '42')]

Группы и re.split

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

import re
print(re.split(r'(\s*)([+*/-])(\s*)', r'12  +  13*15   - 6'))
# -> ['12', '  ', '+', '  ', '13', '', '*', '', '15', '   ', '-', ' ', '6']

import re
print(re.split(r'\s*([+*/-])\s*', r'12  +  13*15   - 6'))
# -> ['12', '+', '13', '*', '15', '-', '6']

Разминка — 3

Использование групп при заменах

Использование групп добавляет замене (re.sub, работает не только в питоне, а почти везде) очень удобную возможность: в шаблоне для замены можно ссылаться на соответствующую группу при помощи \1, \2, \3, .... Например, если нужно даты из неудобного формата ММ/ДД/ГГГГ перевести в удобный ДД.ММ.ГГГГ, то можно использовать такую регулярку:

import re
text = "We arrive on 03/25/2018. So you are welcome after 04/01/2018."
print(re.sub(r'(\d\d)/(\d\d)/(\d{4})', r'\2.\1.\3', text))
# -> We arrive on 25.03.2018. So you are welcome after 01.04.2018.

Если групп больше 9, то можно ссылаться на них при помощи конструкции вида \g<12>.

Замена с обработкой шаблона функцией в питоне

Ещё одна питоновская фича для регулярных выражений: в функции re.sub вместо текста для замены можно передать функцию, которая будет получать на вход match-объект и должна возвращать строку, на которую и будет произведена замена. Это позволяет не писать ад в шаблоне для замены, а использовать удобную функцию. Например, «зацензурим» все слова, начинающиеся на букву «Х»:

import re
def repl(m):
    return '>censored(' + str(len(m.group(0))) + ')<'
text = "Некоторые хорошие слова подозрительны: хор, хоровод, хороводоводовед."
print(re.sub(r'\b[хХxX]\w*', repl, text))
# -> Некоторые >censored(7)< слова подозрительны: >censored(3)<, >censored(7)<, >censored(15)<.

Ссылки на группы при поиске

При помощи \1, \2, \3, ... и \g<12> можно ссылаться на найденную группу и при поиске (backrefs). Необходимость в этом встречается не так часто, но это бывает полезно при обработке простых xml и html.

Только пообещайте, что не будете парсить сложный xml и тем более html при помощи регулярок! Регулярные выражения для этого не подходят. Используйте другие инструменты. Каждый раз, когда неопытный программист парсит html регулярками, в мире умирает котёнок. Если кажется «Да здесь очень простой html, напишу регулярку», то сразу вспоминайте шутку про две проблемы. Не нужно пытаться парсить html регулярками, даже Пётр Митричев не сможет это сделать в общем случае :) Использование регулярных выражений при парсинге html подобно залатыванию резиновой лодки шилом. Закон Мёрфи для парсинга html и xml при помощи регулярок гласит: парсинг html и xml регулярками иногда работает, но в точности до того момента, когда правильность результата будет очень важна.

Используйте lxml и beautiful soup.

import re
text = "SPAM <foo>Here we can <boo>find</boo> something interesting</foo> SPAM"
print(re.search(r'<(\w+?)>.*?</\1>', text)[0])
# -> <foo>Here we can <boo>find</boo> something interesting</foo>
text = "SPAM <foo>Here we can <foo>find</foo> OH, NO MATCH HERE!</foo> SPAM"
print(re.search(r'<(\w+?)>.*?</\1>', text)[0])
# -> <foo>Here we can <foo>find</foo>

Разминка — 4

Шаблоны, соответствующие не конкретному тексту, а позиции

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

Простые шаблоны, соответствующие позиции

^

^Привет

$

Будь здоров!$

\A

\Z

\b

\bвал

\B

\Bвал

Разминка — 5

Сложные шаблоны, соответствующие позиции (lookaround и Co)

Следующие шаблоны применяются в основном в тех случаях, когда нужно уточнить, что должно идти непосредственно перед или после шаблона, но при этом не включать найденное в match-объект. В принципе, это можно сделать и при помощи группирующих скобок, однако наиболее существенная польза lookaround'ов в том, что по ним шаблоны могут пересекаться!

(?=...)

Isaac (?=Asimov)

(?!...)

Isaac (?!Asimov)

(?<=...)

(?<=abc)def

(?<!...)

(?<!abc)def

На всякий случай ещё раз. Каждый их этих шаблонов проверяет лишь то, что идёт непосредственно перед позицией или непосредственно после позиции. Если пару таких шаблонов написать рядом, то проверки будут независимы (то есть будут соответствовать AND в каком-то смысле).

lookaround на примере королей и императоров Франции

КарлIV, КарлIX, КарлV, КарлVI, КарлVII, КарлVIII,
ЛюдовикIX, ЛюдовикVI, ЛюдовикVII, ЛюдовикVIII, ЛюдовикX, ..., ЛюдовикXVIII,
ФилиппI, ФилиппII, ФилиппIII, ФилиппIV, ФилиппV, ФилиппVI

КарлIV, КарлIX, КарлV, КарлVI, КарлVII, КарлVIII,
ЛюдовикIX, ЛюдовикVI, ЛюдовикVII, ЛюдовикVIII, ЛюдовикX, ..., ЛюдовикXVIII,
ФилиппI, ФилиппII, ФилиппIII, ФилиппIV, ФилиппV, ФилиппVI

КарлIV, КарлIX, КарлV, КарлVI, КарлVII, КарлVIII,
ЛюдовикIX, ЛюдовикVI, ЛюдовикVII, ЛюдовикVIII, ЛюдовикX, ..., ЛюдовикXVIII,
ФилиппI, ФилиппII, ФилиппIII, ФилиппIV, ФилиппV, ФилиппVI

КарлIV, КарлIX, КарлV, КарлVI, КарлVII, КарлVIII,
ЛюдовикIX, ЛюдовикVI, ЛюдовикVII, ЛюдовикVIII, ЛюдовикX, ..., ЛюдовикXVIII,
ФилиппI, ФилиппII, ФилиппIII, ФилиппIV, ФилиппV, ФилиппVI

Ещё примеры

(?<!\d)\d(?!\d)

(?<=#START#).*?(?=#END#)

\d+(?=_(?!_))

^(?:(?!boo).)*?$

a foo and
boo and zoo
and others

^(?:(?!boo)(?!foo).)*?$

a foo and
boo and zoo
and others

Прочие фичи

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

Гробы на закуску

Источник идей и иногда заданий целиком: SPOJ и regex golf project.