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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

Приклади[ред.ред. код]

Вираз Традиційна (інфіксна) нотація Зворотна польська (постфіксна) нотація
a + b × c a + bc a b c * +
(a + b) × (z + x) (a + b)*(z + x) a b + z x + *
(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 +

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

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

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

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

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

Для всіх символів робимо наступне:

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

Приклад[ред.ред. код]

Маємо вираз: 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

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

Зчитуємо символ поки не закінчаться і для кожного робимо наступне:

  • Якщо Ai є числом то виводимо його;
  • Якщо символ Ai є функцією завантажити його в стек;
  • Якщо символ Ai='(' то поміщаємо його в стек;
  • Якщо символ Ai=')' то:
    • До тих пір, поки верхнім елементом стека не стане відкриває дужка, виштовхуємо елементи з стека у вихідний рядок. При цьому відкриваюча дужка видаляється з стека, але у вихідну рядок не додається. Якщо після цього кроку на вершині стека виявляється символ функції, виштовхуємо його у вихідну рядок. Якщо стек закінчився раніше, ніж ми зустріли відкриває дужку, це означає, що у виразі або невірно поставлений розділовий знак, або не узгодженні дужки.
  • Якщо символ Ai є оператором то:
  1. поки …

… (Якщо оператор асоційований, або ліво-асоційований) пріоритет оператора менше або дорівнює пріоритету оператора, що знаходиться на вершині стека … … (Якщо оператор право-асоціювання) пріоритет оператора менше пріоритету оператора, що знаходиться на вершині стека … … Виштовхуємо верхні елементи стека у вихідний рядок; 2. Поміщаємо оператор в стек.

Приклад[ред.ред. код]

Маємо рядок «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 ^ / +