/*============================================================================== Лабораторна робота №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 #include #include #include /* Обмеження на розміри даних. */ 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; }