42
Заочная школа программирования
Урок 11: обработка текстов на ЭВМ
Дело состоит только в том, чтобы переменить заданный титул да переменить кое-де главы из первого лица в третье.
Н. В. Гоголь. «Шинель»
Где применяется обработка текстов?
Текстовая обработка широко распространяется сегодня в различных областях применения ЭВМ. Например, большинство задач, возникших при автоматизированной подготовке к печати книг, журналов, газет и других изданий, связано с обработкой текстов. К обработке текстовой информации можновести заготовку, обточить и отшилфовать работу поверхность, подрезать оба торца, просверить три ответствия, в одном из них нарезать резьбу и нанести запитное покрытие. Придумайте для технологической инструкции способ кодировки и запишите ее в виде текста.
Задание 11.2. Для изготовления детали необходимого отитамповать заготовку, обточить и отшилфовать работу поверхность, подрезать оба торца, просверить три ответствия, в одном из них нарезать резьбу и нанести запитное покрытие. Придумайте для технологической инструкции способ кодировки и запишите ее в виде текста.
Задание 11.3. Юные биологически придуманы такую систему для записи своих наблюдений за поведением животных в естественных условиях: буквой С обозначает сон животного, О — охота, К — кормление, В — водопой, Д — драка, И — цера, У — уход за детьмиами. Опишите словами поведение животного, представленное таким текстом:
‘ОВОКСВДКИС’—>ЗВЕРЕК;
Как вы думаете, за каким животным habлодали ребята: хицное оно или травядное, молодое или старое?
Простые формы обработки текстов
Одна из простейших форм обработки текстов — подсчет количества определенных букв или сочетаний букв (задания 4a и 46 Олимпiadы по программированию — «Квант», 1980, № 3). При подготовке печатных изданий и документов такая задача встречается сравнительно редко, а вот при решении задачи из других областей — очень часто. Например, таким способом можно определить процентное содержаниевали в белке, подсчитать количество сверленей при обработке детали или
43
число случаев, когда животное засыпало сразу после edы.
Описем функцию СЧЕТ1 с двумя параметрами — БУКВА и ТЕКСТ, которая будет подсчитывать, сколько раз заданная буква встречает в тексте:
ПРОЦ СЧЕТ1 БУКВА ТЕКСТ = > СЧЕТЧИК;
0 —> СЧЕТЧИК; 1 —> НОМЕР;
ПОКА НОМЕР = < (≠ ТЕКСТ) ::
ЕСЛИ ТЕКСТ[НОМЕР] = БУКВА
ТО СЧЕТЧИК + 1 —> СЧЕТЧИК
ВСЕ;
НОМЕР + 1 —> НОМЕР;
ВСЕ
КНЦ;
Проверьте, что значение функции СЧЕТ1(‘К’, ПОЕЗД) будет равно 5.
Задание 11.4. Описать функцию СЧЕТ2(ОТРЕЗОК, ТЕКСТ), подсчитывающую количество заданных отрезков последовательностей букв в тексте. Например, значение функции СЧЕТ2(‘КУ’,‘КУКАРЕКУ’) равно 2.
Часто приходится решать еще и такую задачу: построить сводную таблицу количества повторений каждой буквы, встречаются в тексте. Такую таблицу удобно представить как множество, состоящее из кортежей вида <БУКВА, ЧИСЛО ПОВТОРЕНИЙ>.
Например, для текста «КУКАРЕКУ» таблица могла бы иметь такой вид: <<‘К’,3>, <‘У’,2>, <‘A’,1>, <‘P’,1>, <‘E’,1>>.
Понятоно, что для построения таблицы нужно просмотреть весь текст и для каждой его буквы проверить, найдется ли в составлении таблице кортеж, первым элементом которого является эта буква. Если такой кортеж есть, то нужно прибавить единицу к его второму элементу, а если нет — нужно добавить к таблице новый кортеж, первый элемент которого — это встретившаяся буква, а второй — единица. Соответствующая процедура может выглядеть так:
ПРОЦ ТАБЛИЦА ТЕКСТ = > МНОЖ;
<**> —> МНОЖ; 1 —> НОМЕР;
ПОКА НОМЕР = < (≠ ТЕКСТ) ::
ТЕКСТ[НОМЕР] —> БУКВА;
0 —> КОНТРОЛь;
ДЛЯ КОРТЕЖ ИЗ МНОЖ::
ЕСЛИ КОРТЕЖ[1] = БУКВА TO
КОРТЕЖ[2] + 1 —> КОРТЕЖ[2];
1 —> КОНТРОЛь
ВСЕ
ВСЕ;
ЕСЛИ КОНТРОЛь = 0 TO
МНОЖ + <БУКВА,1> —> МНОЖ
ВСЕ
ВСЕ
КНЦ;
Обратите внимание на имя КОНТРОЛь! Его пришлось ввести для того, чтобы проверить, был ли среди элементов множества МНОЖ нужный кортеж. Отпечать такую таблицу в удобном виде можно, например, так:
ДЛЯ КОРТЕЖ ИЗ МНОЖ::
ПЕЧАТЬ(‘БУКВА’,КОРТЕЖ[1],
‘ВСТРЕЧАЕТСЯ’,КОРТЕЖ[2]‘РАЗ’)
ВСЕ;
Редактирование
Пожалуйста, самые интересные текстовые задания возникают при обработке «настоящих» текстов: печатных изображений, документов, программ на различных языках программирования и т. д. Применение ЭВМ позволяет легко и быстро редактировать такие тексты, внесить в них любые исправления и изменения, печатать в любом формате, а иногда и любым шрифтом (в одной из статей мы рассакем подробнее о подготовке печатных изображений на ЭВМ).
Типичный пример задания редактирования — задача 4в Олимпиды: «Всюду в тексте с именем ПРИКАЗ заменить слова ‘КАПИАН ИВАНОВ’ на ‘МАЙОР ИВАНОВ’». Большинство участников Олимпиды неполно справились с этой задачей, но почти ничего не обработил внимания на одну тонкость: отыскивая места, где нужно произвести замену, надо было искать отрезок ‘КАПИАН ИВАНОВ’ (с пробелом после фамилии!), а не просто ‘КАПИАН ИВАНОВ’, иначе, например, капитан Ивановский, если его фамилия встречается в приказе, тоже оказывается майором.
Задча замены слов в тексте с учетом различных грамматических форм (в нашем примере слова «КАПИАН ИВАНОВ» могут стать в разных подежах) программируется значительно сложнее. Впрочем, гоголевский Акакий Акакиевич с этой задачей, как известно, тоже не справился. Такого рода редактирование сложных текстов удобно проводить в режиме диалога, когда человекоператор просматривает текст и отыскивает места, где необходимо выполнить текстовые замены (иногда такой поиск может проходить с «подсказкой» со стороны машины), а сами замены выполняет ЭВМ.
Для работы в таком режиме удобно заранее описать процедуры для выполнения самых распространенных операций (попск нужного отрезка текста, замена, исключание, вставка, вывод на терминал и т. д.),
44
а затем использовать эти процесуры в качестве директив в ходе диалога.
Задание 11.5. Описать процессура ЗАМЕНА(ТЕКСТ,СТАР,НОВ), которая всоду в тексте с именем ТЕКСТ заменит определенные соотдачи символов заданным отрезком текста. Второй параметр этой процессуры — заменяемый отрезок текста, а третьий параметр — заменяющий отрезок.
Указание и е. Если длинный старого и нового отрезков текста не совпадают, для правильной замены нужно использовать конкатенацию строк. Например, если слово «КРОНДИЛ», расположенное в тексте с именем БАРМАЛЕЙ, начиная со 128-й позиции, необходимо исправить на «КРОКODИЛ», то это можно выполнить так:
БАРМАЛЕЙ[1:130] + ‘КО’
- БАРМАЛЕЙ[132:(≠БАРМАЛЕЙ)]
-> БАРМАЛЕЙ;
Если вместо этого попробовать использовать простое присваивание, то исправить ошибку не удался: после присваивания ‘КО’-> БАРМАЛЕЙ[131:131];
получится «КРОКДИЛ».
Процедура ЗАМЕНА позволяет исправлять ошибки и вносить изменения в текст. Но использовать ее нужно осторожно, чтобы не возникало новых ошибок. Расмотрим простой пример. Пусть в тексте с именем учёбник нужно было напечатать формату:
SIN (X) + COS (X) = S;
Просматривая этот текст на экране терминала, оператор заметил ошибку. Строка выглядела так:
SIN (S) + COS (X) = S;
Оператор попробал ее исправить и набрал такую директиву:
ЗАМЕНА(учёбник,‘S’,‘X’);
Вторичное просматривая это место, он с удивлением обнаружил, что форматula присвела совсем уже страный вид:
XIN (X) + COS (X) = X.
Причина ясна: все буквы «S» в учёбнике (и не только в этой строке!) заменились на «X».
Задание 11.6. Записать правильную директиву ЗАМЕНА для исправления первого начального варианта.
та этой строки (возможным воздействием на другие части текста претензей).
Если целая книга или большая программа записана в память в виде одного длинного текста, то редактировать такой текст не так уж удобно. При каждом исправлении нужно обозначить проверять, что заменяемый или выбрасываемый участок текста не повторяется ни в каком другом месте. Конецно, такую проверку можно поручить машине (использование, приведению выше процедуры СЧЕТ2), но обычно бывают удобнее просто указать точное место исправления. Для этого большой текст разбиают на короткие участки по 50—60 символов — строки, а из строк составляют кортеж. Каждый строка целиком видна на экране терминала, поэтому подобрать нужное исправление очень легко: не нужно заботиться о сохранности остального текста. В директиве ЗАМЕНА при таком способе представления текста появляется еще один параметр — номер строки, в которой нужно произвести замену.
- Задание 11.7. Составить процессура для проверки правильности расстановки скобок в формате, представленной текстом с именем ФОРМ. Скобки считаются расставленные правилами правилано, если между открывающими и закрывающими скобками можно установить такое взаимное однозначное соответствие, при котором каждой открывающей скобке соответствует стоящая после нее закрывающая. ()()()() — пример правильной расстановки скобок. А вот примеры неправильной расстановки: )(),()(),()(),()(),()().
Указание и е. Для решения этой задачи удобно использовать простой пример, называемый алгоритм Рутисхаузера. Присвоим имени СЧЕТЧИК значение 0 и будем просматривать текст ФОРМ слева направо. Обнаружив закрывающий скобку, будем вычитать единицу из значения имени СЧЕТЧИК, а обнаружив открывающий скобку, прибавлять единицу. Если к окончанию просмотрения имени СЧЕТЧИК положительно, значит, закрывающий скобок не хватает. Если во время просмотрения этого имени хотя бы один раз стало отрицательным, значит, скобки расставлены неправильно. Если во время просмотрения не становилось отрицательным и к окончанию равно нулю, значит, все в порядке (доказите!).
Г. Звеницгородский