Оптимальні програми обчислення виразів, Детальна інформація

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

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

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

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

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

Для прикладу можна розглянути дерево на малюнку 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

Крок 1. Для і від 1 до N виконувати [крок 2]. \\ переглядаємо вираз

Стоп. \\ значення виразу буде на вершині стеку

Крок 2. Якщо S(i) – операнд

тоді j:=j+1; СТЕК(j):=S(i)

інакше Т1:=СТЕК(j); Т2:=СТЕК(j-1);

Т3:=Т2 S(i) Т1; \\ виконуємо операцію

j:=j-1; СТЕК(j):=Т3; \\ результат заносимо в стек

Доведення правильності алгоритму POSTFIX можна отримати за індукцією по довжині N постфіксного виразу S(1) S(2) . . . S(N). Таке доведення залежить від індуктивного означення арифметичного виразу і від процесу трансляції арифметичного виразу з інфіксної форми в постфіксну.

Алгоритм POSTFIX правильно працює на постфіксних виразах довжини N=1 та N=3 (вважаємо, що не існує постфіксних виразів довжини N=2). Це безпосередньо перевіряється ручним обчисленням. Тому припустимо, що алгоритм POSTFIX правильно обчислює всі постфіксні вирази довжини не більше N.

Розглянемо довільний постфіксний вираз S(1) S(2) . . . S(N+1) довжини N+1. Нехай k – найменше ціле число, таке, що S(k) – операція. Тоді очевидно, що ця операція повинна бути виконана над S(k-1) і S(k-2), які є операндами. Взагалі кажучи, з того, що S(i) – операція, не обов’язково слідує, що S(i-1) та S(i-2) - операнди. Але через те, що S(k) – перша операція в послідовності, S(k-1) та S(k-2) повинні бути операндами. На кроці 2 алгоритм POSTFIX забирає зі стеку S(k-1) та S(k-2), обчислює T = S(k-1) S(k) S(k-2) і поміщає Т на стек так, ніби він є ще одним операндом.

В цей момент конфігурація стеку точно така, як була б у випадку, якщо б початковий постфіксний вираз був більш коротким: S(1) . . . S(k-3) T S(k+1) . . . S(N). Але оскільки значення такого зміненого виразу (можна показати, що це правильний постфіксний вираз) рівне значенню початкового виразу і оскільки за припущенням індукції алгоритм POSTFIX правильно працює на всіх виразах довжини не більше N, то можемо зробити висновок, що алгоритм POSTFIX правильно обчислює вихідний вираз.

Постфіксний вираз можна обчислити за допомогою стеку за O(N) операцій. Це випливає з того, що при перегляді кожного з N символів S(1), S(2), . . . , S(N) виконується не більше ніж деяке постійне число операцій.