Необходимо обработать символ *, который означает, что предыдущий символ встречается 0 или более раз.
Дается какая-то строка, например, s="a*b*a". Это означает, что эта строка эквивалентна: a, aa, ba, aba, aaa, bbb, и тд. С парсингом строки s в целом вопросов нет, я разбиваю ее на массив символов и массивом чисел, который характеризует символы. В данном случае:
['a', 'b', 'a'];
[1, 1, 0];
То есть первые 'a' и 'b' являются необычными символами, последний 'a' является обычным.
И теперь вопрос, как проверить на равенство эту строку с другими?
Самая большая проблема возникает, когда для указанного выше s, поступает на проверку строка: "a". Как алгоритм должен понимать, что эта 'a' подходит только к обычному символу 'a' из s. Если я последовательно начну проверять и сперва сверю с необычным 'a', то потом для обычного 'a' символов во входной строке уже не останется и алгоритм решит, что строка неправильная.
Lynn «Кофеман», нет) это просто домашняя задачка из универа, над которой уже несколько дней ломаю голову.
нужно реализовать лишь несколько простых возможностей регулярок
Lynn «Кофеман», я понимаю, как этот метод подойдет для символа "?", который означает 0 или 1 раз встречается предыдущий символ. В котором у нас ограниченное число комбинаций.
А как этот метод применить для "*"? Отойти на шаг назад, значит увеличить количество повторений данного символа на 1, но ведь мы не знаем до какого момента нужно увеличивать, чтоб снова отойти на шаг назад и менять предыдущий символ
n1ksON, Ну так можно отходить на любое количество шагов назад.
Да, в случае неудачного выражения и строки можно получить экспоненциальное время выполнения.
Ну или можно стоить детерминированный конечный автомат, но это уже более другая задача.
Без теории тут никак.
Тут 2 варианта: или стройте конечный недетерменированный автомат (с эпсилон переходами), который соответствует этому регулярному выражению и дальше применяйте стандартный алгоритм проверки. что автомат принимает заданную строку. Или второй вариант: пишите динамическое программирование "соответствует ли вот этот префикс заданной строки вот этому префиксу регулярного выражения".
Конечный автомат будет и побыстрее работать и памяти меньше требовать.
upd: ну и, конечно, тут полным перебором рекурсивно можно сделать. Но это будет гораздо медленнее любого из указанных выше методов.
n1ksON, Ну тогда пишите функцию, которая принимает, какую оставшуюся часть строки надо собрать из какой оставшейся части регулярного выражения (уже распарсенного в строку + флаги, что там есть звездочки).
В функции есть 3 перехода - откусить символ от регулярки, откусить символ от строки и откусить оба символа. Они возможны в засисимости от того, равны ли символы и есть ли звездочка в регулярке.
Простой
Простой
