Польський інверсний запис

Зворо́тний по́льський за́пис (зворотний бездужковий запис, постфіксна нотація, польський інверсний запис (ПОЛІЗ), англ. RPN — Reverse Polish Notation) — форма запису математичних виразів, в якій знаки операцій розташовано після операндів. Розташування знаків операцій перед операндами використовує польська нотація.

Історія розробки ред.

Зворотний польський запис розробив австралійський філософ і фахівець у галузі теорії обчислювальних машин Чарлз Гемблін^[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] називається алгоритм, який проводить обчислення за зворотною польською нотацією^{[джерело?]}. Прикладом використання стекової машини є програма UNIX dc.

Калькулятори ред.

ПОЛІЗ здобув досить широке розповсюдження в інженерних мікрокалькуляторах та мікрокомп'ютерах. Зокрема, такі калькулятори виробляли фірми Hewlett-Packard (HP 9100A),^[2] Texas Instruments (програмно^[3]). Практично всі програмовані калькулятори, що вироблялися в СРСР (Б3-34, MK-52, MK-61 та інші) застосовували зворотну польську нотацію.

Створено кілька калькуляторів з підтримкою ПОЛІЗ та відкритим апаратним забезпеченням, наприклад OpenRPNCalc, кишеньковий інженерний калькулятор на базі мікропроцесора STMicroelectronics STM32 (модель STM32L476).^[4]^[5]

Алгоритм для обчислення значення виразу ред.

Для всіх символів виконуємо такі дії:

Якщо А_і число, то вкласти його у стек;
Якщо А_і оператор, то:
- Витягуємо зі стека два числа;
- Виконуємо дію із числами і результат вкладаємо в стек;
Якщо А_і є функцією то:
- Витягуємо зі стека одне число;
- Визначаємо значення функції із відповідним аргументом та поміщаємо результат у стек;
В кінці роботи в стеку знаходитиметься результат виразу.

Приклад ред.

Маємо вираз: 12 + 2 * ((3 * 4) + (10 / 5))

Вираз у польському інверсному записі: 12 2 3 4 * 10 5 / + * +
Порядок дій над ним буде такий:

Крок	Елемент	Стек
1	12	12
2	2	2 12
3	3	3 2 12
4	4	4 3 2 12
5	*	12 2 12
6	10	10 12 2 12
7	5	5 10 12 2 12
8	/	2 12 2 12
9	+	14 2 12
10	*	28 12
11	+	40

Алгоритм для перетворення звичайного запису в бездужковий ред.

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

Читаємо наступний символ;
Якщо символ є числом або постфіксною функцією (наприклад, ! — факторіал), то додаємо до вихідного рядка;
Якщо символ є префіксною функцією (наприклад, sin — синус), поміщаємо його в стек;
Якщо символ є '(', поміщаємо його в стек;
Якщо символ є ')', то:

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

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

1) поки на вершині стека префіксна функція…

… АБО операція на вершині стека має більший пріоритет ніж o1

… АБО операція на вершині стека ліво-асоціативна з пріоритетом як у o1

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

2) поміщаємо операцію o1 у стек;

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

Приклад ред.

Маємо рядок «3 + 4 * 2 / (1-5) ^ 2». Потрібно перевести його до польського запису

Читаємо «3»
Додаємо «3» до виходу
 Вихід: 3

Читаємо «+»
Вставляємо «+» в стек
 Вихід: 3
 Стек: +

Читаємо «4»
Додаємо «4» до виходу
 Вихід: 3 4
 Стек: +

Читаємо «*»
Вставляємо «*» в стек
 Вихід: 3 4
 Стек: + *

Читаємо «2»
Додаємо «2» до виходу
 Вихід: 3 4 2
 Стек: + *

Читаємо «/»
Видаляємо «*» зі стека і додаємо до виходу, вставляємо «/» в стек
 Вихід: 3 4 2 *
 Стек: + /

Читаємо «(»
Вставляємо «(» в стек
 Вихід: 3 4 2 *
 Стек: + / (

Читаємо «1»
Додаємо «1», до виходу
 Вихід: 3 4 2 * 1
 Стек: + / (

Читаємо «-»
Вставляємо «-» в стек
 Вихід: 3 4 2 * 1
 Стек: + / (-

Читаємо «5»
Додаємо «5» до виходу
 Вихід: 3 4 2 * 1 5
 Стек: + / (-

Читаємо «)»
Видаляємо «-» зі стека і додаємо до виходу, видаляємо «(» зі стека
 Вихід: 3 4 2 * 1 5 -
 Стек: + /

Читаємо «^»
Додаємо «^» в стек
 Вихід: 3 4 2 * 1 5 -
 Стек: + / ^

Читаємо «2»
Додаємо «2» до виходу
 Вихід: 3 4 2 * 1 5 - 2
 Стек: + / ^

Кінець виразу
Витягуємо усі елементи зі стека і додаємо до виходу
 Вихід: 3 4 2 * 1 5 - 2 ^ / +

Див. також ред.

Стекова мова програмування

Посилання ред.

↑ ^а ^б Складанюк, Максим (2020). Арифметичний калькулятор (Курсова робота) (укр.). Бердичів, Україна.
↑ RPN. www.hpmuseum.org. Процитовано 3 жовтня 2023.
↑ Solution 11904: Using Reverse Polish Notation (RPN) on TI Calculators. education.ti.com (англ.). Процитовано 3 жовтня 2023.
↑ Poluektov, Anton (17 вересня 2023), OpenRPNCalc, процитовано 3 жовтня 2023
↑ List, Jenny (5 червня 2021). An Open-source Scientific RPN Calculator. Hackaday (амер.). Процитовано 3 жовтня 2023.

[:0-1] а ^б Складанюк, Максим (2020). Арифметичний калькулятор (Курсова робота) (укр.). Бердичів, Україна.

[2] RPN. www.hpmuseum.org. Процитовано 3 жовтня 2023.

[3] Solution 11904: Using Reverse Polish Notation (RPN) on TI Calculators. education.ti.com (англ.). Процитовано 3 жовтня 2023.

[4] Poluektov, Anton (17 вересня 2023), OpenRPNCalc, процитовано 3 жовтня 2023

[5] List, Jenny (5 червня 2021). An Open-source Scientific RPN Calculator. Hackaday (амер.). Процитовано 3 жовтня 2023.

[1]

[2]

[3]

[4]

[5]