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

Доведення даного твердження можна отримати за індукцією по кількості вершин дерева виразу. Якщо дерево містить одну вершину (операнд), то нічого обчислювати взагалі не потрібно і твердження виконується. Якщо дерево містить три вершини

то префіксна форма запису виразу буде " –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) - або буква (тобто операнд, або змінна), ліва або права дужка, або знак операції (тобто один із символів +, -, *, /, ^ ). Алгоритм використовує стек і пріоритетну функцію Р, згідно якої "", "(", ")" мають пріоритет 0, Р(+)=Р(-)=1, Р(*)=Р(/)=2, Р(^)=3.

Крок 0:СТЕК(1):=; 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)=")" то