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

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

a + b

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

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

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

a b +

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

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

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

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

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

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

• Поки ще є символи для зчитування:

• Читаємо наступний символ;
• Якщо символ є числом або постфіксною функцією (наприклад, ! — факторіал), то додаємо до вихідного рядка;
• Якщо символ є префіксною функцією (наприклад, sin — синус), поміщаємо його в стек;
• Якщо символ є '(', поміщаємо його в стек;
• Якщо символ є ')', то:

До тих пір, поки верхнім елементом стека не стане відкриваюча дужка, виштовхуємо елементи зі стека у вихідний рядок. При цьому відкриваюча дужка видаляється зі стека, але у вихідний рядок не додається. Якщо після цього кроку на вершині стека виявляється символ функції, виштовхуємо його у вихідний рядок. Якщо стек закінчився раніше, ніж ми зустріли відкриваючу дужку, це означає, що у виразі або неправильно поставлений розділовий знак, або неузгодженні дужки.

• Якщо символ є бінарною операцією, тоді:

1) поки на вершині стека префіксна функція…

… АБО операція на вершині стека має більший пріоритет ніж o1

… АБО операція на вершині стека ліво-асоціативна з пріоритетом як у o1

… виштовхуємо верхній елемент стека у вихідний рядок;

2) поміщаємо операцію o1 у стек;

• Коли вхідний рядок закінчився, виштовхуємо всі символи зі стека у вихідний рядок. У стеку повинні були залишитись тільки символи операцій; якщо це не так, значить у виразі неузгоджені дужки.

Читаємо «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 ^ / +

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