Топ питань
Часова шкала
Чат
Перспективи

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

З Вікіпедії, вільної енциклопедії

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

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

Історія розробки

Зворотний польський запис розробив австралійський філософ і фахівець у галузі теорії обчислювальних машин Чарлз Гемблін[en] у середині 1950-х років на основі польської нотації, яку запропонував 1920 року польський математик Ян Лукашевич. Роботу Гембліна представлено на конференції в червні 1957 року, і видано в 1957 і 1962 роках.

Першими комп'ютерами, що підтримують зворотний польський запис були KDF9[en] від English Electric Company, який був випущений в 1963, і американський Burroughs B5000, випущений в тому ж 1963. Зворотна польська нотація застосовувалася в радянському інженерному калькуляторі Б3-19М, випущеному в 1976 році. Майже всі програмовані калькулятори в СРСР аж до кінця 1980-х років використовували ПОЛІЗ — він простіше реалізовувався і дозволяв обійтися в програмуванні обчислень меншим числом команд, порівняно зі звичайною алгебраїчною нотацією, адже обсяг програмної пам'яті в цих моделях завжди було критичним ресурсом.[1]

Remove ads

Загальний вигляд

У загальному вигляді запис виглядає так:

  • Запис набору операцій складається з послідовності операндів і знаків операцій. Операнди у виразі при письмовому записі розділяються пробілами.
  • Вираз читається зліва направо. Коли у виразі зустрічається знак операції, виконується відповідна операція над двома останніми перед ним операндами в порядку їх запису. Результат операції замінює у вираженні послідовність її операндів і її знак, після чого вираз обчислюється далі за тим же правилом.
  • Результатом обчислення виразу стає результат останньої обчисленої операції.[1]
Remove ads

Приклади

Більше інформації Вираз, Традиційна (інфіксна) нотація ...

Застосування

Узагальнити
Перспектива

Зворотний польський запис є зручним для застосування в обчислювальних пристроях. Наприклад, для обчислення виразу: a + b

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

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

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

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

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

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

Thumb
Мікрокалькулятор HP-15C[en]

Калькулятори

Thumb
Симуляція HP-15C у 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], зокрема:

Remove ads

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

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

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

Приклад

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

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

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

Більше інформації Крок, Елемент ...
Remove ads

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

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

Див. також

Посилання

Примітки

Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.

Remove ads
Remove ads