Форум программистов
 
Регистрация на форуме тут, о проблемах пишите сюда - alarforum@yandex.ru, проверяйте папку спам! Обязательно пройдите активизацию e-mail, а тут можно восстановить пароль

Купить рекламу на форуме 15-35 тыс рублей в месяц

Вернуться   Форум программистов > C/C++ программирование > Общие вопросы C/C++
Регистрация

Восстановить пароль
Повторная активизация e-mail

Ответ
 
Опции темы Поиск в этой теме
Старый 05.11.2010, 20:57   #1
1datr
Пользователь
 
Регистрация: 04.03.2008
Сообщений: 16
По умолчанию Regexp на чистом С++

Надо реализовать простое regexp на чистом С++ (без сторонних либ), но желательно чтобы с возможностью последующего расширения. Какой способ лучше? Конечный автомат или с помощью функций типа strstr?
Формат такой:*- любое количество любых символов, ? - один некий символ
Типа: *some??ing*_*sp????l*

Последний раз редактировалось 1datr; 05.11.2010 в 21:11.
1datr вне форума Ответить с цитированием
Старый 05.11.2010, 21:44   #2
still_alive
Great Code Monkey
Форумчанин
 
Аватар для still_alive
 
Регистрация: 09.08.2007
Сообщений: 533
По умолчанию

Конечные автоматы безусловно спасут отца русской демократии)

Тут выбор немного в другом.
По регулярному выражению можно построить как детерминированный, так и недетерминированный конечный автомат. Если один и тот же автомат должен проверять на допустимость большое число цепочек, то дешевле построить сразу ДКА (есть такой алгоритм построения) и моделировать его. Скажем, если пользователь делает fa.setRegExp(expr), а потом кучу fa.isAcceptable(s1), fa.isAcceptable(s2), ... - то лучше ДКА. Естественно, после построения ДКА нужно минимизировать количество его возможных состояний.

Если же нужно проверять небольшое число - достаточно моделирования НКА. Это в случае вызовов fa.isAcceptable(regexp1, s1), fa.isAcceptable(regexp2, s2), ... НКА из регулярного выражения строится по алгоритму Томпсона, но чтобы его можно было проще реализовать, перед его вызовом стоит привести регулярное выражение к постфиксной форме и явно добавить оператор конкатенации.

А если пользователь дурак и вызывает fa.isAcceptable(regexp, s1), fa.isAcceptable(regexp, s2), ... то можно это отследить и неявно преобразовать НКА в ДКА.

Если вверху все сложно и вопросы производительности тебе не сдались, то берешь любой: хоть НКА, хоть ДКА, хоть приведенный, хоть нет)

В общем, используй КА) Просто, очень расширяемо, удобно и хорошо для отладки.
still_alive вне форума Ответить с цитированием
Ответ
Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
как исключить слова RegExp kroŧ Общие вопросы Delphi 0 24.10.2010 18:40
Дисассемблировал прогу на чистом API... Олвин Win Api 2 11.04.2010 22:01
Компиляция в чистом QT JoberLord Qt и кроссплатформенное программирование С/С++ 7 08.04.2010 10:09
C++ Builder RegExp Namolem Помощь студентам 1 19.01.2010 23:13
выделить из строки (regexp) NieL Общие вопросы Delphi 2 23.06.2009 08:21