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

{

Поки СТЕК(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) виконувати: { Вивести СТЕК(j); j:=j-1; }

Стоп.

Складність алгоритму ITP виявляється О(N). Це випливає з таких властивостей алгоритму:

1.Один прохід виконується над N символами послідовності.

2.На стек може попасти найбільше N/2 символів (тобто операцій).

3.Всі символи, що залишаються на стекові, можуть бути виведені після закінчення перегляду послідовності не більше ніж за O(N) операцій.

4.Для обробки довільного символу в послідовності потрібно не більше постійного числа операцій.

Неважко переконатися в тому факті, що алгоритм ІТР можна використати і для переводу виразів з інфіксної форми в префіксну. Для цього потрібно:

•вираз в інфіксній формі переписати посимвольно ззаду-наперед;

•застосувати до цієї послідовності алгоритм ІТР;

•результат знову переписати ззаду-наперед.

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

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