Лекция 11. Строки

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

Знакомство со спецификой обработки строк мы начнем с изучения некоторых встроенных предикатов Турбо Пролога, предназначенных для работы со строками, которыми нам предстоит в дальнейшем воспользоваться.

Начнем со встроенного предиката str_len, который предназначен для определения длины строки, т.е. количества символов, входящих в строку. Он имеет два аргумента: первый — строка, второй — количество символов. Имеется три варианта использования данного предиката.

Первый, наиболее естественный вариант использования этого предиката, когда первый аргумент связан, а второй свободен. В этом случае во второй аргумент будет помещено количество символов в первом аргументе.

Второй, также ожидаемый для стандартного "прологовского" предиката вариант использования этого предиката, когда оба аргумента связаны. В этом случае предикат будет успешен, если длина первого аргумента будет совпадать со вторым аргументом, и неуспешен в противном случае.

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

Следующий стандартный предикат concat предназначен, вообще говоря, для соединения двух строк, или, как еще говорят, для их конкатенации. У него три аргумента, каждый строкового типа, по крайней мере, два из трех аргументов должны быть связаны. Итого получаем четыре возможных шаблона или четыре варианта использования этого предиката.

Первый вариант, когда связаны первые два аргумента. В этом случае третий аргумент будет означен строкой, полученной приписыванием второго аргумента к первому.

Второй вариант, когда связанными оказались первый и третий аргументы. В этой ситуации второй аргумент будет означен строкой, при приписывании которой к первому аргументу получится третий аргумент (если, конечно, такая строка существует). Если такой строки не может быть, предикат будет неуспешен.

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

И, наконец, четвертый вариант возникает, когда все три аргумента означены. Предикат будет успешен, если при соединении первого аргумента со вторым получится третий аргумент, и неуспешен — в противном случае.

Следующие три встроенных предиката предназначены для "разделки" строки на составляющие.

Предикат frontchar служит для разделения исходной строки на первый символ и "хвост", состоящий из оставшихся после удаления первого символа, символов строки. Это чем-то напоминает представление списка в виде головы и хвоста. Причем первый и третий аргументы данного предиката принадлежат строковому домену, а второй — символьному. У этого предиката пять вариантов использования.

Первый вариант, когда первый аргумент связан, а второй и третий — свободны. В этом случае второй аргумент будет означен первым символом строки, а в третий аргумент будут записаны все символы исходной строки, начиная со второго.

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

Третий вариант получается, когда первый и второй аргументы означены, а третий нет. В этой ситуации в третий аргумент будут переписаны все символы первого аргумента, начиная со второго, в случае, если первый символ первого аргумента совпадает со вторым аргументом. В противном случае предикат терпит неудачу.

Четвертый вариант похож на третий, но свободен второй аргумент, а связаны — первый и третий. В этом случае второй аргумент означивается первым символом первого аргумента, если оставшиеся символы первого аргумента образуют в точности третий аргумент. Иначе предикат будет неуспешен.

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

Предикат frontstr обобщает предикат frontchar в том смысле, что он тоже позволяет "откусить" от данной строки некоторое количество символов, но не обязательно один. Предикат имеет четыре параметра. В первом параметре указывается количество символов, которые копируются из второго параметра в третий, остатком второго параметра означивается четвертый аргумент. Как ни странно, этот предикат может использоваться только единственным описанным выше способом, а именно, первые два параметра у него входные, а третий и четвертый — выходные.

Если количество символов, указанных в первом параметре предиката frontstr, превышает длину строки из второго параметра, предикат терпит неудачу.

И, наконец, предикат fronttoken также дробит исходную строку, указанную в качестве первого параметра предиката, на две части. Во второй аргумент предиката попадает первый атом, входящий в строку, размещенную в первом аргументе, в третий — остаток входной строки, полученный после удаления из нее атома. Напомним, что атом — это или идентификатор, или беззнаковое число (целое или вещественное), или символ. У этого предиката существует пять вариантов использования.

Первый вариант, когда первый аргумент связан, а второй и третий — свободны. В этом случае второй аргумент будет означен первым атомом строки, находящейся в первом аргументе, а в третий аргумент будет записан остаток исходной строки.

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

Третий вариант получается, когда первый и второй аргументы означены, а третий нет. В этой ситуации в третий аргумент будут переписаны все символы первого аргумента, остающиеся после удаления первого атома, в случае, если первый атом первого аргумента совпадает со вторым аргументом. В противном случае предикат терпит неудачу.

Четвертый вариант подобен третьему, но свободен второй аргумент, а связаны первый и третий. В этом случае второй аргумент означивается первым атомом первого аргумента, если оставшиеся символы первого аргумента совпадают со строкой, находящейся в третьем аргументе. Иначе предикат будет неудачен.

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

Для полноты картины следует еще упомянуть о предикате isname, который истинен, если его строковый аргумент является идентификатором, и ложен в противном случае.

Пример. Теперь попробуем применить рассмотренные предикаты. Создадим предикат, который будет преобразовывать строку в список символов. Предикат будет иметь два аргумента. Первым аргументом будет данная строка, вторым — список, состоящий из символов исходной строки.

Решение, как всегда, будет рекурсивным. Базис: пустой строке будет соответствовать пустой список. Шаг: с помощью встроенного предиката frontchar разобьем строку на первый символ и остаток строки, остаток строки перепишем в список, после чего добавим первый символ исходной строки в этот список в качестве первого элемента.

Запишем эту идею:

str_list("",[]). /* пустой строке соответствует

пустой список */

str_list(S,[H|T]):–

frontchar(S,H,S1),

/* H — первый символ строки S,

S1 — остаток строки */

str_list(S1,T).

/* T — список, состоящий

из символов, входящих

в строку S1*/

Пример. Теперь попробуем немного модифицировать описанный предикат так, чтобы он преобразовывал строку не в список символов, а в список атомов.

Отличаться предыдущее решение будет заменой предиката frontchar на предикат fronttoken. Да еще надо не забыть в разделе описания предикатов заменить домен второго параметра со списка символов на список строк.

Запишем эту идею:

str_a_list("",[]). /* пустой строке по-прежнему

соответствует пустой список */

str_a_list(S,[H|T]):–

fronttoken(S,H,S1),

/* H — первый атом строки S,

S1 — остаток строки */

str_a_list(S1,T).

/* T — список, состоящий

из атомов, входящих

в строку S1*/

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

Пример. Разработаем предикат, который будет преобразовывать список символов в строку. Предикат будет иметь два аргумента. Первым аргументом будет список символов, вторым — строка, образованная из элементов списка.

Базис рекурсии: пустому списку соответствует пустая строка. Шаг: если исходный список не пуст, то нужно перевести в строку его хвост, после чего, используя стандартный предикат frontchar, приписывать к первому элементу списка строку, полученную из хвоста исходного списка.

Запишем эту идею:

list_str([],""). /* пустой строке соответствует

пустой список */

list_str([H|T],S):–

list_str(T,S1),

/* S1 — строка, образованная

элементами списка T */

frontchar(S,H,S1).

/* S — строка, полученная

дописыванием строки S1

к первому элементу списка H */

Пример. Создадим предикат, который по строке и символу подсчитает количество вхождений этого символа в данную строку. Предикат будет иметь три аргумента: первые два — входные (строка и символ), третий — выходной (количество вхождений второго аргумента в первый).

Решение, как обычно, будет рекурсивным. Рекурсия по строке, в которой ведется подсчет количества вхождений данного символа. Если строка пустая, то не важно, вхождения какого символа мы считаем, все равно ответом будет ноль. Это базис. Шагов рекурсии будет два в зависимости от того, будет ли первым символом строки символ, вхождения которого мы считаем, или нет. В первом случае нужно подсчитать, сколько раз искомый символ встречается в остатке строки, и увеличить полученное число на единицу. Во втором случае (когда первый символ строки отличен от символа, который мы считаем) увеличивать полученное число не нужно. При расщеплении строки на первый символ и хвост нужно воспользоваться уже знакомым нам предикатом frontchar.

char_count("",_,0). /* Любой символ не встречается

в пустой строке ни разу*/

char_count(S,C,N):–

frontchar(S,C,S1),!,

/* символ C оказался первым символом

строки S, в S1 — оставшиеся

символы строки S */

char_count(S1,C,N1),

/* N1 — количество вхождений

символа C в строку S1 */

N=N1+1.

/* N — количество вхождений

символа C в строку S получается

из количества вхождений символа C

в строку S1 добавлением единицы */

char_count(S,C,N):–

frontchar(S,_,S1),

/* первым символом строки S

оказался символ, отличный

от исходного символа C, в S1 —

оставшиеся символы строки S */

char_count(S1,C,N).

/* в этом случае количество

вхождений символа C в строку S

совпадает с количеством

вхождений символа C

в строку S1 */

Пример. Попробуем разработать предикат, который по символу и строке будет возвращать первую позицию вхождения символа в строку, если символ входит в строку, и ноль, если не входит. У предиката будет три параметра. Первые два — входные — символ и строка, третий — выходной — первая позиция вхождения первого параметра во второй параметр или ноль.

Не самая легкая задачка, но мы с ней справимся. Можно, конечно, записать в качестве базиса, что в пустой строке не встречаются никакие символы, но мы пойдем другим путем.

Вначале с помощью предиката frontchar разделим исходную строку на первый символ и остаток строки. Если первым символом строки окажется тот самый символ, позицию которого мы ищем, значит, больше ничего делать не нужно. Ответом будет единица. В этом случае нам даже неважно, какие символы оказались в хвосте строки, поскольку мы ищем первое вхождение данного символа в строку.

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

Давайте попробуем записать эти рассуждения.

str_pos(C,S,1):–

frontchar(S,C,_),!.

/* Искомый символ C оказался первым

символом данной строки S */

str_pos(C,S,N):–

frontchar(S,_,S1),

/* S1 — состоит из всех символов

строки S, кроме первого, который

отличается от искомого символа C */

str_pos(C,S1,N1),

/* N1 — это позиция, в которой

символ C встречается первый раз

в хвосте S1 или ноль*/

N1<>0,!, /* если позиция вхождения

символа C в строку S1 не равна

нулю, то есть если он встречается

в строке S1, /

N=N1+1. /* то, увеличив позицию его

вхождения на единицу, мы получим

позицию его вхождения в исходную

строку */

str_pos(_,_,0). /* искомый символ не входит в данную

строку */

Пример. Создадим предикат, который будет заменять в строке все вхождения одного символа на другой символ. У предиката будет четыре параметра. Первые три — входные (исходная строка; символ, вхождения которого нужно заменять; символ, которым нужно заменять первый символ); четвертым — выходным — параметром должен быть результат замены в первом параметре всех вхождений второго параметра на третий параметр.

Решение, как обычно, будет рекурсивным. Если строка пустая, значит, в ней нет символов, и, следовательно, заменять нечего. Результатом будет тоже пустая строка. Если же строка непустая, то мы должны разделить ее с помощью предиката frontchar на первый символ и строку, состоящую из остальных символов исходной строки.

Возможны два варианта. Либо первый символ исходной строки совпадает с тем, который нужно заменять, либо не совпадает.

В первом случае заменим все вхождения первого символа вторым символом в хвосте исходной строки, после чего, опять-таки с помощью предиката frontchar, приклеим полученную строку ко второму символу. В итоге в результирующей строке все вхождения первого символа будут заменены вторым символом.

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

str_replace("",_,_,""):–!. /* из пустой строки можно

получить только пустую

строку */

str_replace(S,C,C1,SO):–

frontchar(S,C,S1),!,

/* заменяемый символ C оказался

первым символом строки S,

S1 — остаток строки S */

str_replace(S1,C,C1,S2),

/* S2 — результат замены

в строке S1 всех вхождений

символа C на символ C1 */

frontchar(SO,C1,S2).

/* SO — результат склейки

символа C1 и строки S2 */

str_replace(S,C,C1,SO):–

frontchar(S,C2,S1),

/* разделяем исходную строку S

на первый символ C2

и строку S2, образованную

всеми символами строки S,

кроме первого */

str_replace(S1,C,C1,S2),

/* S2 — результат замены

в строке S1 всех вхождений

символа C на символ C1 */

frontchar(SO,C1,S2).

/* SO — результат соединения

символа C1 и строки S2 */

Если нам понадобится предикат, который будет заменять не все вхождения первого символа на второй, а только первое вхождение первого символа, то нужно просто из первого правила удалить вызов предиката str_replace(S1,C,C1,S2).

Пример. Разработаем предикат, который будет удалять часть строки. Предикат будет иметь четыре параметра. Первые три входные: первый — исходная строка, второй — позиция, начиная с которой нужно удалять символы, третий — количество удаляемых символов. Четвертым — выходным — параметром будет результат удаления из строки, указанной в первом параметре, символов, в количестве, указанном в третьем параметре, начиная с позиции, указанной во втором параметре.

Запишем решение этой задачи. Начнем с того, что при помощи стандартного предиката frontstr разобьем исходную строку на две подстроки. Во вторую попадут все символы, начиная с той позиции, с которой нужно удалять символы. В первую — начало исходной строки. Вторую подстроку еще раз разделим на две подстроки. В первую подстроку поместим те символы, которые нужно удалить. В этом месте можно будет воспользоваться анонимной переменной. Во вторую подстроку попадут оставшиеся символы остатка исходной строки. Чтобы получить ответ, нам остается только соединить первую подстроку исходной строки с последней подстрокой второй подстроки. Мы получим строку, состоящую в точности из тех символов, которые и должны были остаться в итоговой строке.

Давайте запишем эти немного путаные размышления в виде предложения на Прологе.

str_delete(S,I,C,SO):–

I1=I–1, /* I1 — количество символов,

которые должны остаться

в начале строки S */

frontstr(I1,S,S1,S2),

/* S1 — первые I1 символов

строки S, S2 — символы

строки S, с I —го

до последнего */

frontstr(C,S2,_,S3),

/* S3 — последние символы

строки S2 (или, что тоже

самое, последние символы

строки S */

concat(S1,S3,SO).

/* SO — строка, полученная

соединением строк S1 и S3 */

Пример. Не помешает иметь в нашем хозяйстве предикат, который будет копировать часть строки. Предикат будет иметь четыре параметра. Первые три входные: первый — исходная строка, второй — позиция, начиная с которой нужно копировать символы, третий — количество копируемых символов. Четвертым — выходным — параметром будет результат копирования символов из строки, указанной в первом параметре, в количестве, указанном в третьем параметре, начиная с позиции, указанной во втором параметре.

Для решения этой задачи опять воспользуемся предикатом frontstr. Сначала получим хвост нашей строки, начиная с той позиции, c которой нужно копировать символы. Если после этого взять столько первых символов новой строки, сколько их нужно копировать, получим в точности ту подстроку исходной строки, которую требуется получить.

Зафиксируем наши рассуждения.

str_copy(S,I,C,SO):–

I1=I–1, /* I1 — это количество

символов, расположенных

в начале строки S, которые

не нужно копировать */

frontstr(I1,S,_,S1),

/* S1 — строка, состоящая

из всех символов строки S,

с I-го и до последнего */

frontstr(C,S1,SO,_).

/* SO — первые C символов

строки S1 */

Пример. Мы реализовали почти все операции, которые есть в большинстве стандартных алгоритмических языков типа Паскаля. Недостает, наверное, только предиката, который позволит нам вставить одну строку внутрь другой строки. Предикат будет иметь четыре параметра. Первые три входные: первый — вставляемая строка; второй — строка, в которую нужно вставить первый аргумент; третий — позиция, начиная с которой нужно вставить первый параметр во второй. Четвертым — выходным — параметром будет результат вставки строки, указанной в первом параметре, в строку, указанную во втором параметре, начиная с позиции, указанной в третьем параметре.

Для реализации этого предиката разделим, используя предикат frontstr, исходную строку на две подстроки. Во вторую поместим все символы, начиная с позиции, в которую должна быть вставлена вторая строка, в первую — оставшееся начало исходной строки. После этого припишем, используя конкатенацию, к полученной строке ту строку, которую нужно было вставить. Для получения окончательного результата нам остается только дописать вторую подстроку исходной строки.

Запишем:

str_insert(S,S1,I,SO):–

I1=I–1, /* I1 — это количество

символов, расположенных

в начале строки S, после

которых нужно вставить новые

символы */

frontstr(I1,S1,S1_1,S1_2),

/* S1_1 — первые I1 символов

строки S1, S1_2 — остаток

строки S1, с I —го и до

последнего */

concat(S1_1,S,S2),

/* S2 — строка, полученная

объединением строк S1_1

и S */

concat(S2,S1_2,SO).

/* SO — строка, полученная

слиянием строк S2 и S1_2 */

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

Для того чтобы реализовать этот предикат, нам придется разработать вспомогательный предикат, который будет означивать второй аргумент единицей (если его первый аргумент является цифрой) и нулем (в противном случае). Основной предикат будет использовать рекурсию по длине строки. Базисом будет очевидный факт, говорящий, что в пустой строке цифр нет. Непустую строку с помощью предиката frontchar разделим на первый символ и хвост. Подсчитаем количество цифр в хвосте, после чего к полученному числу добавим единицу, если первый символ — цифра, и ноль, если первый символ — не цифра.

Запишем оба предиката, вспомогательный и основной:

dig(C,1):–

‘0’<=C,C<=’9’,!. /* C — цифра*/

dig(_,0).

count_digit("",0):–!. /* В пустой строке цифр нет */

count_digit(S,N):–

frontchar(S,C,S2),

/* C — первый символ строки S,

S2 — хвост строки S */

dig(C,M), /* M равен единице, если C —

цифра, и нулю — иначе */

count_digit(S2,N2),

/* N2 — количество цифр

в строке S2*/

N=N2+M. /* Количество цифр во всей

строке больше на единицу,

чем количество цифр

в хвосте, если первый символ

строки — цифра, и равно

количеству цифр в хвосте —

иначе */

Самостоятельные задания

Создайте предикат, который будет находить последнюю позицию вхождения символа в строку.

Создайте предикат, который подсчитает общее количество латинских букв в списке символов.

Создайте предикат, который будет подсчитывать количество русских гласных букв в строке.

Создайте предикат, находящий в исходной строке слово, в котором наибольшее количество русских гласных букв.

Создайте предикат, который будет удалять из данной строки все вхождения заданного символа.

Создайте предикат, удаляющий из данной строки все повторные вхождения символов.

Создайте предикат, который продублирует вхождение каждого символа в строку.

Создайте предикат, "переворачивающий" строку (меняющий в строке порядок символов на обратный).

Создайте предикат, проверяющий, является ли данная строка палиндромом.

Создайте предикат, составляющий список символов, которые входят одновременно в обе данных строки.

Создайте предикат, находящий в исходной строке слово максимальной (минимальной) длины.

Создайте предикат, преобразующий строку в список слов, состоящих из четного количества символов.

Создайте предикат, преобразующий строку в список слов, которые упорядочены по длине.

Создайте предикат, преобразующий строку в список слов, которые упорядочены в лексикографическом порядке.

Создайте предикат, преобразующий исходную строку в строку, состоящую из первых букв слов первоначальной строки.

Создайте предикат, преобразующий исходную строку в строку, состоящую из последних букв слов первоначальной строки.

Создайте предикат, проверяющий правильность расстановки скобок в исходной строке.

Создайте предикат, меняющий местами первую и последнюю буквы в каждом слове исходной строки.