Проверка соответствия строки шаблону

[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: воспользоваться регулярными выражениями не предлать, здесь немного другая ситуация...

[chur]

Наверно проще сразу распаковать шаблон в массив шаблонов без списков и проверять их по очереди, либо распаковывать по ходу пьесы. Второй вариант примерно такой.
Код на perl-е, постарался подробно прокомментировать. Что не понятно, пиши.

Код: Выделить всё

print find_templ('[a]bc{d|e}', 'abdgabcbce');

sub find_templ {
  my $templ = shift;  ### Получаем аргументы функции - шаблон
  my $string = shift; ### - строка
  my @templs = ($templ); # В массив @templs будем складывать шаблоны. Пока один.
  while (@templs) { # если в массиве есть шаблоны
    my $curtempl = pop @templs; # забераем крайний
    ##### устанавливаем начальные значения
    my $curpos = 0; # позиция текущего символа в шаблоне
    my $searchpos = -1; # очередная позиция первого символа шаблона в строке - неопределена
    my $firstenter = undef; # флаг: определена ли позиция первого символа - сброшен
    while ($curpos < length($curtempl)) { # пока не вышли за границу шаблона
      my $char = substr($curtempl, $curpos, 1); # получаем текущщий символ шаблона
      if (($char eq '[') || ($char eq '{')) { # если начало списка
         # раскрываем список (см. ниже). В функцию передаем подстроку шаблона с текущего символа до конца
        my @arr = unpack_templ(substr($curtempl, $curpos));
        $curtempl = substr($curtempl, 0, $curpos) . (pop @arr); # переопределяем текущий шаблон
        foreach (@arr) { push @templs, substr($curtempl, 0, $curpos) . $_; } # остальные кладем в массив шаблонов
        next; # переходим в начало цикла без смены текущей позиции
      }
      unless (defined $firstenter) { # если позиция первого символа неопределена
        $firstenter = index($string, $char, $searchpos+1); # ищем ее с места после последнего нахождения
        if ($firstenter == -1) { ## позиция не найдена, текущий шаблон не подходит
          last; # выходим и цикла по текущему шаблону, т.е. переходим к следующему шаблону
        }
        $searchpos = $firstenter; # очереданая позиция первого символа шаблона
        $curpos++; # инкрементируем текущую позицию и переходим в начало цикла
        next;
      }
      if (substr($string, $searchpos+$curpos, 1) eq $char) { # символ строки совпадает с текущим символом
        $curpos++; # будем проверять следующий
      }
      else { # символ строки не совпадает с текущим символом
        $curpos = 0; undef $firstenter; # надо искать следующую позицию первого символа
      }
    }
    if ($curpos == length($curtempl)) { ## успешно прошли весь шаблон
      return $searchpos; # возращаем позицию первого символа в строке
    }
  }
  return -1; # ничего не нашли
}


sub unpack_templ {
  my $templ = shift; # аргумент функции
  my $br = substr($templ, 0, 1); # открывающая скобка списка
  my $lastbr = $br eq '[' ? ']' : '}'; # закрывающая скобка
  my @brs; # массив внутренних скобок
  my @templs; # наш список
  my $curtempl = ''; # очередной элемент списка
  my $i; # позиция текущего символа
  for($i=1; $i<=length($templ); $i++) { # пробегаем по строке
    my $char = substr($templ, $i, 1); # очередной символ
    if (($char eq $lastbr) && (scalar(@brs) == 0)) { # если нашли закр. скобку, а внутренних не было или закрыты
      push @templs, $curtempl; # кладем элемент в список и выходим и цикла
      last;
    }
    if (($char eq '[') || ($char eq '{')) { # внутренняя открывающая скобка
      push @brs, $char; # отмечаем ее
    }
    elsif (($char eq ']') || ($char eq '}')) { # внутренняя закрывающая скобка
      my $checkbr = pop @brs; # возмем последнюю открывающую скобку
      if ($checkbr ne ($char eq ']' ? '[' : '{')) { # проверим, совпадают ли
        ;;;; #####  _не_ совпадают - ошибка шаблона, здесь должна быть обработка этой ошибки
      }
    }
    elsif (($char eq '|') && (scalar(@brs) == 0)) { # если разделитель списка, а внутренних скобок не было или закрыты
      push @templs, $curtempl;  # кладем элемент в список
      $curtempl = ''; next;  # обнуляем элемент, идем дальше
    }
    $curtempl .= $char; # добавляем символ к текущему элементу списка

  }
  if ($i > length($templ)) {
    ;;;; #####  _не_ нашли основную закрывающую скобу - ошибка шаблона, здесь должна быть обработка этой ошибки
  }
  foreach (@templs) { $_ .= substr($templ, $i+1); }  # ко всем элемента добавим часть строки, которую не прошли
  if ($br eq '[') {  # если лист необязательный
    push @templs, substr($templ, $i+1); # добавим часть строки, которую не прошли
  }
  return reverse @templs; # возвратим массив в обратном порядке

}

[BreakPointMAN]

Спасибо , будем разбираться!

ps: тема остается открытой, если у кого-нибудь есть какие-то мысли по этому поводу, буду очень признателен.

Интересует так же решение этой задачи с помощью автоматов. Через полный перебор и деревья, насколько я понял, работать оно будет долго... ((