← До переліку лабораторних робіт
Лабораторна робота №9. Обробка рядків
Варіант 19 · Виконав: Одарчук Олексій, КНУ імені Тараса Шевченка, ФІТ, група ІПЗ-11 · C17, gcc
1. Мета роботи
- Вивчити подання рядків у мові C: поточну та загальну довжину, ознаку кінця рядка.
- Опанувати бібліотечні функції обробки рядків заголовного файла string.h.
- Навчитися розробляти алгоритми обробки текстів, поданих масивами рядків.
2. Умова задачі
Завдання 1 (19.1)
Увести з клавіатури рядок слів, які відділяються символами пропуску, комами, точками. Слово є послідовністю символів без розділових символів усередині. Передбачити меню для виконання таких дій:
- підрахувати кількість слів, які містять однакову кількість голосних і приголосних літер;
- вивести на екран усі слова, довжина яких менша заданої з клавіатури;
- видалити всі слова, передостання літера яких голосна.
Завдання 2 (19.2)
Увести з клавіатури декілька рядків символів. У кожному рядку записаний арифметичний або логічний вираз в інфіксній формі (звичайній). На екран вивести вираз у постфіксній формі. У постфіксній формі символ операції записується справа від операндів, дужки не застосовуються. Наприклад, вираз (a+b)/c, записаний в інфіксній формі, у постфіксній формі матиме вигляд: a b + c /. Необхідно для кожного виразу в інфіксній формі вивести його аналог у постфіксній формі.
Контрольний тест з умови варіанта:
Уведені рядки: (a + b) / (c – d)
(2*a – 3*d)*c + 2*b
Отримані рядки: a b + c d – /
2 a * 3 d * – c * 2 b * +
Обмеження умови: забороняється використовувати STL, методи класу
string, ітератори, контейнери. Дозволено використовувати функції заголовних
файлів string.h, ctype.h, stdlib.h.
3. Аналіз задачі та теоретичне обґрунтування
Завдання 1. Головна проблема: кодування UTF-8
Функції класифікації символів із ctype.h (isalpha,
tolower та інші) працюють з окремими байтами і придатні лише для
однобайтових кодувань. У сучасному UTF-8 українська літера займає два байти, тому:
-
isalpha()для кириличної літери дає хибний результат — вона розпадається на два байти, жоден з яких літерою не є; -
довжина слова, визначена як
strlen(), була б удвічі більшою за кількість літер, і умова «довжина слова менша заданої» виконувалась би неправильно; - визначити «передостанню літеру» побайтово взагалі неможливо.
Розв'язання: реалізовано власне декодування UTF-8 у код символу (кодову позицію Unicode) та класифікацію літер за кодами. Старші біти першого байта задають довжину послідовності:
0xxxxxxx — 1 байт (латиниця, цифри, розділові знаки) 110xxxxx — 2 байти (зокрема кирилиця) 1110xxxx — 3 байти 11110xxx — 4 байти 10xxxxxx — продовжувальний байт
Декодер перевіряє кожен продовжувальний байт. Якщо послідовність неповна або некоректна — наприклад, текст уведено в іншому кодуванні чи слово обрізано посередині літери, — перший байт вважається окремим недійсним символом, який не є літерою. Тому розбір ніколи не виходить за кінець рядка.
Функції isLetterCode() та isVowelCode() охоплюють і латиницю, і
кирилицю. Українські голосні: а, е, є, и, і, ї, о, у, ю, я. Окремої уваги потребують
літери є, і, ї, ґ: у таблиці Unicode вони розташовані поза основним кириличним
блоком (0x0454, 0x0456, 0x0457, 0x0491), тому проста перевірка діапазону А…я їх не охопила
б.
Функції string.h застосовуються там, де побайтова робота коректна:
strtok() для розбиття на слова (розділові символи однобайтові),
strcpy() і strncpy() для копіювання, strchr() для
перевірки, чи вмістився введений рядок у буфер.
Завдання 1. Особливість функції strtok()
Функція strtok() має дві особливості, які треба враховувати. По-перше, вона
змінює вхідний рядок, замінюючи розділові символи нульовими — тому розбір
виконується над копією рядка, а не над оригіналом. По-друге, вона зберігає внутрішній стан
між викликами: перший виклик отримує рядок, а наступні замість нього нульовий покажчик.
Завдання 1. Крайні випадки
Слово може містити менше двох літер — тоді передостанньої літери не існує. Таке слово не видаляється, і програма повідомляє причину, а не мовчки лишає його. Символи, які не є літерами (цифри, дефіси всередині слова), не враховуються ані в лічильниках голосних і приголосних, ані під час пошуку передостанньої літери.
Видалення реалізовано ущільненням масиву: слова, що лишаються, послідовно переписуються на початок, після чого кількість слів зменшується. Це один прохід замість зсуву всього масиву при кожному видаленні.
Завдання 2. Алгоритм сортувальної станції
Перетворення виконується алгоритмом сортувальної станції (алгоритм Дейкстри). Вираз переглядається зліва направо, використовується стек знаків операцій:
- операнд одразу дописується до вихідного рядка;
- відкривна дужка заноситься до стеку;
- закривна дужка виштовхує зі стеку всі операції до відкривної дужки; сама пара дужок у результат не потрапляє;
- знак операції виштовхує зі стеку всі операції з не меншим пріоритетом (операції лівоасоціативні), після чого заноситься до стеку;
- після перегляду виразу зі стеку виштовхуються всі операції, що лишилися.
Саме тому постфіксна форма не потребує дужок: порядок операцій у ній задається взаємним розташуванням знаків, а не дужками. Трудомісткість алгоритму лінійна: кожен символ переглядається один раз, кожна операція заноситься до стеку й виштовхується з нього не більше одного разу.
Оскільки умова припускає і логічні вирази, таблицю пріоритетів доповнено логічними операціями:
4 унарне заперечення ! 3 множення, ділення, остача * / % 2 додавання, віднімання + − 1 порівняння < > 0 логічні І та АБО & |
Операндом вважається послідовність літер, цифр, символів підкреслення і крапки — це
охоплює як імена змінних (a, x1), так і числові сталі
(2, 3.5). Операнд переписується цілком як одна лексема, тому
багатоцифрові числа не розпадаються на окремі символи.
Завдання 2. Унарне заперечення та перевірка порядку лексем
Унарне заперечення ! стоїть перед своїм операндом, тому заноситься до стеку
без виштовхування інших операцій і потрапляє до результату після операнда:
!a & b → a ! b &, !!a → a ! !.
Під час перегляду виразу програма відстежує, що має йти далі: операнд (або відкривна дужка
чи !) або знак бінарної операції (або закривна дужка). Так виявляються не
лише незбалансовані дужки й неприпустимі символи, а й пропущені операнди (a + * b, a +) та пропущені знаки операцій (a b).
Контрольний тест в умові варіанта записано з типографським тире «–», а не зі знаком «-».
Щоб вираз, скопійований з тексту умови, розбирався так само, як набраний з клавіатури,
функція normalizeMinus() замінює тире (U+2013) і знак мінус (U+2212)
звичайним дефісом-мінусом. Тому в протоколі інфіксна форма виводиться вже з дефісом.
Рекомендована література (зі списку методичних вказівок): Ковалюк Т.В. Алгоритмізація та програмування. – Львів.: «Магнолія 2006», 2024. – 400 с.; Deitel P., Deitel H. C++ How to Program. Pearson Education, Inc. Hoboken, New Jersey. 2017. – 3015 p.; Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein Introduction to Algorithms, Third Edition 2009. – 960 p.
4. Блок-схема алгоритму
Схеми побудовано з текстів програм за допомогою rombik (rombik.app) відповідно до ДСТУ 19.701-90 (ISO 5807).
5. Текст програми
Завдання 1 — task1.c
/*==============================================================================
Лабораторна робота №9. Завдання 1. Варіант 19.
Тема: обробка рядків на основі бібліотеки функцій string.h.
Умова (таблиця 9.2, завдання 19.1): увести з клавіатури рядок слів, які
відділяються символами пропуску, комами, точками. Слово є послідовністю
символів без розділових символів усередині. Передбачити меню для виконання
таких дій:
- підрахувати кількість слів, які містять однакову кількість голосних
і приголосних літер;
- вивести на екран усі слова, довжина яких менша заданої з клавіатури;
- видалити всі слова, передостання літера яких голосна.
ОБМЕЖЕННЯ УМОВИ: забороняється використовувати STL, методи класу string,
ітератори тощо. Дозволено використовувати функції заголовних файлів
string.h, ctype.h, stdlib.h.
ЗАУВАЖЕННЯ ЩОДО КОДУВАННЯ. Функції класифікації символів із ctype.h
(isalpha та інші) працюють з окремими БАЙТАМИ і придатні лише для
однобайтових кодувань. У сучасному UTF-8 українська літера займає два
байти, тому isalpha() для неї дає хибний результат, а довжина слова,
визначена як strlen(), була б удвічі більшою за кількість літер.
Тому в програмі реалізовано власне декодування UTF-8 у код символу
та класифікацію літер за кодами — це охоплює і латиницю, і кирилицю.
Функції string.h (strtok, strcpy, strncpy, strchr) використовуються там,
де побайтова робота є коректною.
Виконав: Одарчук Олексій, КНУ імені Тараса Шевченка, ФІТ, група ІПЗ-11.
Компілятор: gcc -std=c17
==============================================================================*/
#include <stdio.h>
#include <stdbool.h>
#include <string.h>
/* Обмеження на розміри даних. У мові C межа масиву має бути сталим виразом
часу компіляції, а змінна з модифікатором const ним не є — тому розміри
задано директивами препроцесора, а не змінними. */
#define MAX_LINE 1024 /* довжина вхідного рядка в байтах */
#define MAX_WORDS 128 /* кількість слів */
#define MAX_WORD 64 /* довжина одного слова у байтах */
/* Розділові символи, якими відділяються слова (за умовою варіанта). */
const char *DELIMITERS = " \t\n,.";
/*==============================================================================
Робота з символами в кодуванні UTF-8
==============================================================================*/
/*------------------------------------------------------------------------------
utf8Decode — визначити код символу та кількість байтів, які він займає.
У кодуванні UTF-8 старші біти першого байта задають довжину послідовності:
0xxxxxxx — 1 байт (латиниця, цифри, розділові знаки);
110xxxxx — 2 байти (зокрема кирилиця);
1110xxxx — 3 байти;
11110xxx — 4 байти.
Продовжувальні байти мають вигляд 10xxxxxx і несуть по 6 значущих бітів.
Кожен продовжувальний байт перевіряється. Якщо послідовність неповна або
некоректна (зокрема обірвана завершальним нулем рядка), перший байт
вважається окремим недійсним символом U+FFFD. Тому функція ніколи не
«перестрибує» кінець рядка, навіть якщо текст уведено не в UTF-8.
Параметри:
s [вхідний] — покажчик на початок символу;
bytes [вихідний] — адреса змінної для кількості байтів символу.
Повертає : код символу (кодову позицію Unicode) або 0xFFFD.
Локальні змінні:
p — байти символу як беззнакові числа;
length — кількість байтів, яку задає перший байт;
code — накопичуваний код символу.
------------------------------------------------------------------------------*/
unsigned utf8Decode(const char *s, int *bytes)
{
const unsigned char *p = (const unsigned char *)s;
int length = 1;
unsigned code = p[0];
/* Маска лишає старші біти першого байта, решта бітів — початок коду. */
if ((p[0] & 0x80) == 0x00) {
*bytes = 1; /* 0xxxxxxx — однобайтовий символ */
return code;
} else if ((p[0] & 0xE0) == 0xC0) {
length = 2; /* 110xxxxx: 5 значущих бітів */
code = p[0] & 0x1F;
} else if ((p[0] & 0xF0) == 0xE0) {
length = 3; /* 1110xxxx: 4 значущі біти */
code = p[0] & 0x0F;
} else if ((p[0] & 0xF8) == 0xF0) {
length = 4; /* 11110xxx: 3 значущі біти */
code = p[0] & 0x07;
} else {
*bytes = 1; /* продовжувальний байт без початкового */
return 0xFFFD;
}
/* Кожен продовжувальний байт додає до коду шість молодших бітів. */
for (int i = 1; i < length; ++i) {
if ((p[i] & 0xC0) != 0x80) {
*bytes = 1; /* послідовність обірвана */
return 0xFFFD;
}
code = (code << 6) | (p[i] & 0x3F);
}
*bytes = length;
return code;
}
/*------------------------------------------------------------------------------
toLowerCode — звести код літери до нижнього регістру.
Обробляються латиниця (A..Z), основна кирилиця (А..Я) та окремі українські
літери Є, І, Ї, Ґ, які в таблиці Unicode розташовані поза основним блоком.
Параметри: code [вхідний] — код символу.
Повертає : код відповідної малої літери або сам код, якщо він не є великою літерою.
------------------------------------------------------------------------------*/
unsigned toLowerCode(unsigned code)
{
if (code >= 'A' && code <= 'Z')
return code + 32; /* латиниця */
if (code >= 0x0410 && code <= 0x042F)
return code + 32; /* А..Я */
if (code == 0x0404)
return 0x0454; /* Є -> є */
if (code == 0x0406)
return 0x0456; /* І -> і */
if (code == 0x0407)
return 0x0457; /* Ї -> ї */
if (code == 0x0490)
return 0x0491; /* Ґ -> ґ */
return code;
}
/*------------------------------------------------------------------------------
isLetterCode — чи є символ літерою (латиниця або кирилиця).
Параметри: code [вхідний] — код символу.
Повертає : true — символ є літерою.
------------------------------------------------------------------------------*/
bool isLetterCode(unsigned code)
{
const unsigned c = toLowerCode(code);
if (c >= 'a' && c <= 'z')
return true; /* латиниця */
if (c >= 0x0430 && c <= 0x044F)
return true; /* а..я */
if (c == 0x0454 || c == 0x0456 || c == 0x0457 || c == 0x0491)
return true; /* є, і, ї, ґ */
return false;
}
/*------------------------------------------------------------------------------
isVowelCode — чи є літера голосною.
Українські голосні: а, е, є, и, і, ї, о, у, ю, я.
Латинські голосні: a, e, i, o, u, y.
Параметри: code [вхідний] — код символу.
Повертає : true — літера голосна.
------------------------------------------------------------------------------*/
bool isVowelCode(unsigned code)
{
const unsigned c = toLowerCode(code);
/* Латинські голосні. */
if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u' || c == 'y')
return true;
/* Українські голосні: а(0430) е(0435) и(0438) о(043E) у(0443)
ю(044E) я(044F) є(0454) і(0456) ї(0457). */
if (c == 0x0430 || c == 0x0435 || c == 0x0438 || c == 0x043E || c == 0x0443 ||
c == 0x044E || c == 0x044F || c == 0x0454 || c == 0x0456 || c == 0x0457)
return true;
return false;
}
/*------------------------------------------------------------------------------
charCount — кількість СИМВОЛІВ у рядку (не байтів).
Параметри: s [вхідний] — рядок у кодуванні UTF-8.
Повертає : кількість символів.
Локальні змінні:
count — лічильник символів;
bytes — довжина поточного символу в байтах.
------------------------------------------------------------------------------*/
int charCount(const char *s)
{
int count = 0;
int bytes = 0;
for (const char *p = s; *p != '\0'; p += bytes) {
utf8Decode(p, &bytes);
++count;
}
return count;
}
/*------------------------------------------------------------------------------
printPadded — вивести рядок, доповнивши його пропусками до заданої ширини
в СИМВОЛАХ.
Специфікатор формату виду %-24s рахує байти, тому для тексту в кодуванні
UTF-8 він вирівнює таблиці неправильно. Ширина обчислюється функцією
charCount(), яка рахує саме символи.
Параметри:
s [вхідний] — рядок, що виводиться;
width [вхідний] — потрібна ширина поля в символах.
------------------------------------------------------------------------------*/
void printPadded(const char *s, int width)
{
printf("%s", s);
for (int i = charCount(s); i < width; ++i)
putchar(' ');
}
/*------------------------------------------------------------------------------
countVowelsConsonants — підрахувати голосні та приголосні літери слова.
Параметри:
word [вхідний] — слово;
vowels [вихідний] — адреса лічильника голосних;
consonants [вихідний] — адреса лічильника приголосних.
Символи, які не є літерами (цифри, дефіси всередині слова), не враховуються
в жодному з лічильників.
------------------------------------------------------------------------------*/
void countVowelsConsonants(const char *word, int *vowels, int *consonants)
{
*vowels = 0;
*consonants = 0;
int bytes = 0;
for (const char *p = word; *p != '\0'; p += bytes) {
const unsigned code = utf8Decode(p, &bytes);
if (!isLetterCode(code))
continue;
if (isVowelCode(code))
++(*vowels);
else
++(*consonants);
}
}
/*------------------------------------------------------------------------------
penultimateLetter — код передостанньої ЛІТЕРИ слова.
Параметри:
word [вхідний] — слово;
found [вихідний] — адреса ознаки: true, якщо у слові щонайменше дві літери.
Повертає : код передостанньої літери або 0, якщо літер менше двох.
Літерами вважаються лише символи, які проходять перевірку isLetterCode(),
тому цифри та інші символи не спотворюють результат.
Локальні змінні:
last, prev — коди останньої та передостанньої знайдених літер;
total — кількість знайдених літер.
------------------------------------------------------------------------------*/
unsigned penultimateLetter(const char *word, bool *found)
{
unsigned last = 0, prev = 0;
int total = 0;
int bytes = 0;
for (const char *p = word; *p != '\0'; p += bytes) {
const unsigned code = utf8Decode(p, &bytes);
if (!isLetterCode(code))
continue;
prev = last;
last = code;
++total;
}
*found = (total >= 2);
return *found ? prev : 0;
}
/*==============================================================================
Робота зі списком слів
==============================================================================*/
/* Слова вхідного рядка та їх кількість. */
char g_words[MAX_WORDS][MAX_WORD];
int g_count = 0;
/*------------------------------------------------------------------------------
splitIntoWords — розібрати рядок на слова за розділовими символами.
Використано бібліотечну функцію strtok() з string.h. Особливість її
застосування: strtok ЗМІНЮЄ вхідний рядок, замінюючи розділові символи
нульовими, і зберігає внутрішній стан між викликами — тому перший виклик
отримує рядок, а наступні замість нього нульовий покажчик. Через це
розбір виконується над копією рядка, а не над оригіналом.
Параметри: line [вхідний] — вхідний рядок.
Повертає : кількість знайдених слів.
Локальні змінні:
buffer — робоча копія рядка, яку змінює strtok;
token — покажчик на чергове слово;
count — лічильник слів.
------------------------------------------------------------------------------*/
int splitIntoWords(const char *line)
{
char buffer[MAX_LINE];
strncpy(buffer, line, MAX_LINE - 1);
buffer[MAX_LINE - 1] = '\0';
int count = 0;
char *token = strtok(buffer, DELIMITERS);
while (token != NULL && count < MAX_WORDS) {
strncpy(g_words[count], token, MAX_WORD - 1);
g_words[count][MAX_WORD - 1] = '\0';
++count;
token = strtok(NULL, DELIMITERS);
}
return count;
}
/*------------------------------------------------------------------------------
printWords — вивести поточний список слів у табличному вигляді.
Параметри: title [вхідний] — заголовок таблиці.
------------------------------------------------------------------------------*/
void printWords(const char *title)
{
printf("\n%s (слів: %d)\n", title, g_count);
if (g_count == 0) {
printf(" список порожній\n");
return;
}
for (int i = 0; i < g_count; ++i) {
int vowels = 0, consonants = 0;
countVowelsConsonants(g_words[i], &vowels, &consonants);
printf(" %2d. ", i + 1);
printPadded(g_words[i], 22);
printf(" довжина %2d, голосних %d, приголосних %d\n", charCount(g_words[i]),
vowels, consonants);
}
}
/*==============================================================================
Команди меню
==============================================================================*/
/*------------------------------------------------------------------------------
cmdCountBalanced — підрахувати слова з однаковою кількістю голосних
і приголосних літер.
Повертає : кількість таких слів.
------------------------------------------------------------------------------*/
int cmdCountBalanced()
{
int found = 0;
printf("\nСлова з однаковою кількістю голосних і приголосних:\n");
for (int i = 0; i < g_count; ++i) {
int vowels = 0, consonants = 0;
countVowelsConsonants(g_words[i], &vowels, &consonants);
if (vowels == consonants) {
printf(" %s (голосних %d = приголосних %d)\n", g_words[i], vowels,
consonants);
++found;
}
}
if (found == 0)
printf(" таких слів немає\n");
printf("Кількість слів з однаковою кількістю голосних і приголосних: %d\n", found);
return found;
}
/*------------------------------------------------------------------------------
cmdShorterThan — вивести всі слова, довжина яких менша за задану.
Параметри: limit [вхідний] — гранична довжина у символах.
Повертає : кількість виведених слів.
------------------------------------------------------------------------------*/
int cmdShorterThan(int limit)
{
int found = 0;
printf("\nСлова, довжина яких менша за %d:\n", limit);
for (int i = 0; i < g_count; ++i) {
const int length = charCount(g_words[i]);
if (length < limit) {
printf(" %s (довжина %d)\n", g_words[i], length);
++found;
}
}
if (found == 0)
printf(" таких слів немає\n");
return found;
}
/*------------------------------------------------------------------------------
cmdDeletePenultimateVowel — видалити всі слова, передостання літера яких
голосна.
Видалення виконується ущільненням масиву: слова, що лишаються, послідовно
переписуються на початок, після чого кількість слів зменшується.
Повертає : кількість видалених слів.
Локальні змінні:
kept — кількість слів, що лишилися;
removed — кількість видалених слів.
------------------------------------------------------------------------------*/
int cmdDeletePenultimateVowel()
{
int kept = 0, removed = 0;
printf("\nВидалення слів, передостання літера яких голосна:\n");
for (int i = 0; i < g_count; ++i) {
bool found = false;
const unsigned code = penultimateLetter(g_words[i], &found);
if (found && isVowelCode(code)) {
printf(" видалено: %s\n", g_words[i]);
++removed;
continue;
}
if (!found)
printf(" збережено: %s (літер менше двох, передостанньої немає)\n",
g_words[i]);
if (kept != i)
strcpy(g_words[kept], g_words[i]);
++kept;
}
g_count = kept;
if (removed == 0)
printf(" жодного слова не видалено\n");
return removed;
}
/*------------------------------------------------------------------------------
readInt — прочитати ціле число із заданого діапазону.
Параметри: prompt [вхідний], value [вихідний], low, high [вхідні].
Повертає : true — число прочитано; false — вхідні дані вичерпано.
------------------------------------------------------------------------------*/
bool readInt(const char *prompt, int *value, int low, int high)
{
for (;;) {
printf("%s", prompt);
const int scanned = scanf("%d", value);
if (scanned == EOF)
return false;
if (scanned == 1 && *value >= low && *value <= high) {
int c;
/* залишок рядка */
while ((c = getchar()) != '\n' && c != EOF) {
}
return true;
}
if (scanned != 1) {
int c;
/* очищення буфера */
while ((c = getchar()) != '\n' && c != EOF) {
}
}
printf("Помилка: потрібне ціле число від %d до %d.\n", low, high);
}
}
/*------------------------------------------------------------------------------
Головна функція. Читає рядок, розбиває його на слова та виконує команди меню.
Локальні змінні:
line — вхідний рядок;
choice — обраний пункт меню;
limit — гранична довжина слова для другої команди.
------------------------------------------------------------------------------*/
int main()
{
printf("Лабораторна робота №9, завдання 1 (варіант 19)\n");
printf("Виконав: студент групи ІПЗ-11 Одарчук Олексій\n");
printf("Обробка рядка слів\n\n");
printf("Слова відділяються пропусками, комами та крапками.\n");
printf("Уведіть рядок: ");
char line[MAX_LINE];
if (fgets(line, MAX_LINE, stdin) == NULL) {
printf("\nВхідні дані вичерпано.\n");
return 1;
}
if (strchr(line, '\n') == NULL) {
/* Рядок довший за буфер: зайві символи відкидаються. */
int c;
while ((c = getchar()) != '\n' && c != EOF) {
}
}
g_count = splitIntoWords(line);
if (g_count == 0) {
printf("\nУ введеному рядку немає жодного слова.\n");
return 2;
}
printWords("Вхідний список слів");
for (;;) {
printf("\n============================================================\n");
printf("Меню команд:\n");
printf(
" 1 - підрахувати слова з однаковою кількістю голосних і приголосних\n");
printf(" 2 - вивести слова, довжина яких менша заданої\n");
printf(" 3 - видалити слова, передостання літера яких голосна\n");
printf(" 4 - вивести поточний список слів\n");
printf(" 5 - вихід\n");
int choice = 0;
if (!readInt("Оберіть команду (1..5): ", &choice, 1, 5)) {
printf("\nВхідні дані вичерпано. Завершення роботи.\n");
break;
}
if (choice == 1) {
cmdCountBalanced();
} else if (choice == 2) {
int limit = 0;
if (!readInt("Уведіть граничну довжину слова: ", &limit, 1, MAX_WORD))
break;
cmdShorterThan(limit);
} else if (choice == 3) {
const int removed = cmdDeletePenultimateVowel();
printf("Видалено слів: %d\n", removed);
printWords("Список після видалення");
} else if (choice == 4) {
printWords("Поточний список слів");
} else {
printf("\nЗавершення роботи.\n");
break;
}
}
return 0;
}
Завдання 2 — task2.c
/*==============================================================================
Лабораторна робота №9. Завдання 2. Варіант 19.
Тема: обробка текстів, поданих масивами рядків.
Умова (таблиця 9.2, завдання 19.2): увести з клавіатури декілька рядків
символів. У кожному рядку записаний арифметичний або логічний вираз
в інфіксній формі (звичайній). На екран вивести вираз у постфіксній формі.
У постфіксній формі символ операції записується справа від операндів,
дужки не застосовуються. Наприклад, вираз (a+b)/c, записаний в інфіксній
формі, у постфіксній формі матиме вигляд: a b + c /.
Контрольний тест з умови варіанта:
уведені рядки: (a + b) / (c - d)
(2*a - 3*d)*c + 2*b
отримані рядки: a b + c d - /
2 a * 3 d * - c * 2 b * +
ОБМЕЖЕННЯ УМОВИ: забороняється використовувати STL, методи класу string,
ітератори, контейнери. Дозволено використовувати функції заголовних файлів
string.h, ctype.h, stdlib.h.
Виконав: Одарчук Олексій, КНУ імені Тараса Шевченка, ФІТ, група ІПЗ-11.
Компілятор: gcc -std=c17
==============================================================================*/
#include <stdio.h>
#include <stdbool.h>
#include <string.h>
#include <ctype.h>
/* Обмеження на розміри даних. */
const int MAX_LINE = 256; /* довжина одного виразу */
const int MAX_LINES = 32; /* кількість виразів */
const int MAX_STACK = 256; /* глибина стеку операцій */
/*------------------------------------------------------------------------------
precedence — пріоритет операції.
Що більше значення, то раніше виконується операція. Прийнято звичайні
математичні пріоритети, доповнені логічними операціями (умова варіанта
припускає й логічні вирази):
4 унарне заперечення !
3 множення, ділення, остача * / %
2 додавання, віднімання + -
1 порівняння < >
0 логічні І та АБО & |
Параметри: op [вхідний] — символ операції.
Повертає : пріоритет операції або -1, якщо символ операцією не є.
------------------------------------------------------------------------------*/
int precedence(char op)
{
switch (op) {
case '!':
return 4;
case '*':
case '/':
case '%':
return 3;
case '+':
case '-':
return 2;
case '<':
case '>':
return 1;
case '&':
case '|':
return 0;
default:
return -1;
}
}
/*------------------------------------------------------------------------------
isOperator — чи є символ знаком операції.
Параметри: c [вхідний] — символ.
Повертає : true — символ є операцією.
------------------------------------------------------------------------------*/
bool isOperator(char c)
{
return precedence(c) >= 0;
}
/*------------------------------------------------------------------------------
isOperandChar — чи може символ входити до операнда.
Операндом вважається послідовність літер, цифр, символів підкреслення
і крапки: це охоплює як імена змінних (a, b, x1), так і числові сталі
(2, 35, 3.5).
Параметри: c [вхідний] — символ.
Повертає : true — символ належить операнду.
------------------------------------------------------------------------------*/
bool isOperandChar(char c)
{
return isalnum((unsigned char)c) || c == '_' || c == '.';
}
/*------------------------------------------------------------------------------
normalizeMinus — замінити в рядку знаки «–» (тире) та «−» (мінус) на '-'.
Контрольний тест в умові варіанта записано з типографським тире
«(c – d)». У кодуванні UTF-8 тире U+2013 — це три байти E2 80 93,
знак мінус U+2212 — E2 88 92. Щоб вираз, скопійований з тексту умови,
розбирався так само, як набраний з клавіатури, ці знаки замінюються
звичайним дефісом-мінусом. Рядок при цьому лише коротшає.
Параметри: s [вхідний/вихідний] — рядок з виразом.
Локальні змінні:
read, write — позиції читання та запису в рядку;
b — байти рядка, починаючи з позиції читання;
dash — чи стоїть на позиції читання тире або знак мінус.
------------------------------------------------------------------------------*/
void normalizeMinus(char *s)
{
int write = 0;
for (int read = 0; s[read] != '\0'; ++write) {
const unsigned char *b = (const unsigned char *)s + read;
/* Байти порівнюються по черзі: на нульовому байті кінця рядка умова
стає хибною, і наступні байти вже не читаються. */
const bool dash = b[0] == 0xE2 && ((b[1] == 0x80 && b[2] == 0x93) ||
(b[1] == 0x88 && b[2] == 0x92));
if (dash) {
s[write] = '-';
read += 3;
} else {
s[write] = s[read];
++read;
}
}
s[write] = '\0';
}
/*------------------------------------------------------------------------------
infixToPostfix — перетворити вираз з інфіксної форми в постфіксну.
Алгоритм сортувальної станції (алгоритм Дейкстри). Вираз переглядається
зліва направо, використовується стек знаків операцій:
- операнд одразу дописується до вихідного рядка;
- відкривна дужка заноситься до стеку;
- закривна дужка виштовхує зі стеку всі операції до відкривної дужки,
сама пара дужок у результат не потрапляє;
- знак операції виштовхує зі стеку всі операції з не меншим пріоритетом
(для лівоасоціативних операцій), після чого заноситься до стеку;
- після перегляду виразу зі стеку виштовхуються всі операції, що лишилися.
Саме тому постфіксна форма не потребує дужок: порядок операцій у ній
задається взаємним розташуванням знаків.
Унарне заперечення ! стоїть перед операндом, тому заноситься до стеку
без виштовхування інших операцій і виводиться після свого операнда.
Паралельно перевіряється порядок лексем: ознака expectOperand показує,
що зараз очікується — операнд (або '(' чи '!') чи знак бінарної операції
(або ')'). Так виявляються пропущені операнди та знаки операцій.
Параметри:
infix [вхідний] — вираз в інфіксній формі;
postfix [вихідний] — буфер для виразу в постфіксній формі;
error [вихідний] — адреса рядка-повідомлення про помилку;
заповнюється лише при поверненні false.
Повертає : true — перетворення виконано; false — вираз некоректний.
Локальні змінні:
stack — стек знаків операцій та дужок;
top — індекс вершини стеку (-1 — стек порожній);
out — поточна позиція запису у вихідному рядку;
i — поточна позиція перегляду вхідного рядка;
expectOperand — чи очікується зараз операнд.
------------------------------------------------------------------------------*/
bool infixToPostfix(const char *infix, char *postfix, const char **error)
{
char stack[MAX_STACK];
int top = -1;
int out = 0;
int i = 0;
bool expectOperand = true;
while (infix[i] != '\0') {
const char c = infix[i];
/* Пропуски у вхідному виразі ігноруються. */
if (isspace((unsigned char)c)) {
++i;
continue;
}
/* Операнд: переписується цілком, як одна лексема. */
if (isOperandChar(c)) {
if (!expectOperand) {
*error = "пропущено знак операції між операндами";
return false;
}
while (infix[i] != '\0' && isOperandChar(infix[i]))
postfix[out++] = infix[i++];
postfix[out++] = ' ';
expectOperand = false;
continue;
}
if (c == '(' || c == '!') {
if (!expectOperand) {
if (c == '(')
*error = "пропущено знак операції перед дужкою";
else
*error = "заперечення ! має стояти перед операндом";
return false;
}
if (top + 1 >= MAX_STACK) {
*error = "переповнення стеку: вираз занадто складний";
return false;
}
stack[++top] = c;
++i;
continue;
}
if (c == ')') {
if (expectOperand) {
*error = "пропущено операнд перед закривною дужкою";
return false;
}
while (top >= 0 && stack[top] != '(') {
postfix[out++] = stack[top--];
postfix[out++] = ' ';
}
if (top < 0) {
*error = "зайва закривна дужка";
return false;
}
--top; /* вилучити '(' зі стеку */
++i;
continue;
}
if (isOperator(c)) {
if (expectOperand) {
*error = "пропущено операнд перед знаком операції";
return false;
}
/* Для лівоасоціативних операцій виштовхуються операції
з не меншим пріоритетом. */
while (top >= 0 && stack[top] != '(' &&
precedence(stack[top]) >= precedence(c)) {
postfix[out++] = stack[top--];
postfix[out++] = ' ';
}
if (top + 1 >= MAX_STACK) {
*error = "переповнення стеку: вираз занадто складний";
return false;
}
stack[++top] = c;
++i;
expectOperand = true;
continue;
}
*error = "неприпустимий символ у виразі";
return false;
}
if (expectOperand) {
if (out == 0 && top < 0)
*error = "порожній вираз";
else
*error = "вираз закінчується без операнда";
return false;
}
/* Виштовхнути операції, що лишилися у стеку. */
while (top >= 0) {
if (stack[top] == '(') {
*error = "не вистачає закривної дужки";
return false;
}
postfix[out++] = stack[top--];
postfix[out++] = ' ';
}
/* Прибрати завершальний пропуск. */
if (out > 0 && postfix[out - 1] == ' ')
--out;
postfix[out] = '\0';
return true;
}
/*------------------------------------------------------------------------------
Головна функція. Читає кількість виразів та самі вирази, перетворює кожен
у постфіксну форму й виводить результати.
Локальні змінні:
lines — масив рядків з виразами в інфіксній формі;
count — кількість введених виразів;
postfix — буфер для результату перетворення;
error — повідомлення про помилку розбору.
------------------------------------------------------------------------------*/
int main()
{
printf("Лабораторна робота №9, завдання 2 (варіант 19)\n");
printf("Виконав: студент групи ІПЗ-11 Одарчук Олексій\n");
printf("Перетворення виразу з інфіксної форми в постфіксну\n\n");
printf("Припустимі операції: ! * / %% + - < > & |\n");
printf("Операнди — імена змінних та числа.\n\n");
int count = 0;
printf("Уведіть кількість виразів (1..%d): ", MAX_LINES);
if (scanf("%d", &count) != 1 || count < 1 || count > MAX_LINES) {
printf("\nНекоректна кількість виразів.\n");
return 1;
}
/* Прибрати залишок рядка після числа, щоб fgets читав саме вирази. */
int c;
/* залишок рядка */
while ((c = getchar()) != '\n' && c != EOF) {
}
char lines[MAX_LINES][MAX_LINE];
printf("Уведіть вирази по одному в рядку (усього %d):\n", count);
for (int i = 0; i < count; ++i) {
printf(" вираз %d: ", i + 1);
if (fgets(lines[i], MAX_LINE, stdin) == NULL) {
printf("\nВхідні дані вичерпано.\n");
return 1;
}
/* Прибрати символ переведення рядка, який лишає fgets. */
const size_t length = strlen(lines[i]);
if (length > 0 && lines[i][length - 1] == '\n') {
lines[i][length - 1] = '\0';
} else {
/* Рядок довший за буфер: зайві символи відкидаються. */
int c;
while ((c = getchar()) != '\n' && c != EOF) {
}
}
}
printf("\n============================================================\n");
printf("Результати перетворення\n\n");
for (int i = 0; i < count; ++i) {
char postfix[MAX_LINE * 2];
const char *error = "";
normalizeMinus(lines[i]);
printf(" Інфіксна форма: %s\n", lines[i]);
if (infixToPostfix(lines[i], postfix, &error))
printf(" Постфіксна форма: %s\n\n", postfix);
else
printf(" Помилка: %s\n\n", error);
}
return 0;
}
6. Результати виконання роботи
Компіляція: make (gcc -std=c17, прапорці
-Wall -Wextra -pedantic -O2). Попереджень компілятора немає.
Нижче наведено екранні копії повних прогонів програм: кожна починається з запуску програми, містить усе введення з клавіатури й увесь вивід до завершення роботи. Прогін, що не вміщується на один екран, подано кількома послідовними частинами. Протоколи всіх прогонів, зокрема додаткових наборів вхідних даних, винесено окремими файлами за посиланнями.
Повний протокол виконання (task1.txt) — повний протокол, 213 рядків
Повний протокол виконання (task2.txt) — повний протокол, 133 рядків
7. Аналіз достовірності результатів
Достовірність результатів перевірено контрольним тестом з умови варіанта та ручним розбором контрольних рядків. Для кожної контрольної величини поруч із розрахунком наведено результат програми.
Завдання 1. Контрольний рядок українською
Уведено рядок: мова, програма. код тест дім і — розділові символи навмисно
різні (кома, крапка, пропуск).
| Слово | Літер (ручний підрахунок) | Голосні | Приголосні | Передостання літера | Результат програми |
|---|---|---|---|---|---|
| мова | 4 | о, а — 2 | м, в — 2 | в — приголосна | довжина 4, голосних 2, приголосних 2; збережено |
| програма | 8 | о, а, а — 3 | п, р, г, р, м — 5 | м — приголосна | довжина 8, голосних 3, приголосних 5; збережено |
| код | 3 | о — 1 | к, д — 2 | о — голосна | довжина 3; видалено |
| тест | 4 | е — 1 | т, с, т — 3 | с — приголосна | довжина 4, голосних 1, приголосних 3; збережено |
| дім | 3 | і — 1 | д, м — 2 | і — голосна | довжина 3; видалено |
| і | 1 | і — 1 | 0 | літер менше двох | збережено з поясненням |
Результати команд збігаються з ручним розбором:
- слів з однаковою кількістю голосних і приголосних — 1 («мова»);
- слів, коротших за 4 символи — 3 («код», «дім», «і»);
- видалено слів — 2 («код», «дім»).
Ключова перевірка тут — довжини слів. Побайтово («мова» — 8 байтів, «і» — 2 байти) відповіді на другу команду були б зовсім іншими. Отриманий результат підтверджує, що декодування UTF-8 працює правильно. Окремо перевірено літеру і, яка в Unicode лежить поза основним кириличним блоком: вона коректно розпізнана як голосна, через що слово «дім» видалено.
Додатково перевірено рядок англійською (латиниця обробляється тим самим кодом) та рядок з
кількома підряд розділовими символами (один,,, два...три, чотири) — порожніх
слів не утворюється: кілька розділових символів підряд діють як один роздільник.
Завдання 2. Контрольний тест з умови варіанта
| Інфіксна форма | Очікувано за умовою | Результат програми | Збіг |
|---|---|---|---|
| (a + b) / (c − d) | a b + c d − / | a b + c d - / | так |
| (2*a − 3*d)*c + 2*b | 2 a * 3 d * − c * 2 b * + | 2 a * 3 d * - c * 2 b * + | так |
| (a+b)/c — приклад із тексту умови | a b + c / | a b + c / | так |
Рядки контрольного тесту вставлено у програму в тому вигляді, як їх записано в умові (з тире «–»), і обидва результати відтворено символ у символ; тире у виразі програма розпізнала як знак віднімання.
Завдання 2. Перевірка пріоритетів та помилкових виразів
| Вираз | Ручний розбір | Результат програми |
|---|---|---|
| a + b * c − d | множення виконується першим: a b c * + d − | a b c * + d - |
| a * (b + c) * d | дужки змінюють порядок: a b c + * d * | a b c + * d * |
| x > y & z < w | порівняння пріоритетніші за логічне І: x y > z w < & | x y > z w < & |
| (a + b | не вистачає закривної дужки | повідомлення «не вистачає закривної дужки» |
| a + b) | зайва закривна дужка | повідомлення «зайва закривна дужка» |
| a # b | неприпустимий символ | повідомлення «неприпустимий символ у виразі» |
Перші три рядки перевіряють саме те, заради чого потрібна постфіксна форма: порядок операцій, заданий пріоритетами й дужками в інфіксному записі, у постфіксному відтворюється взаємним розташуванням знаків без жодних дужок. Останні три підтверджують, що вирази з незбалансованими дужками чи неприпустимими символами не призводять до аварійного завершення — програма називає конкретну причину.
Завдання 2. Пропущені операнди, знаки операцій і унарне заперечення
| Вираз | Ручний розбір | Результат програми |
|---|---|---|
| a + * b | після знака + очікується операнд, а стоїть * | повідомлення «пропущено операнд перед знаком операції» |
| a b | між двома операндами немає знака операції | повідомлення «пропущено знак операції між операндами» |
| a + | після знака + вираз закінчився | повідомлення «вираз закінчується без операнда» |
| () | у дужках немає операнда | повідомлення «пропущено операнд перед закривною дужкою» |
| !a & b | заперечення стосується лише a: a ! b & | a ! b & |
| !!a | подвійне заперечення: a ! ! | a ! ! |
| !(a | b) | заперечення всієї дужки: a b | ! | a b | ! |
Некоректна послідовність лексем не дає хибного результату: програма зупиняє розбір і повідомляє, чого саме бракує. Унарне заперечення в усіх трьох випадках записано одразу після свого операнда, як і має бути в постфіксній формі.
8. Висновки
- Опрацьовано подання рядків у мові C та бібліотечні функції string.h: strtok, strcpy, strncpy, strchr, strlen.
- Виявлено й розв'язано принципову проблему: функції ctype.h працюють побайтово і непридатні для тексту в UTF-8, де українська літера займає два байти. Реалізовано власне декодування UTF-8 та класифікацію літер за кодовими позиціями Unicode.
- Враховано, що українські літери є, і, ї, ґ розташовані в Unicode поза основним кириличним блоком і потребують окремої перевірки — це підтверджено тестом зі словом «дім».
- Враховано особливості функції strtok: вона змінює вхідний рядок і зберігає стан між викликами, тому розбір виконується над копією.
- Реалізовано всі три команди меню завдання 1; крайній випадок слова з однієї літери оброблено явно, з поясненням для користувача.
- Реалізовано алгоритм сортувальної станції для перетворення інфіксного виразу в постфіксний; обидва рядки контрольного тесту з умови варіанта відтворено точно.
- Таблицю пріоритетів доповнено логічними операціями, оскільки умова припускає й логічні вирази.
- Передбачено діагностику некоректних виразів: незбалансовані дужки, неприпустимі символи, пропущені операнди та знаки операцій виявляються із зазначенням конкретної причини.
- Вирази можна вставляти безпосередньо з тексту умови: типографське тире «–» та знак мінус «−» розпізнаються як знак віднімання.
- Дотримано обмежень умови: STL, клас string та ітератори не використовуються.
- Обидва завдання варіанта виконано в повному обсязі.