Оптимальні програми
Крок 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, якщо цей вираз переписати ззаду-наперед, а у алгоритмі виконувати операції, міняючи місцями операнди відносно знаку операції (для некомутативних операцій).