1. лексический анализ. ИССЛЕДОВАНИЕ алгоритмоВ обработки строк

1. лексический анализ. ИССЛЕДОВАНИЕ алгоритмоВ обработки строк

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

1. 1 Подготовка к лабораторной работе

При подготовке к лабораторной работе необходимо изучить:

- алгоритмы выделения слов в строках;

- способы удаления, вставки и обработки слов.

1. 2 Теоретические сведения

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

В качестве примера рассмотрим строку str, в которой слова разделяются пробелами.

Алгоритм 1.

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

Цикл для пропуска пробелов между словами:

while (str[i] == ' ' & & i < strlen(str))

++i; //пропустить пробелы

Слова можно пропустить аналогичным циклом:

while (str[i]! = ' ' & & i < strlen(str))

++i; // пропустить все символы слова

Эти два цикла должны быть включены во внешний цикл, который закончится тогда, когда закончится строка.

Пример 1. 1. Вывод на экран всех слов строки str ( Алгоритм 1 ):

int main()

{

int i = 0, begin = 0, end = 0;

char str [100], sl[100];

cout< < " Vvedite stroku";

cin. getline(str, 100, '\n');

int len= strlen(str);

sl[0] = '\0';

while (i < len)

{

while (str[i] == ' ' & & i < len)

++i; //пропустить пробелы

begin = i; // номер первого символа слова

while (str[i]! = ' ' & & i < len)

++i; // пропустить все символы слова

end = i; // номер символа, следующего за последним символом слова

strncpy(sl, & str[begin], end-begin); //записать слово в sl

sl [end-begin] = '\0'; // добавить символ конца строки

cout< < sl< < '\n'; ; // вывод слова

}

system(" pause" );

return 0;

}

Пример 1. 2. Вывод на экран всех слов строки str ( Алгоритм 2).

int main()

{ char str [100], sl[100];

int k = 0, i;

cout< < " Vvedite stroku";

cin. getline(str, 100, '\n');

strcat (str, " " );

cout< < " Slova: ";

sl[0] = '\0';

for (i=0; i< strlen(str); i++) //проход по строке

if (str [i]! = ' ') //если символ строки отличен от пробела

sl[k++] = str [i]; //записываем его переменную sl для хранения слова

else //если символ строки пробел

{

if (strlen (sl) > 0) //если длина слова отлична от нуля

{sl[k] = '\0'; cout< < sl< < '\n'; }// добавить символ '\0' и вывести слово

sl[0] = '\0';

k = 0;

}

system(" pause" );

return 0;

}

Функции работы с символьными строками (объявлены в заголовочном файле < stdlib. h> ):

double atof (const char *str) // преобразует строку str в вещественное число //типа double

int atoi (const char *str) // преобразует строку str в целое число типа int

long atol (const char *str) // преобразует строку str в целое число типа long

char *itoa (int v, char *str, int baz) //преобразует целое v в строку str. При //изображении числа используется основание baz //(2< =baz< =36)

char *ltoa (long v, char *str, int baz) // преобразует длинное целое v в строку str. //При изображении числа используется основание baz (2< =baz< =36)

char *ultoa (unsignedlong v, char *str, int baz) // преобразует беззнаковое длинное //целое v в строку str второй строки

Функции работы с символьными строками (объявлены в заголовочном файле < string. h> ):

char* strcpy(char* p, const char* q) //копирование из q в p

char* strcat(char* p, const char* q) //добавление q к p

size_t strlen(const char* p) //длина p (не считая конца строки)

int strcmp(const char* p, const char* q) //сравнение p и q; меньше (-1), равно (0), //больше(1)

char *strchr(const char *, int) // находит первое вхождение заданного //символа в строке

char *strncat(char *, const char *, size_t) // добавляет заданное число символов

//второй строки в конец первой

int strncmp(const char *, const char *, size_t) // сравнивает заданное число символов

//двух строк

char *strncpy(char *, const char *, size_t) // копирует заданное число символов

//второй строки в первую строку

char *strrchr(const char *, int) // находит последнее вхождение заданного

//символа в строке

char *strstr(const char *, const char *) // находит первое вхождение второй

//строки как подстроки первой

Из файла < ctype. h>:

int isdigit(int); // определяет, цифра или нет

int isalpha(int); //буква

int isupper(int); //буква в верхнем регистре

int islower(int); //буква в нижнем регистре

int isspace(int); //символ – разделитель

int ispunct(int); //символ пунктуации (ни один из вышеупомянутых)

int isalnum(int); //буква или цифра

int toupper(int); //перевод в верхний регистр

int tolower(int); //перевод в нижний регистр

Пример 1. 3. Дана строка, состоящая из слов, разделенных пробелами (одним или несколькими). Записать все слова в массив. Подсчитать количество слов, содержащих цифры. Сформировать новую строку со словами, расположенными в обратном порядке.

#include " stdafx. h"

#include < iostream>

#include < string. h>

#include < ctype. h>

#include < conio. h> // файл, где определена функция getch()

using namespace std;

int main()

{

char str[100], sl[100];

cout< < " InputLine: ";

cin. getline(str, 100, '\n');

int k = 0;

int len = strlen(str); //длина введённого текста

char words[50][30]; // массив для хранения слов

int i = 0;

int begin = 0, end = 0;

int count = 0, count_digit = 0;

while (i < len)

{

while (str[i] == ' ' & & i < len)

++i; //пропустить пробелы

begin = i; // номер первого символа слова

bool fl=false;

while (str[i]! = ' ' & & i < len) //если символ строки отличен от пробела

{

if (str [i]> ='0'& & str [i]< ='9') fl=true; //если символ слова цифра

//можно использовать isdigit(str [i]) для латиницы

++i; // пропустить все символы слова

}

end = i; // номер символа, следующего за последним символом слова

if (fl==true) count_digit++; //если в слове есть цифры, увеличиваем //count_digit

strncpy(words[count], & str[begin], end-begin); //записать слово в массив

words[count++][end-begin] = '\0'; // добавить символ конца строки

}

cout< < " Array of words: "; // вывод массива слов

for(i = 0; i < count; ++i)

cout< < words[i]< < " \n";

cout< < " Word count, in which there are digits: " < < count_digit< < " \n";

sl[0] = '\0';

cout< < " String with the words in reverse order";

for(i = count-1; i > = 0; --i) {strcat(sl, words[i]); strcat(sl, " " ); }// формирование новой //строки sl

cout< < sl< < '\n';

getch(); // ждать нажатия любой клавиши

return 0;

}

Пример 1. 4. Дана строка, состоящая из слов, разделенных пробелами (одним или несколькими). Записать все слова в массив. Сформировать две новых строки со словами четной и нечетной длины.

#include " stdafx. h"

#include < iostream>

#include < string. h>

#include < conio. h> // файл, где определена функция getch()

using namespace std;

int main()

{ char str [100], n_str1 [100], n_str2 [100], sl[100];

int k = 0, i;

cout< < " Vvedite stroku";

cin. getline(str, 100, '\n');

strcat (str, " " );

cout< < " Slova: ";

sl[0] = '\0';

n_str1[0]='\0';

n_str2[0] ='\0';

for (i=0; i< strlen(str); i++) //проход по строке

if (str [i]! = ' ') //если символ строки отличен от пробела

sl[k++] = str [i]; //записываем его в переменную sl для хранения слова

else //если символ строки пробел

{

if (strlen (sl) > 0)//если длина слова отлична от нуля

{

sl[k] = '\0';

if (strlen (sl)%2==0) {strcat(n_str1, sl); strcat(n_str1, " " ); }//если длина //слова четная

else {strcat(n_str2, sl); strcat(n_str2, " " ); }//если длина слова нечетная

}

sl[0] = '\0';

k = 0;

}

cout< < " string with the words of even length\n";

cout< < n_str1< < '\n'; // вывод строки со словами четной длины

cout< < " string with the words of odd length\n";

cout< < n_str2< < '\n'; // вывод строки со словами нечетной длины

system(" pause" );

return 0;

}

Пример 1. 5 (с использованием класса string). Дана строка, состоящая из слов, разделенных пробелами (одним или несколькими) и символами пунктуации. Вывести те слова строки, которые являются числами типа long, и удалить их из исходной строки. Все остальные слова строки выделить символом ‘*’ с обеих сторон.

#include " stdafx. h"

#include < iostream>

#include < string>

#include < clocale>

#include < conio. h>

using namespace std;

int main()

{

setlocale (LC_CTYPE, " rus" );

string str, s;

cout< < " InputLine: ";

getline(cin, str, '*'); // ввод текста

str+=" ";

int len = str. size(); //длина введённого текста

int i = 0;

int begin = 0, end = 0;

cout< < " Числа типа long в строке\n";

while (i < str. size()-1)

{

while ((isspace(str[i])||ispunct(str[i]))& & i < str. size()-1)

++i; //пропустить пробелы и любые разделители

begin = i; // номер первого символа слова

while (! isspace(str[i])& &! ispunct(str[i])& & i < str. size()-1)

++i; // пропустить все символы слова

end = i; // номер символа, следующего за последним символом слова

s=str. substr(begin, end-begin); // копируем в s (end-begin)символов строки str, //начиная с begin

if (atol(s. c_str())) //если преобразование строки s в целое число типа long //прошло успешно

{

cout< < atol(s. c_str())< < " \n"; //вывод числа

str. erase(begin, end-begin); i=i-(end-begin); //ПРИ УДАЛЕНИИ //ДОЛЖНЫ УМЕНЬШИТЬ i НА КОЛИЧЕСТВО УДАЛЕННЫХ СИМВОЛОВ!

}

else {str. insert (begin, 1, '*'); i++; str. insert (end+1, 1, '*'); i++; }//ПРИ ВСТАВКЕ //ДОЛЖНЫ УВЕЛИЧИТЬ i НА КОЛИЧЕСТВО ВСТАВЛЕННЫХ СИМВОЛОВ!

}

cout< < " Строка без чисел с остальными словам, выделенными звездочками\n";

cout< < str< < " \n";

getch(); // ждать нажатия любой клавиши

return 0;

}

12 Следующая ⇒