Типовые программы обработки строк
В Турбо Паскале, как отмечалось выше, используются данные строкового типа – string. Операции, процедуры и функции, применяемые для этих типов, уже рассмотрены. Пример 1. Ввести в ЭВМ массив из n (n< =50) слов на английском языке. Расположить их по алфавиту. Латинские буквы любой ЭВМ, как известно, представляются кодами, которые упорядочены по алфавиту (от " a" до " z"). Слово – это строка, которую можно считать длинным двоичным кодом. Для упорядочения таких кодов можно использовать методы упорядочения чисел, например, метод " пузырька", который был изучен ранее. Программа будет иметь вид Program SortW; Const Nmax = 20; {Количество слов} m = 10; {Максимальная длина слова} Var W: Array[1..Nmax] of string[m]; {Массив для хранения слов} Wr: String[m]; {Промежуточная переменная для перестановок} n, i, k: integer; Begin WriteLn('Введите количество слов'); Readln(n); WriteLn('Введите слова'); for i: = 1 to n do ReadLn(w[i]); for k: = 1 to n-1 do for i: = 1 to n-k do if w[i] > w[i+1] then begin Wr: = w[i]; w[i]: = w[i+1]; w[i+1]: = Wr; end; WriteLn(Слова, упорядоченные по алфавиту: '); for i: = 1 to n do WriteLn(w[i]); End. В таблицах кодировки символов, содержащих буквы кириллицы, коды букв кириллицы также упорядочены по алфавиту. Студентам предоставляется возможность проверить самостоятельно работу алгоритма на русских словах. Наиболее типичными задачами обработки текстов являются задачи синтаксического анализа, которые сводятся к выделению слов из предложений и анализу этих слов. В частности, такие задачи решаются при трансляции и компиляции программ с языков высокого уровня. Основными особенностями структур данных при этом являются следующие. 1. Строка текста или одно слово – одномерный массив символов, а несколько слов – это массив строк (двумерный массив символов). 2. Длина слов в тексте, как правило, неодинакова. Обычно для их разделения используются пробелы. Найти пробел в предложении можно, просматривая последовательно каждый его символ (так как пробел – это тоже символ). Если очередной пробел найден, то предыдущее слово закончилось. Формирование отдельных слов может быть осуществлено посимвольно, путем объединения слова (строки) с очередным символом, отличным от пробела. Ясно, что вначале формируемое слово должно быть пустым. Второй метод – запоминание положения первой и последней букв очередного слова в предложении и использование функции Copy для его выделения. Возможны 2 способа представления текстов: 1) слова разделены всегда одним пробелом; 2) слова разделены одним или несколькими пробелами (общий случай). Методы выделения слов при этом несколько отличаются.
16.1. Выделение слов из текста Условие. Ввести в ЭВМ предложение, в котором слова разделены одним пробелом. Выделить слова, переписать их в массив слов и вывести на экран. В самом общем виде алгоритм решения задачи может быть таким. 1. Ввести предложение 2. Выделить слова 3. Вывести слова 4. Закончить. Уточняем пункты алгоритма. 1.1. Ввести предложение 1.2. n = Длина (предложения) 2.1. k = 1; {Номер слова} 2.2. Слово[k] = ''; { пустое слово } 2.3. Для номера буквы в предложении (i) от 1 до n выполнить 2.3.1. Если предл[i] < > ' ', то {очередной символ – не пробел} Слово[k] = Слово[k] + предл[i] Иначе {т.е. предл[i]= пробелу; значит, конец предыдущего слова} а) k = k+1 б) Слово[k] ='' { пустое слово } 3.1. Для номера слова (i) от 1 до k выполнить 3.1.1. Вывести слово[i] 4. Закончить. Приводимая ниже программа реализует рассмотренный алгоритм. Program GetSl1; CONST m = 50; {Максимальное количество слов в предложении} VAR Predl: string; {Предложение} Slovo: array[1..m] of string; {Массив для слов} n, k, i: integer; {Вспомогательные переменные} BEGIN WriteLn('Вводите предложение: '); ReadLn(Predl); n: = Length(Predl); {п. 1.2.} k: = 1; Slovo[k]: = ''; {Пустое слово – 2 апострофа подряд} {п. 2.3.} For i: = 1 to n do If predl[i] < > ' ' then Slovo[k]: = Slovo[k] + Predl[i] Else begin k: = k + 1; Slovo[k]: = ''; end; {п. 3.1.} WriteLn('Слова из предложения: '); For i: = 1 to k do WriteLn(Slovo[i]); END.
16.2. Выделение слов из текста Условие. Ввести в ЭВМ предложение, в котором слова могут быть разделены одним или несколькими пробелами. Выделить слова и вывести их на экран. В этом случае задача осложняется тем, что номер слова необходимо менять только при встрече с первым пробелом, а все последующие пробелы – просто пропускать. Алгоритм будет отличаться от предыдущего в основном в части, связанной с обработкой пробелов. Алгоритм для этой задачи 1.1. Ввести предложение. 1.2. n: = Длина (предложения). 2.1. Номер слова (k): = 1. 2.2. Слово[k]: = ''. 2.3. Номер символа (i): = 1. 2.4. Пока i < = n повторять 2.4.1. Если предл[i] < > ' ', ТО а) Слово[k]: = Слово[k] + предл[i]; б) i: = i + 1 Иначе а) k: = k + 1; б) Слово[k]: = '' в) Пока (предл[i]=' ') И (i< =n) выполнить i = i + 1; 3.1. Для i от 1 до k выполнить вывести слово[i]; 4. Закончить.
Приводимая ниже программа реализует рассмотренный алгоритм.
Program GetSl2; const m = 50; Var Predl: string; Slovo: array [1..m] of string; n, k, i: integer; Begin n: = Length(Predl); k: = 1; Slovo[k]: = ''; i: = 1; While i< =n do If predl[i] < > ' ' then {символ – не пробел} begin Slovo[k]: = slovo[k] + predl[i]; i: = i + 1; end Еlse {символ – пробел} begin k: = k + 1; slovo[k]: = ''; While (predl[i]=' ') and (i < = n) do i: = i + 1; end; WriteLn('Слова из предложения: '); For i: = 1 to k do WriteLn(slovo[i]); END.
16.3. Некоторые типовые алгоритмы и программы
Рассмотрим примеры некоторых наиболее часто встречающихся задач обработки слов из текстов. В таких задачах вначале выделяются слова из текста с использованием алгоритмов, описанных выше. Затем полученные массивы слов (строк) обрабатываются в соответствии с условиями задачи. Задачи типа 1 связаны с определением длины слов. Пример 1.1. Ввести в ЭВМ предложение, в котором слова могут быть разделены несколькими пробелами. Выделить слова и вывести их на экран. Затем подсчитать количество слов с четным числом букв и вывести эти слова и их количество. Для решения задачи можно предложить следующий алгоритм. 1. Ввести предложение 2. Выделить слова 3. Вывести слова 4. Подсчитать и вывести количество слов с четным числом букв 5. Закончить. Уточняем пункты алгоритма. 1.1. Ввести предложение 1.2. n: = Длина (предложения) 2.1. Номер слова (k): = 1 2.2. Слово[k]: = '' 2.3. Номер символа (i): = 1 2.4. Пока i < = n повторять 2.4.1. Если предл[i] < > ' ', то а) Слово[k]: = Слово[k] + предл[i]; б) i: = i + 1 Иначе а) k: = k + 1; б) Слово[k]: = '' в) Пока (предл[i]=' ') И (i< =n) выполнить i = i + 1; 3.1. Для i от 1 до k выполнить вывести слово[i] 4.1.Количество_слов = 0. 4.2. Для i от 1 до k выполнять Если Длина(слово[i]) mod 2 = 0 то а) вывести слово[i]; б) Количество_слов = Количество_слов +1. 4.3. Вывести Количество_слов. 5. Закончить. Приводимая ниже программа реализует рассмотренный алгоритм. Program Not_Odd_Sl; const m = 50; Var Predl: string; Slovo: array [1..m] of string; n, k, i, kol: integer; BEGIN { Выделение слов из предложения – п.п. 1 -3 } n: = Length(Predl); k: = 1; Slovo[k]: = ''; i: = 1; While i< =n do If predl[i] < > ' ' then {символ – не пробел} begin Slovo[k]: = slovo[k] + predl[i]; i: = i + 1; end Еlse {символ – пробел} begin k: = k + 1; slovo[k]: = ''; While (predl[i]=' ') and (i < = n) do i: = i + 1; end; WriteLn('Слова из предложения'); For i: = 1 to k do WriteLn(slovo[i]); Kol: =0; WriteLn('Слова с четным количеством букв'); For i: = 1 to k do If Length(slovo[i]) mod 2 =0 then Begin WriteLn(slovo[i]); Kol: = kol+1; End; WriteLn('Количество слов с четным числом букв=', kol); Writeln('Работа окончена. Нажмите клавишу ENTER'); Readln; END.
Пример 1.2. Ввести в ЭВМ предложение. Упорядочить его слова по возрастанию длины и вывести их в столбик.
Для решения этой задачи воспользуемся методом сортировки «пузырьком», который применим к длинам слов. Алгоритм будет следующий. 1. Ввести предложение. 2. Выделить слова. 3. Вывести слова. 4. Упорядочить слова по возрастанию длины. 5. Вывести упорядоченные слова. 6. Закончить. Уточним пункты 4 и 5 и получим алгоритм. 4. Для j от 1 до k-1 выполнить 4.1. Для i от 1 до k-j выполнять Если слово[i] > слово[i+1] то Поменять их местами. 5. Для i от 1 до k выполнять вывести слово[i]. Приведем фрагмент программы, реализующий эти пункты. {Упорядочение слов} For j: = 1 to k-1 do For i: = 1 to k-j do If Length(slovo[i])> Length(slovo[i+1]) then Begin RSl: = slovo[i]; slovo[i]: = slovo[i+1]; slovo[i+1]: =Rsl; End; WriteLn('Упорядоченные слова из предложения'); For i: = 1 to k do WriteLn(slovo[i]);
Задачи типа 2 связаны с определением окончаний слов.
Пример 2.1. Ввести в ЭВМ строку, содержащую названия единиц физических величин. Вывести названия единиц длины и подсчитать их количество. При разработке алгоритма учтем, что искомые названия имеют окончание «метр»: сантимерт, километр, дециметр и т.д. Алгоритм может быть следующий. 1. Ввести строку. 2. Выделить из нее слова. Общее количество слов = k. 3.1. Количество_длин = 0. 3.2. Для i от 1 до k выполнить 3.2.1. n = Длина(слово[i]). 3.2.2. Если Подстрока(из слово[i] от номера n –3 длиной 4) = «метр» то а) вывести слово[i]; б) Количество_длин = Количество_длин +1. 3.3. Вывести Количество_длин. 4. Закончить. Приведем фрагмент программы, реализующий пункт 3. kol: =0; WriteLn('Названия единиц длины'); For i: = 1 to k do Begin n: =Length(slovo[i]); If Copy(Slovo[i], n-3, 4) = ‘метр’ then Begin WriteLn(slovo[i]); Kol: = kol+1; End; End; WriteLn('Количество названий единиц длины=', kol);
Задачи типа 3 связаны с анализом первых букв слов.
Пример 3.1. Ввести в ЭВМ строку, содержащую слова и числа в символьном виде. Вывести входящие в нее числа и их количество. При разработке алгоритма будем считать, что слово из строки, начинающееся с цифры, является числом. Кроме того, воспользуемся тем, что коды цифровых символов упорядочены от ‘0’ до ‘9’.
Алгоритм для решения этой задачи может быть следующий. 1. Ввести строку 2. Выделить из нее слова. Общее количество слов = k 3.1. Количество_чисел = 0. 3.2. Для i от 1 до k выполнять Если (слово[i, 1] > =’0’) И (слово[i, 1] < =’9’) то а) вывести слово[i]; б) Количество_чисел = Количество_ чисел +1. 3.3. Вывести Количество_чисел. 4. Закончить.
Приведем фрагмент программы, реализующий пункт 3.
{Нахождение чисел} kol: =0; WriteLn('Числа из строки'); For i: = 1 to k do If (Slovo[i, 1]> =’0’) And (Slovo[i, 1]< =’9’) then Begin WriteLn(slovo[i]); Kol: = kol+1; End; WriteLn('Количество чисел=', kol);
|
