Математичні дерева. Польські вирази.

Однією з головних причин, що лежать в основі появи мов програмування високого рівня, з'явилися обчислювальні задачі, що вимагають великих об'ємів рутинних обчислень. Тому до мов програмування пред'являлися вимоги максимального наближення форми запису обчислень до природної мови математики.

Розглянемо зіставлення виразів (арифметичним, логічним тощо) дерев і побудова на цій основі різних форм запису виразів.

Приклад 4.1. Наступний арифметичний вираз потрібно подати у вигляді дерева:

.

Послідовність дій відтворено на рис. 4.1. Рамкою на ньому обведено дерево, яке відповідає заданому арифметичному виразу. Внутрішнім вершинам цього дерева відповідають символи операцій, а листкам – операнди.

Рис. 4.1 Подання виразу за допомогою дерева

Обійдемо це дерево, записуючи символи у вершинах у тому порядку, у якому вони зустрічаються в разі заданого способу обходу. Отримаємо такі три послідовності:

Ø у разі обходу в прямому порядку – префіксний (польський) запис

*+а/bc-d*ef;

Ø у разі обходу у внутрішньому порядку – інфіксний запис

а+b/с*d-e*f;

Ø у разі обходу в зворотному порядку – постфіксний (зворотний польський) запис

abс/+def*-*.

Зупинимось на інфіксній формі запису виразу. Без дужок вона неоднозначна: один запис може відповідати різним деревам. Наприклад, дереву, зображеному на рис. 4.2, у разі обходу зліва направо відповідає той самий вираз а + b / с * d - e * f, що й дереву на рис. 4.1 (у рамці), хоча на цих рисунках зображено різні дерева. Щоб уникнути неоднозначності інфіксної форми, використовують круглі дужки щоразу, коли зустрічають операцію. Повністю „одужкований" вираз, одержаний під час обходу дерева у внутрішньому порядку, називають інфіксною формою запису. Отже, для дерева з рис. 4.1 інфіксна форма така:

((а +(b / c))*(d -(e */))),

а для дерева, зображеного на рис. 4.2, інфіксна форма має такий вигляд:

(a +(((b /(c * d))- e)* f)).

Наведені міркування свідчать, що інфіксна форма запису виразів незручна. На практиці використовують префіксну та постфіксну форми, бо вони однозначно відповідають виразу й не потребують дужок. Ці форми запису називають польським записом (на честь польського математика й логіка Яна Лукасевича, українця за походженням).

Рис. 4.2. Подання виразу деревом

Приклад 4.2. Розглянемо логічний вираз . Послідовні етапи побудови відповідного бінарного дерева зображено на рис. 4.3.

Рис. 4.3. Побудова математичного дерева

Форми запису виразу наступні:

Ø інфіксна форма запису: (((p Ù q)) ~ ((p)Ú (q)));

Ø польський запис: ~ Ù pq Ú pq;

Ø зворотний польський запис: pq Ù рq Ú ~.

Правило 4.1. Для обчислення значення виразу в польському записі його проглядають справа наліво та знаходять два операнди разом зі знаком операції перед ними. Ці операнди та знак операції вилучають із запису, виконують операцію, а її результат записують на місце вилучених символів.

Приклад 4.3. Обчислимо значення виразу в польському записі (стрілка означає піднесення до степеня)

+–*235/­234.

За сформульованим правилом 4.1 виділимо ­23, ці символи вилучимо й обчислимо 2­3=8; результат запишемо на місце вилучених символів:

+–*235/84.

Продовжимо обчислення. Динаміку процесу відображено в табл. 4.1.

Таблиця 4.1

Правило 4.2. Для обчислення значення виразу в зворотному польському записі його проглядають зліва направо та виділяють два операнди разом зі знаком операції після них. Ці операнди та знак операції вилучають із запису, виконують операцію, а її результат записують на місце вилучених символів.

Приклад 4.4. Обчислимо значення виразу в зворотному польському записі

723*–4­93/+.

Динаміку обчислень відображено в табл. 4.2.

Таблиця 4.2