Одесский национальный университет им. И.И.Мечникова
Министерство науки и образования Украины
Лабораторная работа №3
по курсу: «Специализированые
языки программирования»
выполнил студент III курса
гр. МОКС, Таран Евгений Юрьевич
Одесса 2012
Вариант №
Цель работы: приобретение навыков работы со строками в
Пролог-программах.
Постановка задач
1. Написать программу, которая по введенной строке определяет
a. Количество цифр в строке.
b. Количество слов в строке. Слова отделяются одним или
несколькими символами "пробел", "," , "." , ";", "-",”!”,”?”.
c. Удаляет лишние пробелы между словами.
d. меняет все вхождения слова "пес" на слово "кот"
e. Определяет количество чисел в строке
f. Находит в строке самое короткое слово.
g. Удаляет из строки гласные буквы.
Интерфейс с пользователем должен быть оформлен в виде
простого
Вначале приведу код всей программы, после чего в отдельности будет разобрана постановка, решение и тестирование всей программы.
Код программы:
goal:-write('Введите строку\n'),read(X),write('Выберите пункт:\n'),
write('a. - Количество цифр в строкеъ\nb. - Количество слов в строке\nc. - Удаляет лишние пробелы\nd. - меняет все вхождение слова пес на кот
e. - Определяет количество чисел в строке.\nf. - Находит в строке самое короткое слово.\ng. - Удаляет из строки гласные буквы\n'),
read(A),start(X,A).
start(X,A):-char_code(A,97),totalnumber(X,N),write(N).
start(X,A):-char_code(A,98),totalword(X,N),write(N).
start(X,A):-char_code(A,99),onespace(X,R),write(R).
start(X,A):-char_code(A,100),pesvkot(X,R),write(R).
start(X,A):-char_code(A,101),numinstring(X,N),write(N).
start(X,A):-char_code(A,102),minword(X,R),write(R).
start(X,A):-char_code(A,103),deletevovel(X,R),write(R).
frontchar(S, C, S1):-string_concat(C, S1, S), string_length(C, 1),!.
totalnumber(S,N):-frontchar(S,C,S1),tn(S1,C,N).
tn(S,C,1):-string_length(S,0),char_code(C,CN),CN > 47, CN < 58.
tn(S,_,0):-string_length(S,0).
tn(S,C,N):-char_code(C,CN),CN > 47, CN < 58,frontchar(S, C1, S1), tn(S1,C1,N1),N is N1+1.
tn(S,_,N):-frontchar(S, C, S1), tn(S1,C,N).
isdel(C):-char_code(C,32).
isdel(C):-char_code(C,44).
isdel(C):-char_code(C,46).
isdel(C):-char_code(C,59).
isdel(C):-char_code(C,45).
isdel(C):-char_code(C,33).
isdel(C):-char_code(C,63).
totalword(S,N):-frontchar(S,C,S1),isdel(C),tw(S1,C,N,0).
totalword(S,N):-frontchar(S,C,S1),tw(S1,C,N,1).
tw(S,_,1,STATE):-string_length(S,0),STATE =:= 1.
tw(S,_,0,STATE):-string_length(S,0),STATE =:= 0.
tw(S,C,N,STATE):-STATE =:= 1, isdel(C), frontchar(S,C1,S1), tw(S1,C1,N1,0), N is N1 + 1.
tw(S,C,N,STATE):-STATE =:= 0, isdel(C), frontchar(S,C1,S1), tw(S1,C1,N,0).
tw(S,_,N,_):-frontchar(S,C1,S1), tw(S1,C1,N,1).
isspace(C):-char_code(C,32).
onespace(S,R):-os(S,R,0).
os(S,'',1):-string_length(S,1),isspace(S).
os(S,S,_):-string_length(S,1).
os(S,R,0):-frontchar(S,C,S1),isspace(C),os(S1,R1,1),string_concat(C,R1,R).
os(S,R,1):-frontchar(S,C,S1),isspace(C),os(S1,R,1).
os(S,R,_):-frontchar(S,C,S1),os(S1,R1,0),string_concat(C,R1,R).
%п - 1087, е - 1077, с - 1089
pesvkot(S,R):-pvk(S,R,0,'','').
pvk(S,RESSTR1,2,_,BeforeState):-string_length(S,1),char_code(S,1089),string_concat(BeforeState,'кот',RESSTR1),!.
pvk(S,RESSTR1,_,RESSTR,_):-string_length(S,1),string_concat(RESSTR,S,RESSTR1),!.
pvk(S,R1,0,RESSTR,BeforeState):-frontchar(S,C,S1),char_code(C,1087),string_concat(RESSTR,C,RESSTR1),pvk(S1,R1,1,RESSTR1,BeforeState),!.
pvk(S,R1,1,RESSTR,BeforeState):-frontchar(S,C,S1),char_code(C,1077),string_concat(RESSTR,C,RESSTR1),pvk(S1,R1,2,RESSTR1,BeforeState),!.
pvk(S,R1,2,_,BeforeState):-frontchar(S,C,S1),char_code(C,1089),string_concat(BeforeState,'кот',RESSTR1),pvk(S1,R1,0,RESSTR1,RESSTR1),!.
pvk(S,R1,_,RESSTR,_):-frontchar(S,C,S1),string_concat(RESSTR,C,RESSTR1),pvk(S1,R1,0,RESSTR1,RESSTR1).
isnum(C):-char_code(C,CN),CN > 47, CN < 58.
iszero(C):-char_code(C,48).
numinstring(S,N):-nis(S,N,1).
nis(S,1,2):-string_length(S,0).
nis(S,1,3):-string_length(S,0).
nis(S,0,_):-string_length(S,0).
nis(S,N,1):-frontchar(S,C,S1),iszero(C),nis(S1,N,3),!.
nis(S,N,1):-frontchar(S,C,S1),isnum(C),nis(S1,N,2),!.
nis(S,N,2):-frontchar(S,C,S1),isnum(C),nis(S1,N,2 ),!.
nis(S,N,2):-frontchar(S,C,S1),isspace(C),nis(S1,N1,1),N is N1 + 1,!.
nis(S,N,3):-frontchar(S,C,S1),isspace(C),nis(S1,N1,1),N is N1 + 1,!.
nis(S,N,_):-frontchar(S,C,S1),isspace(C),nis(S1,N,1),!.
nis(S,N,_):-frontchar(S,_,S1),nis(S1,N,0),!.
minword(S,R):-mw(S,R,0,'','').
mw(S,S2,1,S2,MINWORD):-string_length(S,0),string_length(MINWORD,0).
mw(S,S2,1,S2,MINWORD):-string_length(S,0),string_length(S2,S2L),string_length(MINWORD,MWL),S2L < MWL.
mw(S,MINWORD,_,_,MINWORD):-string_length(S,0).
mw(S,R,1,S2,MINWORD):-frontchar(S,C,S1),isdel(C),string_length(MINWORD,0), mw(S1,R,0,'',S2).
mw(S,R,1,S2,MINWORD):-frontchar(S,C,S1),isdel(C),string_length(S2,S2L),string_length(MINWORD,MWL),S2L < MWL, mw(S1,R,0,'',S2).
mw(S,R,1,_,MINWORD):-frontchar(S,C,S1),isdel(C),mw(S1,R,0,'',MINWORD).
mw(S,R,0,_,MINWORD):-frontchar(S,C,S1),isdel(C),mw(S1,R,0,'',MINWORD).
mw(S,R,_,S2,MINWORD):-frontchar(S,C,S1), string_concat(S2,C,S2a), mw(S1,R,1,S2a,MINWORD).
isvovel(C):-char_code(C,65).
isvovel(C):-char_code(C,73).
isvovel(C):-char_code(C,85).
isvovel(C):-char_code(C,69).
isvovel(C):-char_code(C,79).
isvovel(C):-char_code(C,89).
isvovel(C):-char_code(C,97).
isvovel(C):-char_code(C,105).
isvovel(C):-char_code(C,117).
isvovel(C):-char_code(C,101).
isvovel(C):-char_code(C,111).
isvovel(C):-char_code(C,121).
deletevovel(S,''):-string_length(S, 0),!.
deletevovel(S,R):-frontchar(S,C,S1),isvovel(C),deletevovel(S1,R),!.
deletevovel(S,R):-frontchar(S,C,S1),deletevovel(S1,R1),string_concat(C,R1,R).
Программа вызывается предикатом goal.
Начнем с простого меню. Это самая легкая часть программы. Вначале мы позволяем пользователю, ввести строку, затем отображаем список вариантов, и пользователь выбирает ему нужный. Сразу отмечу особенность всех программ: в связи с тем, что при выполнении пролог программ в SWI-прологе, предикаты вида isspace(‘ ‘). не работают корректно, когда я вызываю его внутри функций от различных значений, то была использована альтернатива – этот символ переводится в код этого символа, и сравнивается с его номер в таблице символов SWI пролога. Это никак не повлияло на работоспособность программы, лишь немного усложнилась читаемость кода, но при наличии описания предикатов, и не работоспособности выше указанного варианта решил использовать его.
Рассмотрим 1-ую задачу.
a. Количество цифр в строке.
В ней мы последовательно проверяем является ли каждый символ числом, и увеличиваем счетчик на 1 если является, или переходим к следующему символу, если это не выполняется.
Тестирования 1-го пункта.
b. Количество слов в строке. Слова отделяются одним или несколькими символами "пробел", "," , "." , ";", "-",”!”,”?”.
Вначале был определен предикат isdel. В нем перечисляются коды символов-разделителей, и если символ является таковым, то возвращается true. Далее используется предикат tw , который имеет 2 состояние – ожидание окончания слова, и состояние символа-разделителя.
В 1-ом случае мы ждем символа-разделителя, и когда его получаем, то увеличиваем счетчик на 1 и переходим во 2-ое состояние. А во 2-ом состоянии мы ждем начала слова и затем переходим в 1-ое состояние.
Тестирования программы.
c. Удаляет лишние пробелы между словами.
Не указано что принято считать «лишними» пробелами. Будем считать, что когда пробелов больше 1-го подряд, то из них все кроме 1-го являются лишними. В случае наличия пробелов в конце и в начале, будем аналогично удалять все кроме 1-го. Решение представлено предикатом os. Для решения мы опять же используем 2 состояния. 1-ое состояние – нормальное состояние, в котором мы просто переписываем строку в результат, ожидая пробела для перехода во 2-ое.
2-ое состояние – состояние введенного пробела. Мы не включаем в результат все последующий пробелы, и при получении символа отличного от пробела переходим в состояние 1.
Тестирование программы:
d. меняет все вхождения слова "пес" на слово "кот"
Данная задача решается предикатом pesvkot, который использует pvk.
В ней мы используем следующие переменные pvk(S,R1,STATE,RESSTR,BEFORESTATE).
S – передаваемая строка.
R1 – результат.
3-ий параметр – состояние программы:
Имеется 3 состояния:
-
Получение произвольных символов отличных от ‘п’ – 0.
-
Получение символа ‘п’ – 1.
-
Получение символа ‘е’ после ‘п’ – 2.
И далее, если мы находимся в 3-ем состоянии ( состояние 2 в программе) то в случае получения буквы ‘с’ – мы берем строку, которая была запомнена в переменной BeforeState, до вхождения в состояние 1, и добавляем к ней слово кот. Весь результат обработки мы храним в RESSTR, и затем возвращаем его через 2-ую переменную, что позволяет нам создать хвостовую рекурсию.
Результаты тестирования:
e. Определяет количество чисел в строке
Т. к. не указана четкое определение какие числа, и при каких условиях надо выделять, то были взяты следующие условия – целые положительные числа, которые с обеих сторон отделены пробелами.
Т. е. в строке ‘123eaf 4235 123 0012’ числами будут являться 4235 и 123,
Т. е. результатом будет 2.
В данном случае использовался предикат numinstring(S,N) который вызывал вспомогательный предикат nis(S,N,1), где 3-яя переменная – переменная состояния, которая работает аналогично предыдущих случаев, только тут уже было использовано больше вариантов. Стоит отметить, что в случае необходимости изменения условий выделений чисел, будут немного изменены переменные состояние, в случае необходимости учета дробей, или рациональных чисел, добавятся опять же новые состояния и новые предикаты используемых символов. В данном варианте используются предикаты iszero, и isnum.
Результаты тестирования:
f. Находит в строке самое короткое слово.
Будет выбирать первое самое короткое слово.
Данное задания мы решаем с помощью предиката minword(S,R) и основного рабочего предиката mw(S,R,0, S2, MINWORD).
В данном предикате
S – получаемая строка
R – результат
3-ая переменная переменная состояния, которая используется для того чтобы определить обрабатываем ли мы слово, или разделители.
S2 – переменная в которой мы накапливаем каждое последующее слово
MINWORD – минимальное на данный момент слово.
Алгоритм следующий – мы последовательно выделяем слова, находим их длину, и если их длина меньше текущей минимальной, то мы заменяем минимальное значение на новую величину, и в конце возвращаем результат через 2-ую переменную. Это также нам дало возможность создавать хвостовую рекурсию.
Тестирования программы:
g. Удаляет из строки гласные буквы.
Предикат является довольно таки легким, мы определяем предикат isvovel(C) и затем пройдясь по всему списку символов, проверяем, является ли он гласной, и если да, то не добавляем его в результирующую строку. (предикат deletevovel).
Результаты тестирования:
2. Написать программу, определяющую – является ли введенное
предложение палиндромом. Пример строки – палиндрома
«аргентина манит негра». Строчные или заглавные буквы,
пробелы и знаки препинания не учитывать.
Код программы:
isdel(C):-char_code(C,32).
isdel(C):-char_code(C,44).
isdel(C):-char_code(C,46).
isdel(C):-char_code(C,59).
isdel(C):-char_code(C,45).
isdel(C):-char_code(C,33).
isdel(C):-char_code(C,63).
frontchar(S, C, S1):-string_concat(C, S1, S), string_length(C, 1),!.
deletedel(S,''):-string_length(S, 0),!.
deletedel(S,R):-frontchar(S,C,S1),isdel(C),deletedel(S1,R),!.
deletedel(S,R):-frontchar(S,C,S1),deletedel(S1,R1),string_concat(C,R1,R).
palindrom(S):-string_length(S,1).
palindrom(S):-deletedel(S,S2),downcase_atom(S2,S3),string_length(S3,L),L1 is L-1,isp(S3,L1,0).
isp(_,L,K):-R is L div 2, K > R+1.
isp(S3,L,K):-sub_string(S3,K,1,_,C1),L1 is L-K,sub_string(S3,L1,1,_,C2),char_code(C1,CC1),char_code(C2,CC2),CC1 =:= CC2,K1 is K+1,isp(S3,L,K1).
Для решения данной задачи я использовал следующий алгоритм:
-
Прошелся по всей строке и удалил символы-разделители.
-
Перевел всю строку в нижний регистр стандартным методом.
-
С помощью предиката sub_string выделяются символы в начале и в конце строки, и так они сравниваются пока не дойдут до средины. Если все время все условия выполнялись, то предложение палиндромом – иначе нет.
Результаты тестирования:
Вывод
В данной лабораторной работе были получены основные навыки по обработке строк в пролог программах, а также изучены основные особенности работы со строками в SWI-Prolog среде