23.5. Проблема
Потоки ввода-вывода и класс
string
помогают нам считывать и записывать последовательности символов, хранить их и выполнять над ними основные операции. Однако при работе с текстом во многих случаях необходимо анализировать контекст строки или рассматривать много аналогичных строк. Рассмотрим тривиальный пример. Возьмем сообщение электронной почты (последовательность слов) и посмотрим, содержит ли оно аббревиатуру U.S. и почтовый код (две буквы, за которыми следуют пять цифр).
string s;
while (cin>>s) {
if (s.size()==7
&& isalpha(s[0]) && isalpha(s[1])
&& isdigit(s[2]) && isdigit(s[3]) && isdigit(s[4])
&& isdigit(s[5]) && isdigit(s[6]))
cout << " найдена " << s << '\n';
}
Здесь значение
isalpha(x)
равно
true
, если
x
— это буква, а значение
isdigit(x)
равно
true
, если
x
— цифра (см. раздел 11.6). В этом (слишком) простом решении кроется несколько проблем.
• Оно громоздко (четыре строки, восемь вызовов функций).
• Мы пропускаем (умышленно?) почтовые индексы, не отделенные от своего контекста пробелом (например, "TX77845", TX77845–1234 и ATX77845).
• Мы пропускаем (умышленно?) почтовые индексы с пробелом между буквами и цифрами (например, TX 77845).
• Мы принимаем (умышленно?) почтовые индексы, в которых буквы набраны в нижнем регистре (например, tx77845).
• Если вы решите проанализировать почтовые индексы, имеющие другой формат (например, CB3 0FD), то будете вынуждены полностью переписать весь код.
Должен быть более хороший способ! Перед тем как его описать, рассмотрим поставленные задачи. Предположим, что мы хотим сохранить “старый добрый код”, дополнив его обработкой указанных ситуаций.
• Если мы хотим обрабатывать не один формат, то следует добавить инструкцию
if
или
switch
.
• Если мы хотим учитывать верхний и нижний регистры, то должны явно конвертировать строки (обычно в нижний регистр) или добавить дополнительную инструкцию
if
.
• Мы должны как-то (как?) описать контекст, в котором выполняется поиск. Это значит, что мы должны работать с отдельными символами, а не со строками, т.е. потерять многие преимущества, предоставляемые потоками
iostream
(см. раздел 7.8.2).
Если хотите, попробуйте написать код в этом стиле, но нам очевидно, что в этом случае вы запутаетесь в сети инструкций
if
, предназначенных для обработки особых ситуаций. Даже в этом простом примере мы стоим перед выбором (например, учитывать ли пяти- и девятизначные почтовые индексы). Во многих других примерах нам необходимо работать с восклицательными знаками (например, любым количеством цифр, за которыми следует знак восклицания, такими как
123!
и
123456!
). В конце концов, нельзя забывать о префиксах и суффиксах. Как мы уже указывали (см. разделы 11.1 и 11.2), предпочтения пользователей по отношению к разным форматам не ограничиваются стремлением программистов к систематичности и простоте. Просто подумайте о разнообразных способах записи одной только даты.
2007–06–05
June 5, 2007
jun 5, 2007
5 June 2007
6/5/2007
5/6/07
...
В этот момент, если не раньше, опытный программист воскликнет: “Должен быть более хороший способ!” (чем нагромождение ординарного кода) и станет его искать. Простейшим и наиболее широко распространенным решением этой задачи является использование так называемых регулярных выражений (regular expressions).
Регулярные выражения являются основой большинства методов обработки текстов и команды
grep
в системе Unix (см. упр. 8), а также важной частью языков программирования, интенсивно применяющихся для решения этих задач (таких как AWK, Perl и PHP).
Регулярные выражения, которые мы будем использовать, реализованы в библиотеке, которая станет частью следующего стандарта языка С++ (C++0x). Они сопоставимы с регулярными выражениями из языка Perl. Этой теме посвящено много книг, учебников и справочников, например, рабочий отчет комитета по стандартизации языка C++ (в сети веб он известен под названием WG21), документация Джона Мэддокса (John Maddock)
boost::regex
и учебники по языку Perl. Здесь мы изложим фундаментальные понятия, а также основные и наиболее полезные способы использования регулярных выражений.
ПОПРОБУЙТЕ
В последних двух абзацах “неосторожно” упомянуты несколько имен и аббревиатур без каких-либо объяснений. Поищите в веб информацию о них.
23.6. Идея регулярных выражений
Основная идея регулярного выражения заключается в том, что оно определяет шаблон (pattern), который мы ищем в тексте. Посмотрим, как мы могли бы точно описать шаблон простого почтового кода, такого как TX77845. Результат первой попытки выглядит следующим образом:
wwddddd
где символ w означает любую букву, а символ d — любую цифру. Мы используем символ w (от слова “word”), поскольку символ l (от слова “letter”) слишком легко перепутать с цифрой 1. Эти обозначения вполне подходят для нашего простого примера, но что произойдет, если мы попробуем применить их для описания формата почтового кода, состоящего из девяти цифр (например, TX77845–5629). Что вы скажете о таком решении?
wwddddd–dddd
Они выглядят вполне логичными, но как понять, что символ
d означает “любая цифра”, а знак
– означает “всего лишь” дефис? Нам необходимо как-то указать, что символы
w и
d являются специальными: они представляют классы символов, а не самих себя (символ
w означает “
a или
b или c или
...”, а символ
d означает “
1 или
2, или
3, или
...”). Все это слишком сложно. Добавим к букве, обозначающей имя класса символов, обратную косую черту, как это сделано в языке С++ (например, символ
\n означает переход на новую строку). В этом случае получим такую строку:
\w\w\d\d\d\d\d–\d\d\d\d
Выглядит довольно некрасиво, но, по крайней мере, мы устранили неоднозначность, а обратные косые черты ясно обозначают то, что за ними следует “нечто необычное”. Здесь повторяющиеся символы просто перечислены один за другим. Это не только утомительно, но и провоцирует ошибки. Вы можете быстро сосчитать, что перед обратной косой чертой до дефиса действительно стоят пять цифр, а после — четыре? Мы смогли, но просто сказать 5 и 4 мало, чтобы в этом убедиться, поэтому придется их пересчитать. После каждого символа можно было бы поставить счетчик, указывающий количество его повторений.
