Польський інверсний запис (ПОЛІЗ, англ.Reverse Polish Notation (RPN), дос. «зворотня польська нотація», зворотний бездужковий запис, постфіксна нотація) — форма запису математичних виразів, в якій знаки операцій розташовано після операндів. Розташування знаків операцій перед операндами використовує польська нотація.
Історія розробки
Зворотний польський запис розробив австралійський філософ і фахівець у галузі теорії обчислювальних машин Чарлз Гемблін[en] у середині 1950-х років на основі польської нотації, яку запропонував 1920 року польський математик Ян Лукашевич. Роботу Гембліна представлено на конференції в червні 1957 року, і видано в 1957 і 1962 роках.
Першими комп'ютерами, що підтримують зворотний польський запис були KDF9[en] від English Electric Company, який був випущений в 1963, і американський Burroughs B5000, випущений в тому ж 1963. Зворотна польська нотація застосовувалася в радянському інженерному калькуляторі Б3-19М, випущеному в 1976 році. Майже всі програмовані калькулятори в СРСР аж до кінця 1980-х років використовували ПОЛІЗ — він простіше реалізовувався і дозволяв обійтися в програмуванні обчислень меншим числом команд, порівняно зі звичайною алгебраїчною нотацією, адже обсяг програмної пам'яті в цих моделях завжди було критичним ресурсом.[1]
Загальний вигляд
У загальному вигляді запис виглядає так:
Запис набору операцій складається з послідовності операндів і знаків операцій. Операнди у виразі при письмовому записі розділяються пробілами.
Вираз читається зліва направо. Коли у виразі зустрічається знак операції, виконується відповідна операція над двома останніми перед ним операндами в порядку їх запису. Результат операції замінює у вираженні послідовність її операндів і її знак, після чого вираз обчислюється далі за тим же правилом.
Результатом обчислення виразу стає результат останньої обчисленої операції.[1]
Приклади
Вираз
Традиційна (інфіксна) нотація
Зворотна польська (постфіксна) нотація
a + b × c
a + b*c
a b c * +
(a + b) × (c + d)
(a + b) * (c + d)
a b + c d + *
(a + t) × (b × (a + c))(c + d)
(a + t) * (b * (a + c))^(c + d)
a t + b a c + * c d + ^ *
Застосування
Зворотний польський запис є зручним для застосування в обчислювальних пристроях. Наприклад, для обчислення виразу: a + b
слід виконати такі дії:
обчислити a
обчислити b
скласти результати (+)
Саме така послідовність і задається польським інверсним записом: a b +
Комп'ютерні програми зазвичай під час аналізу формул перетворюють їх на послідовність інструкцій у ПОЛІЗ, і саме в такому порядку вони виконуються.
На основі постфіксної нотації побудовано мову програмування Forth, також вона безпосередньо застосовується у PostScript.
Стековою машиною[en] називається алгоритм, який проводить обчислення за зворотною польською нотацією[джерело?]. Прикладом використання стекової машини є програма UNIXdc.
Існує велика кількість програмного забезпечення у вигляді калькуляторів з підтримкою ПОЛІЗ (у тому числі й емуляторів і симуляторівапаратних калькуляторів та мікрокалькуляторів) для різних платформ[7][8][9], зокрема:
Алгоритм для перетворення звичайного запису в бездужковий
Поки ще є символи для зчитування:
Читаємо наступний символ;
Якщо символ є числом або постфіксною функцією (наприклад, ! — факторіал), то додаємо до вихідного рядка;
Якщо символ є префіксною функцією (наприклад, sin — синус), поміщаємо його в стек;
Якщо символ є '(', поміщаємо його в стек;
Якщо символ є ')', то:
До тих пір, поки верхнім елементом стека не стане відкриваюча дужка, виштовхуємо елементи зі стека у вихідний рядок. При цьому відкриваюча дужка видаляється зі стека, але у вихідний рядок не додається. Якщо після цього кроку на вершині стека виявляється символ функції, виштовхуємо його у вихідний рядок. Якщо стек закінчився раніше, ніж ми зустріли відкриваючу дужку, це означає, що у виразі або неправильно поставлений розділовий знак, або неузгодженні дужки.
Якщо символ є бінарною операцією, тоді:
поки на вершині стека префіксна функція…
… АБО операція на вершині стека має більший пріоритет ніж o1
… АБО операція на вершині стека ліво-асоціативна з пріоритетом як у o1
… виштовхуємо верхній елемент стека у вихідний рядок;
поміщаємо операцію o1 у стек;
Коли вхідний рядок закінчився, виштовхуємо всі символи зі стека у вихідний рядок. У стеку повинні були залишитись тільки символи операцій; якщо це не так, значить у виразі неузгоджені дужки.
Приклад
Маємо рядок 3 + 4 * 2 / (1-5) ^ 2.
Переводимо його до польського запису:
Читаємо «3»
Додаємо «3» до виходу
Вихід: 3
Читаємо «+»
Вставляємо «+» в стек
Вихід: 3
Стек: +
Читаємо «4»
Додаємо «4» до виходу
Вихід: 3 4
Стек: +
