Loading AI tools
З Вікіпедії, вільної енциклопедії
Польський інверсний запис (ПОЛІЗ, англ. Reverse Polish Notation (RPN), дос. «зворотня польська нотація», зворотний бездужковий запис, постфіксна нотація) — форма запису математичних виразів, в якій знаки операцій розташовано після операндів. Розташування знаків операцій перед операндами використовує польська нотація.
Зворотний польський запис розробив австралійський філософ і фахівець у галузі теорії обчислювальних машин Чарлз Гемблін[en] у середині 1950-х років на основі польської нотації, яку запропонував 1920 року польський математик Ян Лукашевич. Роботу Гембліна представлено на конференції в червні 1957 року, і видано в 1957 і 1962 роках.
Першими комп'ютерами, що підтримують зворотний польський запис були KDF9[en] від English Electric Company, який був випущений в 1963, і американський Burroughs B5000, випущений в тому ж 1963. Зворотна польська нотація застосовувалася в радянському інженерному калькуляторі Б3-19М, випущеному в 1976 році. Майже всі програмовані калькулятори в СРСР аж до кінця 1980-х років використовували ПОЛІЗ — він простіше реалізовувався і дозволяв обійтися в програмуванні обчислень меншим числом команд, порівняно зі звичайною алгебраїчною нотацією, адже обсяг програмної пам'яті в цих моделях завжди було критичним ресурсом.[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[en][2], HP-15C[en][3]), Texas Instruments (програмно[4]). Практично всі програмовані калькулятори, що вироблялися в СРСР (Електроніка Б3-34, МК-52, МК-61[en] та інші) застосовували зворотну польську нотацію.
Існують кілька калькуляторів з відкритим апаратним забезпеченням і підтримкою ПОЛІЗ, наприклад OpenRPNCalc, кишеньковий інженерний калькулятор на базі мікропроцесора STMicroelectronics STM32 (модель STM32L476).[5][6]
Існує велика кількість програмного забезпечення у вигляді калькуляторів з підтримкою ПОЛІЗ (у тому числі й емулятороів і симуляторів апаратних калькуляторів та мікрокалькуляторів) для різних платформ[7][8][9], зокрема:
xcalc
[17] (є частиною X.Org), KCalc[en] (є частиною KDE), GNOME Calculator[en](є частиною GNOME), galculator (з інтерфейсом на GTK), XCALC[16] (з інтерфейсом на Qt4), x11-calc
[18] (симулятор різних калкуляторів HP з інтрефейсом на X11), calc
(бібліотека для Emacs)Для всіх символів виконуємо такі дії:
Маємо вираз: 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 |
Маємо рядок 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 ^ / +
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.