Польський інверсний запис
 |
Польський інверсний запис (ПОЛІЗ, англ. 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] називається алгоритм, який проводить обчислення за зворотною польською нотацією[джерело?]. Прикладом використання стекової машини є програма UNIX dc.
x11-calcПОЛІЗ здобув досить широке розповсюдження в інженерних настільних калькуляторах та мікрокалькуляторах і мікрокомп'ютерах. Зокрема, такі калькулятори виробляли фірми 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):
- 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 / + * +
Порядок дій над ним буде такий:
| Крок | Елемент | Стек |
|---|---|---|
| 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 — синус), поміщаємо його в стек;
- Якщо символ є '(', поміщаємо його в стек;
- Якщо символ є ')', то:
- До тих пір, поки верхнім елементом стека не стане відкриваюча дужка, виштовхуємо елементи зі стека у вихідний рядок. При цьому відкриваюча дужка видаляється зі стека, але у вихідний рядок не додається. Якщо після цього кроку на вершині стека виявляється символ функції, виштовхуємо його у вихідний рядок. Якщо стек закінчився раніше, ніж ми зустріли відкриваючу дужку, це означає, що у виразі або неправильно поставлений розділовий знак, або неузгодженні дужки.
- Якщо символ є бінарною операцією, тоді:
- поки на вершині стека префіксна функція…
- … АБО операція на вершині стека має більший пріоритет ніж o1
- … АБО операція на вершині стека ліво-асоціативна з пріоритетом як у o1
- … виштовхуємо верхній елемент стека у вихідний рядок;
- поміщаємо операцію 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) |
- ↑ а б Складанюк, Максим (2020). Арифметичний калькулятор (Курсова робота) (укр.). Бердичів, Україна.
- ↑ RPN. www.hpmuseum.org. Процитовано 3 жовтня 2023.
- ↑ RPN calculators. linuxfocus.org. Процитовано 6 вересня 2024.
- ↑ 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.
- ↑ RPN Tutorial. hansklav.home.xs4all.nl. Процитовано 6 вересня 2024.
- ↑ OTHER Files. www.hpcalc.org. Процитовано 6 вересня 2024.
- ↑ HP Calculator Simulations. www.hpmuseum.org. Процитовано 6 вересня 2024.
- ↑ а б Free42 : An HP-42S Calculator Simulator. thomasokken.com. Процитовано 6 вересня 2024.
- ↑ Calcoo - RPN and algebraic scientific calculator. calcoo.sourceforge.net. Процитовано 6 вересня 2024.
- ↑ Krischik, Martin (16 липня 2024). RPN-45 Scientific Calculator. uiq3.sourceforge.io (брит.). Процитовано 6 вересня 2024.
- ↑ а б Degnbol, Gunnar. Stak. home.tiscali.dk (англ.). Архів оригіналу за 3 листопада 2004.
- ↑ Windows. rayslogic.com. Процитовано 6 вересня 2024.
- ↑ а б в Christoph Giesselink Emu48 Page. hp.giesselink.com. Процитовано 6 вересня 2024.
- ↑ а б XCALC. tordivel.no. Процитовано 6 вересня 2024.
- ↑ XCALC. www.x.org (англ.). Процитовано 6 вересня 2024.
- ↑ mike632t (27 серпня 2024), mike632t/x11-calc, процитовано 6 вересня 2024
- ↑ RPN Calculator for Nokia DCT-3 phones. panuworld.net. Процитовано 6 вересня 2024.
- ↑ NokiX. SourceForge (англ.). 7 квітня 2013. Процитовано 6 вересня 2024.
- ↑ Schwebke Softwareentwicklung: UPN-Calc. www.schwebke.com. Процитовано 6 вересня 2024.
- ↑ Calc - Java Calculator: Scientific, Statistical, Financial, Programmable, Graphing, RPN. midp-calc.sourceforge.net. Процитовано 6 вересня 2024.
- ↑ HorsePower J2ME RPN Calculator. SourceForge (англ.). 30 липня 2016. Процитовано 6 вересня 2024.
- ↑ Krischik, Martin (13 січня 2011). Symbian. uiq3.sourceforge.io (брит.). Процитовано 6 вересня 2024.
- ↑ Rechlin, Eric (2008). RPN-45 Emulator for Symbian. news.hpcalc.org.
- ↑ RPN Simulators for iOS Devices. cuveesoft.ch. Процитовано 6 вересня 2024.
- ↑ Calcium - Fast free calculator for S60. mtvoid.com. Процитовано 6 вересня 2024.
- ↑ PocketPC. rayslogic.com. Процитовано 6 вересня 2024.
- ↑ Ray's RPN Calculator. rayslogic.com. Процитовано 6 вересня 2024.
- ↑ Power48. hpcalc.org (англ.). Процитовано 6 вересня 2024.
- ↑ Psion48: The scientific RPN calculator for Symbian OS. psion48.free.fr. Процитовано 6 вересня 2024.
- ↑ Psion48 2.0 - detailed information. www.hpcalc.org. Процитовано 6 вересня 2024.
Основні теми математичного аналізу | |
|---|---|
| Ця стаття є частиною Проєкту:Математика (рівень: III, важливість: середня) | ||
|---|---|---|
|
Мета проєкту — створення якісних та інформативних статей на теми, пов'язані з Математикою. Ви можете покращити цю статтю, відредагувавши її, а на сторінці проєкту вказано, чим ще можна допомогти. Учасники проєкту будуть вам вдячні. | |
| III (у розвитку) |
Ця стаття за шкалою оцінок статей Проєкту:Математика має рівень «стаття у розвитку». | |
|
Середня |
Важливість цієї статті для проєкту Математика: «середня» | |
Чим допомогти: Статті до створення та доопрацювання
| ||
