Задача. Удаление пробелов

В строке текста записаны слова, разделенные пробелами в произвольном количестве. Сжатие текста состоит в том, что между словами оставляется по одному пробелу, а после последнего слова пробелы удаляются (пробелы перед первым словом сохраняются). Сжатый текст записать в другой файл. Если строка содержит только пробелы, то все они копируются.

Вход. Строка неограниченной длины.

Выход. Строка неограниченной длины.

Анализ и решение задачи. На этой простой задаче мы познакомимся с тем, как в обработке текстов применяются конечные автоматы. По условию задачи:

· пробелы перед первым словом копируются в другой текст;

· после каждого слова, кроме последнего, из серии пробелов выводится только один;

· после последнего слова они вообще не выводятся.

Как видим, реакция на пробел зависит от того, в какой части входной строки находится прочитанный символ. Ясно, что этими частями строки являются, как минимум, часть перед первым словом и часть после него.

Кроме того, если после слова появился пробел, его нельзя сразу копировать — неизвестно, было ли это слово последним. Будем выводить пробел, идущий после слова, только при появлении следующего слова. Значит, нужно по-разному реагировать на очередную литеру, когда слово продолжается, и когда литера появляется после пробела и слово не первое. В первой ситуации выводится прочитанная литера, во второй — пробел и литера.

Итак, у нас есть три различные части строки: "перед первым словом", "после литеры слова", "после пробела". Назовем их состояниями. По текущему состоянию можно определить, в какое состояние переходит текст после чтения очередного входного символа. Например, из состояния "перед первым словом" литера переводит в состояние "после литеры слова", а пробел оставляет в том же состоянии. Изменение состояния в зависимости от текущего состояния и прочитанного символа называется переходом.

Изобразим переходы между состояниями. Обозначим состояния, указанные выше, цифрами соответственно 0, 1, 2. Добавим еще состояние "конец текста", возникающее при окончании входной строки, и обозначим его цифрой 3. В этом состоянии работа завершается.

Переходы изобразим на диаграмме переходов (Рис.1). Круги обозначают состояния, а стрелки, отмеченные символами, — переходы. Переход по стрелке происходит тогда и только тогда, когда текущим является состояние в начале стрелки и на входе прочитан отмечающий ее символ. Символы, отличные от пробела, обозначим буквой а. Окончание текста обозначим "символом" eof. При некоторых переходах в выходной текст выводятся символы — укажем их справа от косой черты "/"; если при переходе символы не выводятся,"/" отсутствует.

Рис. 1. Диаграмма состояний при сжатии пробелов

Неформально, конечная система состояний и правил переходов между ними под воздействием входных символов называется конечным автоматом. Автомат функционирует, читая входные символы и изменяя свои состояния. С помощью состояния автомата, можно, например, представить множество цепочек входных символов, приводящих в это состояние. Тогда своими состояниями автомат распознает множества цепочек.

Другой способ изобразить конечный автомат – это задать переходы в таблице.

	Символ
Состояние	a	‘ ‘ - пробел	eof
0	1/ a	0/ ‘ ‘	3
1	1/ a	2	3
2	1/ ‘ ‘, a	2	3

В состоянии 3 переходов нет, поэтому в таблице его нет. По диаграмме или таблице переходов легко написать программу чтения и обработки символов текста. В основе программы лежит цикл, в котором очередной символ считывается и обрабатывается с учетом текущего состояния. Представим состояние значением целой переменной state, очередной символ ‑ переменной с типа char. Начальным состоянием (перед обработкой входа) является 0.Внутри основного цикла программы, по сути, реализована таблица переходов. Текущее состояние определяется с помощью switch state.... В вариантных операторах указано, как обрабатывается символ и изменяется состояние. Состояние 3 в программе не представлено – переходу в него соответствует прерывание цикла и завершение работы.

#include <cstdlib>

#include <iostream>

using namespace std;

int main(int argc, char *argv[])

{

enum Tstate {before, after_word, after_space};

char c;

Tstate state = before;

while (cin.get(c))

{//

switch (state)

{

case before:

cout << c;

if (c!= ' ') state = after_word;

break;

case after_word:

if (c!= ' ')

cout << c;

else

state = after_space;

break;

case after_space:

if (c!= ' ')

{

cout << ' ' << c;

state = after_word;

}

}

}

system("PAUSE");

return EXIT_SUCCESS;

}

Упражнение. У Васи Хвостикова очень старая клавиатура и клавиши на ней «западают», то есть вдруг какой-нибудь символ при вводе многократно повторяется. Напишите программу, которая из текста удалит все подряд идущие повторяющиеся символы, оставив только один.

Вход. Строка неограниченной длины.

Выход. Строка неограниченной длины.

Дата добавления: 2015-07-11