Польський інверсний запис (ПОЛІЗ, , зворотний бездужковий запис, постфіксна нотація) — форма запису математичних виразів, в якій знаки операцій розташовано після операндів. Розташування знаків операцій перед операндами використовує польська нотація.
Історія розробки Зворотний польський запис розробив австралійський філософ і фахівець у галузі теорії обчислювальних машин у середині 1950-х років на основі польської нотації, яку запропонував 1920 року польський математик Ян Лукашевич. Роботу Гембліна представлено на конференції в червні 1957 року, і видано в 1957 і 1962 роках.
Першими комп'ютерами, що підтримують зворотний польський запис були від English Electric Company, який був випущений в 1963, і американський Burroughs B5000, випущений в тому ж 1963. Зворотна польська нотація застосовувалася в радянському інженерному калькуляторі Б3-19М, випущеному в 1976 році. Майже всі програмовані калькулятори в СРСР аж до кінця 1980-х років використовували ПОЛІЗ — він простіше реалізовувався і дозволяв обійтися в програмуванні обчислень меншим числом команд, порівняно зі звичайною алгебраїчною нотацією, адже обсяг програмної пам'яті в цих моделях завжди було критичним ресурсом.
Загальний вигляд У загальному вигляді запис виглядає так:
Запис набору операцій складається з послідовності операндів і знаків операцій. Операнди у виразі при письмовому записі розділяються пробілами. Вираз читається зліва направо. Коли у виразі зустрічається знак операції, виконується відповідна операція над двома останніми перед ним операндами в порядку їх запису. Результат операції замінює у вираженні послідовність її операндів і її знак, після чого вираз обчислюється далі за тим же правилом. Результатом обчислення виразу стає результат останньої обчисленої операції.
Приклади Вираз Традиційна (інфіксна) нотація Зворотна польська (постфіксна) нотація 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.
називається алгоритм, який проводить обчислення за зворотною польською нотацією. Прикладом використання стекової машини є програма UNIX dc.
Калькулятори
ПОЛІЗ здобув досить широке розповсюдження в інженерних настільних калькуляторах та мікрокалькуляторах і мікрокомп'ютерах. Зокрема, такі калькулятори виробляли фірми Hewlett-Packard (, ), Texas Instruments (програмно). Практично всі програмовані калькулятори, що вироблялися в СРСР (Електроніка Б3-34, МК-52, та інші) застосовували зворотну польську нотацію.
Існують кілька калькуляторів з відкритим апаратним забезпеченням і підтримкою ПОЛІЗ, наприклад OpenRPNCalc, кишеньковий інженерний калькулятор на базі мікропроцесора STMicroelectronics STM32 (модель STM32L476).
Програмне забезпечення
Існує велика кількість програмного забезпечення у вигляді калькуляторів з підтримкою ПОЛІЗ (у тому числі й емуляторів і симуляторів апаратних калькуляторів та мікрокалькуляторів) для різних платформ, зокрема:
крос-платформові: WRPN (симулятор ), JRPN ( та ), Free42/Plus42 (симулятор ), Calcoo (симулятор ), RPN-45 (емулятор ), , Stak/Stak16 (симулятор ), RRDtool для комп'ютерів: MS-DOS/Windows 1.0x-3.1x (16-біт): WRPN Windows 95—Windows 11 (x86-32, x86-64): Калькулятор Windows, RayRPN, Emu48 (емулятор різних калькуляторів HP), XCALC (з інтерфейсом на Qt4) Mac OS: Калькулятор (Apple) Linux та інших Unix: dc, xcalc (є частиною X.Org), KCalc (є частиною KDE), (є частиною GNOME), galculator (з інтерфейсом на GTK), XCALC (з інтерфейсом на Qt4), x11-calc (симулятор різних калькуляторів HP з інтрефейсом на X11), calc (бібліотека для Emacs) для мобільних пристроїв: мобільні телефони (у вигляді прошивки): RPN Calculator ( та інші Nokia на платформі DCT3, підтримувані NokiX) фічефони і смартфони з підтримкою J2ME (Java ME): MIDP 1.0: UPN, Stak/Stak16 (симулятор ) MIDP 2.0: Calc, HorsePower, RPN-45 (емулятор для Symbian UIQ) iOS: RPN Simulators (симулятори різних калькуляторів HP) Android: Free42/Plus42 (симулятор ) Symbian S60: Calcium Pocket PC (Windows Mobile): RayRPN, Emu48 Palm OS: RayRPN, Power48 (порт Emu48) комунікатори (Symbian EPOC): Psion48 (симулятор )
Алгоритм для обчислення значення виразу Для всіх символів виконуємо такі дії:
Якщо Аі число, то вкласти його у стек; Якщо Аі оператор, то: Витягуємо зі стека два числа; Виконуємо дію із числами і результат вкладаємо в стек; Якщо Аі є функцією то: Витягуємо зі стека одне число; Визначаємо значення функції із відповідним аргументом та поміщаємо результат у стек; В кінці роботи в стеку знаходитиметься результат виразу.
Приклад
Маємо вираз: 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 ^ / +
Див. також Стекова мова програмування
Посилання
Примітки