Practicum on regular expressions, task 7.
Считываем строку - регулярное выражение в польской записи, букву x и число k. Храним стек сетов, в каждом сете - возможные остатки от деления числа букв х на k. Идём циклом по строке. Смотрим на текущий символ, если это буква или пустое слово, кидаем в стек новый сет (состоящий из 0 или, если тукущий символ х, 1), если операция, выполняем соответсвующую операцию. Для + нужно просто объединить два верхние в стеке сета (потому что остаток от деления числа букв х какого-то подслова данного языка на k будет совпадать с одним из остатков складываемых подслов). Для * нужно перезаполнить последний сет остатками, полученными при умножении тех остатков, что там есть, на любое натуральное число или 0 (т.е. достаточно рассмотреть произведения остатков на числа от 0 до k; в данной реализации я инициировала сет для результата сетом с нулём, а потом рассматривала произведения на числа от 1 до k). Для . нужно вместо двух верхних в стеке сетов записать их сумму по множествам (т.е. сет, состоящий из попарных сумм элементов двух сетов). Чтобы убедиться, что слово с количеством букв х кратным k, принадлежит данному языку, достаточно посмотреть, что 0 есть в единственном оставшемся сете (если сетов больше или меньше, входные данные некорректны).
Таким образом, если в строке n букв, в ней должно быть (n - 1) бинарных операций и сколько угодно (пусть это будет m) * . Для выполнения * требуется O(k * (размер посленего сета в стеке)) операций. Для выполнения + требуется O(суммарный размер послених двух сетов в стеке)) (считаем, что объединение сетов работает за линию). Для . требуется O(произведение размеров послених двух сетов в стеке)) операций. Для рассмотрения буквенного символа или пустого слова O(1). Размер любого сета в стеке не превосходит k (т.е. O(k^2) на + и столько же для * , O(k) для +), поэтому суммарная ассимптотика: O((m + n) * k^2), т.е. O(|s| * k^2), где s - считываемая строка.
Тестирование с помощью bash:
echo -e "ab+ b 6" | python main.py | grep -q "YES" && echo "Success"
echo -e "ab+c*. c 6" | python main.py | grep -q "YES" && echo "Success"
echo -e "ab+c*.++ c 6" | python main.py | grep -q "ERROR" && echo "Success"
echo -e "ab.aab.+.* b 179" | python main.py | grep -q "YES" && echo "Success"
echo -e "b*aa.. a 179" | python main.py | grep -q "NO" && echo "Success"
echo -e "ab.c.1+c*b.. a 3" | python main.py | grep -q "YES" && echo "Success"
echo -e "ab.1+*b. b 5" | python main.py | grep -q "YES" && echo "Success"
echo -e "aa.aa.*. a 179" | python main.py | grep -q "YES" && echo "Success"
echo -e "cb+b*.ab.c.ba.+*c.a. a 11" | python main.py | grep -q "YES" && echo "Success"
echo -e "c*ab.c+a+. b 17" | python main.py | grep -q "YES" && echo "Success"
echo -e "c*ab.cb.+ab.+. b 17" | python main.py | grep -q "NO" && echo "Success"
echo -e "c*ab.cb.+ab.+ b 17" | python main.py | grep -q "ERROR" && echo "Success"