Більш звична для сприйняття форма арифметичного виразу А+В називається інфіксною формою, вона отримується при проходженні дерева в зворотному порядку, який можна позначити (Л)(В)(П). На жаль лінійна послідовність символів, яка отримується при цьому не дає змоги однозначно відтворити початкове дерево виразу, тому при обчисленні виразу в інфіксній формі можливі двозначності. По суті, розглянуте на початку параграфу означення арифметичних виразів вводить вирази саме в інфіксній формі, і для подолання проблеми неоднозначності тут застосовуються дужки.
Постфіксна форма арифметичного виразу – в якій знак операції слідує за операндами, наприклад АВ+, - отримується при кінцевому порядку (Л)(П)(В) проходження вершин дерева. Ця форма запису найчастіше використовується для внутрішнього представлення виразів в комп’ютерних програмах, оскільки вона, так як і інфіксна форма, дозволяє повністю однозначно обчислити значення виразу, не використовуючи дужок і пріоритет операцій, а також є зручною для реалізації.
Для прикладу можна розглянути дерево на малюнку 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) виконується не більше ніж деяке постійне число операцій.
Потрібно відмітити деякі властивості алгоритму POSTFIX:
1. Алгоритм вважає, що вхідна послідовність є правильним постфіксним виразом; відсутні тести, що гарантують правильність вхідної послідовності.
2. Алгоритм розроблено для обробки виразів, в яких операнди не повинні складатися з кількох букв або цифр.
3. Недопустимою є поява у виразі числових констант чи звернень до функцій.
4. У виразі не повинно бути одномісних операцій, наприклад -А або +А-В.
5. Алгоритм не ініціалізує стек нулями і не заповнює його нулями після того, як значення були використані.
Має місце наступне твердження:
Твердження 2. Арифметичний вираз, записаний у префіксній формі, може бути обчислений алгоритмом POSTFIX, якщо цей вираз переписати ззаду-наперед, а у алгоритмі виконувати операції, міняючи місцями операнди відносно знаку операції (для некомутативних операцій).
Доведення даного твердження можна отримати за індукцією по кількості вершин дерева виразу. Якщо дерево містить одну вершину (операнд), то нічого обчислювати взагалі не потрібно і твердження виконується. Якщо дерево містить три вершини
то префіксна форма запису виразу буде " –AB ". Якщо її переписати ззаду-наперед " ВА– " і застосувати модифікований алгоритм POSTFIX (міняючи місцями операнди відносно операції), то отримаємо правильний результат (значення А-В), отже твердження виконується.
Припустимо, що твердження виконується для всіх виразів, дерево яких містить не більше n вершин. Тоді вираз з n+1 - вершинним деревом, згідно означення арифметичного виразу, складається з двох менших підвиразів (піддерев), і має вигляд "Оперція1 Вираз1 Вираз2" у префіксній формі. Переписавши його ззаду-наперед "Вираз2 Вираз1 Операція1" і припускаючи, що Вираз1 та Вираз2 обчислюються модифікованим алгоритмом POSTFIX правильно, ми отримаємо на виході правильний результат, тобто "Значення виразу1" Операція1 "Значення виразу2". Твердження доведено.
Отже ми бачимо, що арифметичний вираз дуже легко обчислюється, як тільки його переведено в постфіксну або префіксну форму. Але в більшості мов програмування вимагається запис арифметичних виразів в інфіксній формі. Наступний алгоритм розроблено для переведення виразів з інфіксної форми в постфіксну [1]. Він базується на наступному правилі пріоритетів:
| Символ | Пріоритет |
| ( , ) | 0 |
| + , - | 1 |
| * , / | 2 |
| ^ | 3 |
Таблиця 1.
Хоч насправді пріоритет дужок є найвищим, ми для даного алгоритму штучно знижуємо його, для простішої обробки послідовності у стекові. Але хоч і неявно, а все ж верховенство пріоритету дужок проявляє себе в тому, що для їх обробки використовуються окремі процедури.
Алгоритм працює, читаючи символи інфіксного виразу зліва направо. Всі операнди (змінні) попадають на вхід по мірі прочитування виразу; інші символи поміщаються на стек і або видаляються, або поступають на вихід пізніше в відповідності з наведеним вище правилом пріоритетів.
Алгоритм ITP (інфіксна в постфіксну).
Перевести інфіксний вираз S(1) S(2) . . . S(N), N³1, в постфіксну форму. S(i) - або буква (тобто операнд, або змінна), ліва або права дужка, або знак операції (тобто один із символів +, -, *, /, ^ ). Алгоритм використовує стек і пріоритетну функцію Р, згідно якої "e", "(", ")" мають пріоритет 0, Р(+)=Р(-)=1, Р(*)=Р(/)=2, Р(^)=3.
Крок 0: СТЕК(1):=e; j:=1;
Крок 1: Для і від 1 до N виконувати: { Кроки 2 - 5 }
Крок 2: Якщо S(i) - буква то { Вивести S(i) }
Крок 3: Якщо S(i)="(" то { j:=j+1; CTEK(j):=S(i) }
Крок 4: Якщо S(i)=")" то
{
Поки СТЕК(j)¹"(" виконувати:{ Вивести СТЕК(j); j:=j-1; }
j:=j-1;
}
Крок 5: Якщо S(i) - знак операції то
{
Поки Р(S(i)) £ P(СТЕК(j)) виконувати: { Вивести СТЕК(j); j:=j-1; }
j:=j+1; СТЕК(j):=S(i);
}
Крок 6: Поки СТЕК(j)¹e виконувати: { Вивести СТЕК(j); j:=j-1; }
Стоп.
Складність алгоритму ITP виявляється О(N). Це випливає з таких властивостей алгоритму:
1. Один прохід виконується над N символами послідовності.
2. На стек може попасти найбільше N/2 символів (тобто операцій).
3. Всі символи, що залишаються на стекові, можуть бути виведені після закінчення перегляду послідовності не більше ніж за O(N) операцій.
4. Для обробки довільного символу в послідовності потрібно не більше постійного числа операцій.
Неважко переконатися в тому факті, що алгоритм ІТР можна використати і для переводу виразів з інфіксної форми в префіксну. Для цього потрібно:
Отримана послідовність якраз і буде префіксною формою запису виразу.
Розглянувши базові алгоритми роботи з виразами, звернемо увагу на іншу, більш прагматичну сторону обчислень. Зокрема потрібно з’ясувати в складі якого програмного пакету відбувається обчислення виразу, щоб мати змогу обрати більш ефективний метод. Розрізняють два принципово різні підходи до обчислення виразів - інтерпретативний і компілятивний.
Компілятивний підхід полягає в тому, що для даного виразу генерується окрема програма в машинних кодах, яка обчислює вираз при заданих значеннях змінних. Особливістю цього підходу є те, що спочатку затрачається багато машинних ресурсів для перевірки виразу, переведення його в зручну форму, генерації програми на мові низького рівня, але зате потім згенерована програма, вже будучи цілком самостійною, обчислює значення виразу з великою швидкістю. Такий підхід є просто незамінним у тому випадку, коли потрібно обчислити серію значень деякої формули на різних наборах вхідних даних.