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

{

Поки СТЕК(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). Це випливає з таких властивостей алгоритму:

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

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

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

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

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

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

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

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

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

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

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

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

Не можна однозначно сказати який з цих підходів є кращим. Кожен з них має свою сферу застосування. У таких відомих математичних пакетах як MathCad, Mathematica, Derive та інших застосовують інтерпретативний підхід, оскільки користувачів найчастіше цікавить отримання одиничного результату. Зате при обчисленнях в пакетах математичного моделювання кожна зайва операція в циклі обробки моделі значно збільшує час, необхідний для розрахунків, тому тут найчастіше звертаються до компіляції виразів.

§2. Перевірка правильності виразів.



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

Цілком очевидно, що ті обмеження, які ми накладали раніше на арифметичні вирази є дуже жорсткими і для практичних обчислень їх потрібно зняти. Тому надалі вважаємо наступне:

змінні та константи в арифметичному виразі можуть позначатися не тільки великими буквами латинського алфавіту, але і довільним ідентифікатором (Ідентифікатор - послідовність букв і цифр, яка починається з букви і не містить пробілів всередині);