Трабла с реализацией алгоритма

Тема в разделе "Общие вопросы по С и С++", создана пользователем BreakPointMAN, 10 май 2005.

Статус темы:
Закрыта.
  1. BreakPointMAN

    BreakPointMAN Гость

    Вообщем, если кто-нибудь что-то может посоветовать, как энто реализовать - буду премного благодарен... ))

    Требуется написать класс, конструктор которого принимает шаблонную строку особого вида (формат которой описан ниже), и в котором имеется функция, принимающая некую строку и проверяющую ее на соответствие шаблону. Функция должна возвращать -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: воспользоваться регулярными выражениями не предлать, здесь немного другая ситуация...
     
  2. Guest

    Guest Гость

    Поскольку тебе надо написать собственную реализацию упрощенных RegExp, то и смотри открытые реализации. Можно и автоматами, и деревьями и еще как-то там.
     
  3. BreakPointMAN

    BreakPointMAN Гость

    Спасибо за совет...

    Деревьями - непрактично... (( в шаблоне есть необязательные элементы, если строить дерево, то оно по два раза будет дублировать одни и те же ветки - сначала через необязательные элементы, потом без них... Долго и память жрет... ((

    Автоматы... БЛИИИН! У кого-нить по этой теме что-нибудь есть? Я не представляю, как это реализуется. ((
     
  4. Guest

    Guest Гость

    Я же тебе говорю - смотри исходники. Есть Colorer, GRETA, RegExp++, наконец на codeproject было несколько реализаций.
     
  5. BreakPointMAN

    BreakPointMAN Гость

    о'кей, спасибо, будем разбираться... :lol:
     
Загрузка...
Статус темы:
Закрыта.

Поделиться этой страницей