Зворотній польський запис

Не слід плутати з (Прямий) польської нотацією.

Зворотній польська нотація (ГНН) - форма запису математичних виразів, в якій операнди розташовані перед знаками операцій. Також іменується як зворотна польський запис, зворотна бесскобочная запис (ОБЗ), постфіксной нотація, бесскобочная символіка Лукашевича, польська інверсна запис, полізім.

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


1. Історія

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

Першими комп'ютерами, що підтримують зворотний польську нотацію були KDF9 від English Electric Company, який був анонсований в 1960 і випущений (з'явився у продажу) в 1963, і американський Burroughs B5000, анонсований в 1961, випущений в тому ж 1963. Один з проектувальників B5000, Р. С. Бартон , Пізніше написав, що розробив зворотну польську запис незалежно від Хемблін, приблизно в 1958, в процесі читання книги по символьної логіки, і до того як познайомився з роботою Хемблін.

Компанія Friden перенесла ОПН в настільні калькулятори, випустивши у червні 1964 модель EC-130. А в 1968 інженери Hewlett-Packard розробили настільний калькулятор 9100A з підтримкою гострої ниркової недостатності. Цей калькулятор зробив зворотний польську нотацію популярною серед учених і інженерів, навіть незважаючи на те, що в ранній рекламі 9100A гострої ниркової недостатності не згадувалася. В 1972 калькулятор HP-35 з підтримкою гострої ниркової недостатності став першим науковим кишеньковим калькулятором.

У 1971 році з'явився оригінальний мову програмування Forth, мовна машина якого має двухстековую структуру і де всі обчислення проводяться на стеку. У цій мові гострої ниркової недостатності є природним способом запису будь-яких операцій з даними, хоча можлива, при бажанні, реалізація та звичайної (інфіксной) запису арифметичних операцій.

Гостра ниркова недостатність застосовувалася в радянському інженерному калькуляторі Б3-19М (спільна розробка з НДР), випущеному в 1976 році. Все що випускаються в СРСР аж до кінця 1980-х років програмовані мікрокалькулятори, за винятком "Електроніка МК-85", використовували ОПН - вона простіше реалізовувалася і дозволяла обійтися в програмуванні обчислень меншим числом команд, в порівнянні із звичайною алгебраїчної нотацією, а кількість програмної пам'яті в цих моделях завжди було критичним ресурсом (не більше 105 осередків, при тому, що команда займала 1-2 вічка). Гострої ниркової недостатності використовується в сучасних російських програмованих калькуляторах " Електроніка МК-152 "та" ЕЛЕКТРОНІКА МК-161 ", що забезпечує їх сумісність із програмами, написаними для радянських калькуляторів.


2. Визначення

Щоб дати індуктивне визначення постфіксной нотації [1], позначимо вираження в інфіксной нотації E , E_1 , E_2 , Еквівалентні їм вирази в постфіксной нотації \ Dot E , \ Dot E_1 , \ Dot E_2 відповідно; o - Довільний бінарний оператор, тоді:

1. Якщо E - Змінна або константа, то \ Dot E є E .

2. Якщо E - Вираз виду E_1 o E_2 , То \ Dot E є \ Dot E_1 \ dot E_2 o .

3. Якщо E - Вираз виду (E_1) , То \ Dot E є \ Dot E_1 .


3. Опис

Відмінною особливістю зворотної польської нотації є те, що всі аргументи (або операнди) розташовані перед знаком операції. У загальному вигляді запис виглядає наступним чином:

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

Наприклад, розглянемо обчислення виразу 7 2 3 * - (Еквівалентне вираження в інфіксной нотації: 7-2*3 ).

  1. Перший по порядку знак операції - "*", тому першою виконується операція множення над операндами 2 і 3 (вони стоять останніми перед знаком). Вираз при цьому перетвориться до вигляду 7 6 - (Результат множення - 6, - замінює трійку "2 3 *").
  2. Другий знак операції - "-". Виконується операція віднімання над операндами 7 і 6.
  3. Обчислення закінчено. Результат останньої операції дорівнює 1, це і є результат обчислення виразу.

Очевидне розширення зворотної польської записи на унарні, тернарні і операції з будь-яким іншим кількістю операндів: при використанні знаків таких операцій в обчисленні виразу операція застосовується до відповідного числа останніх зустрілися операндів.

Особливості зворотної польської записи наступні:

  • Порядок виконання операцій однозначно задається порядком проходження знаків операцій у виразі, тому відпадає необхідність використання дужок і введення пріоритетів і асоціативності операцій.
  • На відміну від інфіксной записи, неможливо використовувати одні й ті ж знаки для запису унарних і бінарних операцій. Так, в інфіксной запису вираз 5 * (-3 + 8) використовує знак "мінус" як символ унарний операції (зміна знака числа), а вираз (10 - 15) * 3 застосовує цей же знак для позначення бінарної операції (віднімання). Конкретна операція визначається тим, в якій позиції знаходиться знак. Зворотній польський запис не дозволяє цього: запис 5 3 - 8 + * (Умовний аналог першого виразу) буде інтерпретована як помилкова, оскільки неможливо визначити, що "мінус" після 5 і 3 позначає не віднімання; в результаті буде зроблена спроба обчислити спочатку 5 - 3, потім 2 + 8, після чого з'ясується, що для операції множення не вистачає операндів. Щоб все ж записати цей вираз, доведеться або переформулювати його, або ввести для операції зміни знака окреме позначення, наприклад, "": 5 3 8 + * .
  • Так само, як і в інфіксной нотації, в ОПН одне і те ж обчислення може бути записано в декількох різних варіантах. Наприклад, вираз (10 - 15) * 3 в ОПН можна записати як 10 15 - 3 * , А можна - як 3 10 15 - *
  • Через відсутність дужок зворотна польський запис коротше інфіксной. За цей рахунок при обчисленнях на калькуляторах підвищується швидкість роботи оператора (зменшується кількість натискає клавішу), а в програмованих пристроях скорочується обсяг тих частин програми, які описують обчислення. Останнє може бути важливо для портативних і вбудованих обчислювальних пристроїв, що мають жорсткі обмеження на обсяг пам'яті.

4. Обчислення на стеку

4.1. Загальний порядок

Автоматизація обчислення виразів в зворотної польської нотації заснована на використанні стека. Алгоритм обчислення для стековой машини елементарний:

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

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


4.2. Приклад обчислення виразів

Вираз (1 + 2) \ times 4 + 3 в ОПН може бути записано так: 1 2 + 4 3 +

Обчислення проводиться таким чином (вказано стан стека після виконання операції):

Введення Операція Стек
1 помістити в стек 1
2 помістити в стек 1, 2
+ додавання 3
4 помістити в стек 3, 4
* множення 12
3 помістити в стек 12, 3
+ додавання 15

Результат, 15, в кінці обчислень знаходиться на вершині стека.

Інший спосіб представити роботу стека в процесі обчислення представлений нижче (на прикладі калькулятора HP48S). (Вершина стека виділена кольором).

 ┌ ─ ─ ─ ─ ┐ │ 1 │ 1 [Введення] └ ─ ─ ─ ─ ┘ 
 ┌ ─ ─ ─ ─ ┐ │ 1 │ │ 2 │ 2 └ ─ ─ ─ ─ ┘ 
 ┌ ─ ─ ─ ─ ┐ │ 3 │ + └ ─ ─ ─ ─ ┘ 
 ┌ ─ ─ ─ ─ ┐ │ 3 │ │ 4 │ 4 └ ─ ─ ─ ─ ┘ 
 ┌ ─ ─ ─ ─ ┐ │ 12 │ * └ ─ ─ ─ ─ ┘ 
 ┌ ─ ─ ─ ─ ┐ │ 12 │ │ 3 │ 3 └ ─ ─ ─ ─ ┘ 
 ┌ ─ ─ ─ ─ ┐ │ 15 │ + └ ─ ─ ─ ─ ┘ 


Клавіша Ввід (позначається на калькуляторах як "Enter" або символом "↑") виконує роль роздільника операндів, коли два операнда безпосередньо слідують один за одним. Якщо за операндом слід знак операції, то її натискання не потрібно, це скорочує кількість дій, які потрібно виконати для отримання результату.


5. Перетворення з інфіксной нотації

Едсгер Дейкстра винайшов алгоритм для перетворення виразів із інфіксной нотації в ОПН. Алгоритм отримав назву "сортувальна станція", за схожість його операцій з подіями на залізничних сортувальних станціях. Інфіксная нотація - це форма математичних записів, яку використовує більшість людей (наприклад, 3 + 4 або 3 + 4 * (2 - 1) ). Як і алгоритм обчислення гострої ниркової недостатності, алгоритм сортувальної станції заснований на стеку. У перетворенні беруть участь дві текстових змінних: вхідна і вихідна рядки. У процесі перетворення використовується стек, який зберігає ще не додані до вихідний рядку оператори. Перетворююча програма читає вхідну рядок послідовно символ за символом (символ - це не обов'язково буква), виконує на кожному кроці деякі дії в залежності від того, який символ був прочитаний.


5.1. Простий приклад

Вхід: 3 + 4

Додамо 3 до вихідний рядку (якщо прочитано число, то воно відразу додається до вихідної рядку).

Поміщаємо + (або його Ідентифікатор) в стек операторів.

Додамо 4 до вихідний рядку.

Ми прочитали всі вираз, тепер виштовхуємо всі залишилися в стеці оператори в вихідну рядок. У нашому прикладі в стеку міститься тільки +.

Вихідна рядок: 3 4 +

У даному прикладі проявляються деякі правила: всі числа переносяться в вихідну рядок відразу після прочитання; коли вираз прочитано повністю, всі залишилися в стеці оператори виштовхуються в вихідну рядок.


5.2. Алгоритм

  • Поки є ще символи для читання:
  • Читаємо черговий символ.
  • Якщо символ є числом, додати його до вихідної рядку.
  • Якщо символ є символом функції, поміщаємо його в стек.
  • Якщо символ є відкриваючою дужкою, поміщаємо його в стек.
  • Якщо символ є закриваючою дужкою:
До тих пір, поки верхнім елементом стека не стане відкриваюча дужка, виштовхуємо елементи з стека в вихідну рядок. При цьому відкриває дужка видаляється з стека, але в вихідну рядок не додається. Якщо після цього кроку на вершині стека виявляється символ функції, виштовхуємо його у вихідну рядок. Якщо стек закінчився раніше, ніж ми зустріли відкриваючу дужку, це означає, що у виразі або невірно поставлений роздільник, або не погоджені дужки.
  • Якщо символ є оператором о1, тоді:
1) поки ...
... (Якщо оператор o1 право-асоціювання) пріоритет o1 менше пріоритету оператора, що знаходиться на вершині стека ...
... (Якщо оператор o1 асоційований, або ліво-асоційований) пріоритет o1 менший або дорівнює пріоритету оператора, що знаходиться на вершині стека ...
... Виштовхуємо верхні елементи стека в вихідну рядок;
2) поміщаємо оператор o1 в стек.
  • Коли вхідна рядок закінчилася, виштовхнути всі символи зі стека у вихідну рядок. У стеці повинні були залишитися тільки символи операторів; якщо це не так, значить у вираженні не узгоджені дужки.

5.3. Складний приклад

Пріоритети : ^ високий * / середній + - низький Вхід: 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 * 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 ^ / + 

6. Оптимізація виразів

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

6.1. Приклад алгоритму спрощення висловлювання

Розглянемо алгоритм, який здійснює перевирахованой констант в вираженні. Дано вираз в ОПН. Нам знадобиться стек для зберігання змішаних даних (чисел і операторів).

Алгоритм подібний до того, який застосовується для обчислення виразів. Ми переглядаємо вираз зліва направо.

Поки є символи для читання:

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

Після того, як всі вираз просмотрено, те, що залишилося в стеку, є оптимизирования виразом (оператори вираження лежать в стеку у зворотному порядку).


6.2. Приклад роботи алгоритму

 Вираз Інфіксая нотація: exp (-1 / 2 * x) Зворотній Польська нотація: -1 2 / x * exp Читаємо: "-1" Кладемо "-1" в стек Стек: -1 Читаємо: "2" Кладемо "2" в стек Стек: -1 2 Читаємо: "/" Обчислюємо приватне, результат кладемо в стек Стек: -0.5 Читаємо: "x" Кладемо "x" в стек зі значенням null Стек: -0.5 x (null) Читаємо: "*" Кладемо "*" в стек зі значенням null Стек: -0.5 x (null) * (null) Читаємо "exp" Кладемо "exp" в стек зі значенням null Стек: -0.5 x (null) * (null) exp (null) Результат оптимізації: -0.5 x * exp 

Даний метод, очевидно, не включає всіх можливих способів оптимізації.


7. Приклади реалізації

У статті " Зворотній польський запис: приклади реалізації "зібрані приклади реалізації зворотної польської записи на різних мовах програмування.

8. Практичні реалізації

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


Література

Т. Пратт, М. Зелковіц Мови програмування: розробка та реалізація = Terrence W. Pratt, Marvin V. Zelkowitz. Programming Languages: Design and Implementation. - 4-те видання. - Пітер, 2002. - 688 с. - (Класика Computer Science). - 4000 прим. - ISBN 5-318-00189-0

Примітки

  1. А. В. Ахо, Р. Мережі, Д. Д. Ульман. Компілятори: принципи, технології та інструменти. М.: "Вильямс", 2003. С. 51.