Оптимальні програми

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

Читаємо префіксний запис виразу посимвольно (він обов’язково починається знаком операції), записуємо знак операції у вершину, зчитуємо два наступні символи і якщо вони є операндами (змінними чи константами) то для даної вершини будуємо дві дочірні вершини, записуючи в ліву перший операнд, а в праву - другий; якщо якийсь з двох символів є не операндом а операцією, то для цієї дочірньої вершини рекурсивно застосовуємо це ж саме правило.

Префіксна форма запису є вдалою в тому розумінні, що нам не потрібно використовувати дужки і вводити пріоритет операцій, хоч ми все рівно можемо однозначно обчислити вираз.Більш звична для сприйняття форма арифметичного виразу А+В називається інфіксною формою, вона отримується при проходженні дерева в зворотному порядку, який можна позначити (Л)(В)(П). На жаль лінійна послідовність символів, яка отримується при цьому не дає змоги однозначно відтворити початкове дерево виразу, тому при обчисленні виразу в інфіксній формі можливі двозначності. По суті, розглянуте на початку параграфу означення арифметичних виразів вводить вирази саме в інфіксній формі, і для подолання проблеми неоднозначності тут застосовуються дужки.

Постфіксна форма арифметичного виразу – в якій знак операції слідує за операндами, наприклад АВ+, - отримується при кінцевому порядку (Л)(П)(В) проходження вершин дерева. Ця форма запису найчастіше використовується для внутрішнього представлення виразів в комп’ютерних програмах, оскільки вона, так як і інфіксна форма, дозволяє повністю однозначно обчислити значення виразу, не використовуючи дужок і пріоритет операцій, а також є зручною для реалізації.

Для прикладу можна розглянути дерево на малюнку 1. Щоб пройти це дерево в прямому порядку потрібно почати з першої кореневої вершини (відміченої +), пройти в прямому порядку спочатку ліве піддерево з коренем ( * ), а потім праве з коренем ( / ). Для проходження кожного піддерева знову застосовуємо те ж саме правило – корінь, ліве піддерево, праве піддерево. Таким чином, проходження всього дерева в прямому порядку породжує послідовність

+ * - A B C / D ^ E F(префіксна)

Проходження цього дерева в оберненому і кінцевому порядках відповідно породжує наступні послідовності

A – B * C + D / E ^ F (інфіксна)

A B – C * D E F ^ / + (постфіксна)

Потрібно відмітити, що в усіх трьох виразах порядок входження змінних співпадає, міняється лише порядок знаків операцій.

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

Опишемо алгоритм [1], який дозволяє обчислити значення арифметичного виразу в постфіксній формі.

Алгоритм POSTFIX.

Обчислити арифметичний вираз в постфіксній формі; вираз задано послідовністю S(1) S(2) . . . S(N), N  1, де S(J) – або буква (операнд, змінна, константа), або один зі знаків +, -, *, /, ^ (тобто двохмісна арифметична операція)

Крок 0. j:=0