іч рекурсивно викликаних процедур в даному випадку утворює дерево, прохідне в зворотному порядку.
.3 Синтаксичний аналіз арифметичних виразів
Задача синтаксичного аналізу полягає в тому, щоб за наявною рядку, що містить арифметичний вираз, і відомим значенням, що входять до неї змінних, обчислити значення виразу.
Процес обчислення арифметичних виразів можна представити у вигляді бінарного дерева. Дійсно, кожен з арифметичних операторів (+, -, *, /) вимагає двох операндів, які також будуть і арифметичними виразами і, відповідно можуть розглядатися як піддерева. Рис. 8 показує приклад дерева, відповідного висловом:
В
В
Рис. 8. Синтаксичне дерево, відповідне арифметичному вираженню (6). br/>
У такому дереві кінцевими вузлами завжди будуть змінні (тут x) або числові константи, а всі внутрішні вузли будуть містити арифметичні оператори. Щоб виконати оператор, треба спочатку обчислити його операнди. Таким чином, дерево на малюнку слід обходити в кінцевому порядку. Відповідна послідовність вузлів
В
називається зворотної польської записом арифметичного вираження.
При побудові синтаксичного дерева слід звернути увагу на таку особливість. Якщо є, наприклад, вираз
В
і операції додавання і віднімання ми будемо зчитувати зліва на право, то правильне синтаксичне дерево буде містити мінус замість плюса (рис. 9а). По суті, це дерево відповідає виразу Полегшити складання дерева можна, якщо аналізувати вираз (8) навпаки, справа наліво. У цьому випадку виходить дерево з рис. 9б, еквівалентну дереву 8а, але не вимагає заміни знаків. p> Аналогічно справа наліво потрібно аналізувати вирази, що містять оператори множення і ділення.
В
Рис. 9. Синтаксичні дерева для вираження a - b + c при читанні зліва направо (а) і справа наліво (б). br/>
.4 Швидкі сортування
Прості методи сортування кшталт методу вибору або методу бульбашки сортують масив з n елементів за O (n2) операцій. Однак за допомогою принципу В«розділяй і володарюйВ» вдається побудувати більш швидкі, що працюють за O (n log2 n) алгоритми. Суть цього принципу в тому, що рішення виходить шляхом рекурсивного поділу завдання на кілька прості підзадачі того ж типу до тих пір, поки вони не стануть елементарними. Наведемо як приклади кілька швидких алгоритмів такого роду. p> Алгоритм 1: В«ШвидкаВ» сортування (quicksort).
. Вибирається опорний елемент (наприклад, перший або випадковий). p>. Реорганізуємо масив так, щоб спочатку йшли елементи менші опорного, потім рівні йому, потім великі. Для цього досить пам'ятати, скільки було знайдено менших (m1) і великих (m2), ніж опорний і ставити черговий елемент на місце з індексом m1, а черговий більший на місце з індексом n-1-m2. p> Після виконання такої операції опорний елемент і рівні йому стоять на своєму місці, їх переставляти більше не доведеться. Між В«меншоюВ» і В«більшоїВ» частину масиву п...
