Постфіксна форма запису операцій (зворотний польський запис)

Зворотний польський запис (ЗПЗ) - форма запису математичних виразів, у якій операнди розташовані перед знаками операцій. Відмінною рисою зворотної польської нотації є те, що всі аргументи (чи операнди) розташовані перед знаком операції. У загальному випадку запис має такий вигляд:

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

Наприклад, розглянемо обчислення виразу 7 2 3 * - (еквівалентний вираз в інфіксній нотації: 7-2*3).

Перший по порядку знак операції - "*", тому першою виконується операція множення над операндами 2 і 3 (вони стоять останніми перед знаком). Вираз при цьому перетвориться до вигляду 7 6 - (результат множення: 6, - заміняє трійку "2 3 *").
Другий знак операції - "-". Виконується операція віднімання над операндами 7 і 6.
Обчислення закінчене. Результат останньої операції дорівнює 1, це і є результат обчислення виразу.

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

Особливості ЗПЗ:

Порядок виконання операцій однозначно задається порядком проходження знаків операцій у виразі, тому відпадає необхідність використання дужок і введення пріоритетів і асоціативності операцій.
На відміну від інфіксного запису, неможливо використовувати ті самі знаки для запису унарних і бінарних операцій. Так, у інфіксному запису вираз 5 * (-3 + 8) використовує знак "мінус" як символ унарної операції (зміна знака числа), а вираз (10 - 15) * 3 застосовує цей же знак для позначення бінарної операції (віднімання). Конкретна операція визначається тим, у якій позиції знаходиться знак. Зворотний польський запис не дозволяє цього: запис 5 3 - 8 + * (умовний аналог першого виразу) буде інтерпретований як помилковий, оскільки неможливо визначити, що "мінус" після 5 і 3 позначає не віднімання; у результаті буде зроблена спроба обчислити спочатку 5 - 3, потім 2 + 8, після чого з’ясується, що для операції множення не вистачає операндів. Щоб усе-таки записати цей вираз, прийдеться або переформулювати його, або ввести для операції зміни знака окреме позначення, наприклад, "±": 5 3 ± 8 + *.
Так само, як і в інфіксній нотації, в ЗПЗ те саме обчислення може бути записане в декількох різних варіантах. Наприклад, вираз (10 - 15) * 3 в ЗПЗ можна записати як 10 15 - 3 *, а можна і як 3 10 15 - *.
Через відсутність дужок ЗПЗ коротший, ніж інфікс ний запис. За рахунок цього при обчисленнях на калькуляторах підвищується швидкість роботи оператора (зменшується кількість клавіш, що натискаються,), а в програмувальних пристроях скорочується обсяг тих частин програми, що описують обчислення.
Використання ЗПЗ дозволяє спростити процес розробки компіляторів.

Перетворення з інфіксної нотації в ЗПЗ

Едсгер Дейкстра розробив алгоритм для перетворення виразів з інфіксної нотації в ЗПЗ. Алгоритм одержав назву "сортувальна станція", за подібність його операцій із діями, які відбуваються на залізничних сортувальних станціях. Як і алгоритм обчислення ЗПЗ, алгоритм «сортувальної станції» базується на стеці. У перетворенні беруть участь дві текстові змінні: вхідний і вихідний рядки. У процесі перетворення використовується стек, що зберігає ще не додані до вихідного рядка оператори. Перетворююча програма читає вхідний рядок послідовно символ за символом (символ - це не обов'язково буква), виконує на кожнім кроці деякі дії в залежності від того, який символ був прочитаний.

Алгоритм

Поки є ще символи для читання:

Читаємо черговий символ.
Якщо символ є числом, то додаємо його до вихідного рядка.
Якщо символ є символом функції, то поміщаємо його в стек.
Якщо символ є відкриваючою дужкою, то поміщаємо його в стек.
Якщо символ є закриваючою дужкою:

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

Якщо символ є оператором ор, тоді:

1) поки...

... (якщо оператор ор асоційований, або ліво-асоційований) пріоритет ор менший або дорівнює пріоритету оператора, що знаходиться на вершині стеку...

... (якщо оператор ор право-асоційований) пріоритет ор менший, ніж пріоритет оператора, що знаходиться на вершині стеку...

... виштовхуємо верхні елементи стеку у вихідний рядок;

2) поміщаємо оператор ор у стек.

Коли вхідний рядок закінчився, виштовхнути всі символи зі стека у вихідний рядок. У стеці повинні залишитися тільки символи операторів; якщо це не так, значить у виразі порушений баланс дужок.

Приклад

Пріоритети:

^ високий

* / середній

+ - низький

Вхід: 3 + 4 * 2 / (1 - 5)^2

Читаємо "3"

Додаємо "3" до вихідного рядка

Вихід: 3

Читаємо "+"

Кладемо "+" у стек

Вихід: 3