| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > C/C++: Общие вопросы > Трабла с реализацией алгоритма... |
| Автор: BreakPointMAN 9.5.2005, 22:56 |
| Вообщем, если кто-нибудь что-то может посоветовать, как энто реализовать - буду премного благодарен... )) Требуется написать класс, конструктор которого принимает шаблонную строку особого вида (формат которой описан ниже), и в котором имеется функция, принимающая некую строку и проверяющую ее на соответствие шаблону. Функция должна возвращать -1, если в переданной ей строке нет подстрок, отвечающих требованию шаблона, либо смещение, указывающее на начало подходящей подстроки. Формат шаблона следующий: \xHH - задает ASCII-код символа в 16-ричном виде; (\xHH-\xHH) - задает символ, ASCII-код которого находится в заданном диапазоне [] - задает список необязательных элементов {} - задает список обязательных элементов Т.е., если отвлечься от того, что символы задаются с помощью 16-ричных кодов в виде \xHH, где H- шестнадцатеричная цифра, и опустить задание диапазона ASCII-кодов символа, то шаблон может выглядеть примерно так: "[a]{b|cd}[ef{g|[h]i}]" и ему соответствуют строки: ab acd b cd abefg abefi abefhi acdefg acdefi acdefhi befg befi befhi cdefg cdefi cdefhi Есть смутное предположение, что тут не обойтись без дерева, но какого именно, как его строить и как обходить - это вопрос. ps: воспользоваться регулярными выражениями не предлать, здесь немного другая ситуация... |
| Автор: BreakPointMAN 13.5.2005, 20:57 |
| Быть может, кто-нибудь сталкивался с подобной задачей? Насколько я понял, варианта здесь может быть два. 1-ый, достаточно простой, но не рациональный - построить дерево и потом проверку делать по нему. Вся фигня в том, что шаблон недетерминированный, в нем есть необязательные элементы, и дерево должно по два раза включать одни и те же элементы - сначала с необяхательными элементами, потом без них... распухнет оно до невообразимых размеров, да и работать это будет долго. 2-ой, правильный - через автоматы. Тут уже трабла, в автоматах я постольку поскольку... (( Если у кого-нибудь есть какие-то соображения, plz... )) Уже неделю голову ломаю. ps: достал пару исходников по регэкспам, но это death в них разбираться... указатель на указателе скачет, куча свитчей, циклов и рекурсий. И почти без комментариев... (( |
| Автор: maxim1000 14.5.2005, 12:53 |
| http://forum.vingrad.ru/index.php?showtopic=37306&hl=маска это, конечно, не решение именно этой проблемы, но думаю. может оказаться полезным... |
| Автор: BreakPointMAN 16.5.2005, 18:44 |
| Да, спасибо, это интересно, ...хотя и не совсем то, что нужно. |
| Автор: BreakPointMAN 24.5.2005, 21:29 |
| |
| Автор: Guest 9.6.2005, 23:11 |
| У меня тоже похожая проблема... только формат шаблона немного другой... Народ, может кто-нибудь что-нибудь посоветует????? |