Строковый автомат
Строковый автомат «Гомер-2015» принимает на вход строку символов и возвращает строку как результат. У автомата есть набор инструкций — список правил замены. Каждое правило состоит из подстроки, которую нужно заменить, и строки, на которую эта подстрока заменяется. Автомат выполняет следующие операции: ищет первое правило, для которого текущая строка содержит соответствующую подстроку, заменяет первое вхождение этой подстроки на строку-замену и повторяет процесс с начала. Когда ни одна подстрока не содержится в текущей строке, автомат возвращает эту строку как результат. Список замен автомата называется программой. Количество правил замен называется размером программы. Количество произведённых замен на конкретных входных данных называется количеством операций.
Рассмотрим пример, когда на вход автомату подаётся строка abcbca, а его программа размера 2 выглядит так: 1) bac → c и 2) bc → cba. Порядок работы автомата следующий:
Текущая строка: abcbca.
Поскольку abcbca не содержит подстроку bac из первого правила, автомат переходит ко второму правилу.
Поскольку abcbca содержит подстроку bc из второго правила, автомат заменяет первое вхождение этой подстроки на cba и возвращается к началу.
Текущая строка: acbabca.
Поскольку acbabca не содержит подстроку bac из первого правила, автомат переходит ко второму правилу.
Поскольку acbabca содержит подстроку bc из второго правила, автомат заменяет первое (и единственное) вхождение этой подстроки на cba и возвращается к началу.
Текущая строка: acbacbaa.
Поскольку acbacbaa содержит подстроку bac из первого правила, автомат заменяет первое (и единственное) вхождение этой подстроки на c и возвращается к началу.
Текущая строка: accbaa.
Поскольку accbaa не содержит подстроку bac из первого правила, автомат переходит ко второму правилу.
Поскольку accbaa не содержит подстроку bc из второго правила, автомат пытается перейти к следующему правилу.
Поскольку правила закончились, автомат возвращает строку accbaa как результат.
Таким образом, из строки abcbca автомат сформировал accbaa. Количество операций в данном случае равно 3: заменили bc на cba, затем ещё раз bc на cba, далее bac на c.
Задание
Напишите набор программ для строкового автомата, решающих различные задачи преобразования строк (см. ниже). Для каждой подзадачи вы сдаёте только текст программы строкового автомата. За каждую подзадачу вы получаете либо полный балл, если программа прошла все её тесты, либо ноль, если хотя бы один тест не пройден.
Ограничения
В каждом правиле длина как подстроки поиска, так и строки замены не должна превышать 10 символов (но в сумме они могут быть длиннее); при этом строка замены может быть пустой, а подстрока поиска — нет. Автомат может использовать такие символы: цифры, строчные и заглавные латинские буквы (причём строчные и заглавные буквы считаются разными символами), а также символ «плюс» (+). Вы можете использовать все эти символы как в подстроках поиска, так и в строках замены во всех подзадачах. Размер одной программы не может превышать 100. Для любых входных данных количество операций не должно превышать 1000. Определение размера программы и количества операций см. выше.
Проверка с помощью эмулятора
В электронном варианте условий приведена ссылка для загрузки программы, эмулирующей строковый автомат и предоставляющей вспомогательную информацию о ходе выполнения программы. Чтобы использовать эмулятор, разместите его в отдельном каталоге, создайте в этом каталоге файл program.txt с текстом программы, а также файл input.txt, в который введите входную строку для вашей программы (можно добавить или не добавлять перенос строки в конце файла), и запустите программу-эмулятор. Она создаст такие файлы:
!output.txt: выходная строка автомата (если программа или входные данные некорректны или количество операций превышает ограничение, файл не будет создан / будет удалён).
!debug.txt: в каждой строке этого файла указано состояние строки после соответствующего количества операций (если программа или входные данные некорректны, этот файл не будет создан / будет удалён; если количество операций превышает ограничение, файл будет содержать состояние строки только до момента, когда было превышено ограничение).
!info.txt: в первой строке этого файла указано, являются ли корректными программа и входные данные (а если они некорректны, то почему); если программа и входные данные корректны, во второй строке указано количество операций выполненной программы; в третьей строке указано размер программы; в четвёртой строке указана длина самой длинной строки поиска и длина самой длинной строки замены.
Дополнительно эмулятору можно передавать до четырёх параметров командной строки: ограничение на количество операций, на размер программы, на длину строки поиска и на длину строки замены. Например, если запустить эмулятор командой auto.exe 2000 100 15, ограничение на количество операций будет установлено 2000 (вместо 1000); ограничение на размер программы будет стандартным (100); ограничение на длину строки поиска — 15; неуказанное в параметрах командной строки ограничение на длину строки замены также останется стандартным (10).
Подзадача 1 (5 баллов)
На входе — строка из цифр длиной от 1 до 20 включительно. На выходе — строка из тех же цифр в порядке от наименьших к наибольшим. Пример: 9101→0119.