http://softcraft.ru
| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Трабла с реализацией алгоритма |
| Автор: BreakPointMAN 16.5.2005, 18:41 |
| Вообщем, если кто-нибудь что-то может посоветовать, как энто реализовать - буду премного благодарен... )) Требуется написать класс (c++ -> Builder 6, если кому интересно... но это не суть важно), конструктор которого принимает шаблонную строку особого вида (формат которой описан ниже), и в котором имеется функция, принимающая некую строку и проверяющую ее на соответствие шаблону. Функция должна возвращать -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 Как можно реализовать это дело? Через дерево? Тогда как его строить и как обходить? Через автоматы? А с чем это дело едят?.. .......... вариант "использовать готовую библиотеку для работы с рег.выр." не совсем подходит, хотя бы потому что интересно разобраться самому в том, как оно работает... |
| Автор: SoWa 17.5.2005, 14:16 |
| Циклы, Парсинг, поиск в тексте, куча условий. Вот и все! Разбираешь все группы элементов, потом сравниваешь с входными |
| Автор: BreakPointMAN 20.5.2005, 21:19 |
| Ну-ну... а как прикажешь быть со вложенностью скобок? Причем возможно многократной? Да если скобок здесь два вида - для задания просто перечисления и для задания необязательных элементов? А как быть с шаблонами вида: "[a]{a|b|c}"? Строка "a" здесь подходит, верно? А как реализовать проверку, чтобы она на таком тесте не завалилась? |
| Автор: Sardar 21.5.2005, 00:16 |
| BreakPointMAN контекстно-свободная грамматика тебя выручит в любом случае http://softcraft.ru |
| Автор: BreakPointMAN 24.5.2005, 21:28 | ||
Спасибо, очень интересный ресурс!  |