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

Постфіксна нотація ("Інверсний польський") Інфіксна нотація Префіксна нотація ("Польська")

п о р

Польський інверсний запис (ПОЛІЗ, англ. 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

слід виконати такі дії:

• обчислити a
• обчислити b
• скласти результати (+)

Саме така послідовність і задається польським інверсним записом: a b +

Комп'ютерні програми зазвичай під час аналізу формул перетворюють їх на послідовність інструкцій у ПОЛІЗ, і саме в такому порядку вони виконуються.

На основі постфіксної нотації побудовано мову програмування Forth, також вона безпосередньо застосовується у PostScript.

Стековою машиною^[en] називається алгоритм, який проводить обчислення за зворотною польською нотацією^{[джерело?]}. Прикладом використання стекової машини є програма UNIX dc.

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

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

Існує велика кількість програмного забезпечення у вигляді калькуляторів з підтримкою ПОЛІЗ (у тому числі й емулятороів і симуляторів апаратних калькуляторів та мікрокалькуляторів) для різних платформ^[7][8][9], зокрема:

• крос-платформові: WRPN (симулятор HP-16C^[en]), JRPN (HP-15C^[en] та HP-16C^[en]), Free42/Plus42^[10] (симулятор HP-42S^[en]), Calcoo^[11] (симулятор HP-28^[en]), RPN-45^[12] (емулятор HP-45^[en]), Qalculate!^[en], Stak/Stak16^[13] (симулятор HP-16C^[en]), RRDtool
• для комп'ютерів:
  • MS-DOS/Windows 1.0x-3.1x (16-біт): WRPN
  • Windows 95—Windows 11 (x86-32, x86-64): Калькулятор Windows, RayRPN^[14], Emu48^[15] (емулятор різних калькуляторів HP), XCALC^[16] (з інтерфейсом на Qt4)
  • Mac OS: Калькулятор (Apple)
  • Linux та інших Unix: dc, xcalc^[17] (є частиною X.Org), KCalc^[en] (є частиною KDE), GNOME Calculator^[en](є частиною GNOME), galculator (з інтерфейсом на GTK), XCALC^[16] (з інтерфейсом на Qt4), x11-calc^[18] (симулятор різних калкуляторів HP з інтрефейсом на X11), calc (бібліотека для Emacs)
• для мобільних пристроїв:
  • мобільні телефони (у вигляді прошивки): RPN Calculator^[19] (Nokia 6110^[en] та інші Nokia на платформі DCT3, підтримувані NokiX^[20])
  • фічефони і смартфони з підтримкою J2ME (Java ME):
    • MIDP 1.0: UPN^[21], Stak/Stak16^[13] (симулятор HP-16C^[en])
    • MIDP 2.0: Calc^[22], HorsePower^[23], RPN-45^[24][25] (емулятор HP-45^[en] для Symbian UIQ)
  • iOS: RPN Simulators^[26] (симулятори різних калькуляторів HP)
  • Android: Free42/Plus42^[10] (симулятор HP-42S^[en])
  • Symbian S60: Calcium^[27]
  • Pocket PC (Windows Mobile): RayRPN^[28], Emu48^[15]
  • Palm OS: RayRPN^[29], Power48^[30] (порт Emu48^[15])
  • комунікатори Psion^[en] (Symbian EPOC): Psion48^[31][32] (симулятор HP-48^[en])

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

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

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

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

Порядок дій над ним буде такий:

• Поки ще є символи для зчитування:
  • Читаємо наступний символ;
  • Якщо символ є числом або постфіксною функцією (наприклад, ! — факторіал), то додаємо до вихідного рядка;
  • Якщо символ є префіксною функцією (наприклад, 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 ^ / + 

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

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

1. ↑ ^{а б} Складанюк, Максим (2020). Арифметичний калькулятор (Курсова робота) (укр.). Бердичів, Україна.
2. ↑ RPN. www.hpmuseum.org. Процитовано 3 жовтня 2023.
3. ↑ RPN calculators. linuxfocus.org. Процитовано 6 вересня 2024.
4. ↑ Solution 11904: Using Reverse Polish Notation (RPN) on TI Calculators. education.ti.com (англ.). Процитовано 3 жовтня 2023.
5. ↑ Poluektov, Anton (17 вересня 2023), OpenRPNCalc, процитовано 3 жовтня 2023
6. ↑ List, Jenny (5 червня 2021). An Open-source Scientific RPN Calculator. Hackaday (амер.). Процитовано 3 жовтня 2023.
7. ↑ RPN Tutorial. hansklav.home.xs4all.nl. Процитовано 6 вересня 2024.
8. ↑ OTHER Files. www.hpcalc.org. Процитовано 6 вересня 2024.
9. ↑ HP Calculator Simulations. www.hpmuseum.org. Процитовано 6 вересня 2024.
10. ↑ ^{а б} Free42 : An HP-42S Calculator Simulator. thomasokken.com. Процитовано 6 вересня 2024.
11. ↑ Calcoo - RPN and algebraic scientific calculator. calcoo.sourceforge.net. Процитовано 6 вересня 2024.
12. ↑ Krischik, Martin (16 липня 2024). RPN-45 Scientific Calculator. uiq3.sourceforge.io (брит.). Процитовано 6 вересня 2024.
13. ↑ ^{а б} Degnbol, Gunnar. Stak. home.tiscali.dk (англ.). Архів оригіналу за 3 листопада 2004.
14. ↑ Windows. rayslogic.com. Процитовано 6 вересня 2024.
15. ↑ ^{а б в} Christoph Giesselink Emu48 Page. hp.giesselink.com. Процитовано 6 вересня 2024.
16. ↑ ^{а б} XCALC. tordivel.no. Процитовано 6 вересня 2024.
17. ↑ XCALC. www.x.org (англ.). Процитовано 6 вересня 2024.
18. ↑ mike632t (27 серпня 2024), mike632t/x11-calc, процитовано 6 вересня 2024
19. ↑ RPN Calculator for Nokia DCT-3 phones. panuworld.net. Процитовано 6 вересня 2024.
20. ↑ NokiX. SourceForge (англ.). 7 квітня 2013. Процитовано 6 вересня 2024.
21. ↑ Schwebke Softwareentwicklung: UPN-Calc. www.schwebke.com. Процитовано 6 вересня 2024.
22. ↑ Calc - Java Calculator: Scientific, Statistical, Financial, Programmable, Graphing, RPN. midp-calc.sourceforge.net. Процитовано 6 вересня 2024.
23. ↑ HorsePower J2ME RPN Calculator. SourceForge (англ.). 30 липня 2016. Процитовано 6 вересня 2024.
24. ↑ Krischik, Martin (13 січня 2011). Symbian. uiq3.sourceforge.io (брит.). Процитовано 6 вересня 2024.
25. ↑ Rechlin, Eric (2008). RPN-45 Emulator for Symbian. news.hpcalc.org.
26. ↑ RPN Simulators for iOS Devices. cuveesoft.ch. Процитовано 6 вересня 2024.
27. ↑ Calcium - Fast free calculator for S60. mtvoid.com. Процитовано 6 вересня 2024.
28. ↑ PocketPC. rayslogic.com. Процитовано 6 вересня 2024.
29. ↑ Ray's RPN Calculator. rayslogic.com. Процитовано 6 вересня 2024.
30. ↑ Power48. hpcalc.org (англ.). Процитовано 6 вересня 2024.
31. ↑ Psion48: The scientific RPN calculator for Symbian OS. psion48.free.fr. Процитовано 6 вересня 2024.
32. ↑ Psion48 2.0 - detailed information. www.hpcalc.org. Процитовано 6 вересня 2024.

Ця стаття є частиною Проєкту:Математика (рівень: III, важливість: середня)
	Мета проєкту — створення якісних та інформативних статей на теми, пов'язані з Математикою. Ви можете покращити цю статтю, відредагувавши її, а на сторінці проєкту вказано, чим ще можна допомогти. Учасники проєкту будуть вам вдячні.
III (у розвитку)	Ця стаття за шкалою оцінок статей Проєкту:Математика має рівень «стаття у розвитку».
Середня	Важливість цієї статті для проєкту Математика: «середня»
	Чим допомогти: Статті до створення та доопрацювання