1. Загальний порядок [ правити | правити код ]
2. Приклад обчислення виразів [ правити | правити код ]
3. Перетворення з інфіксной нотації [ правити | правити код ]
4. Простий приклад [ правити | правити код ]
5. алгоритм [ правити | правити код ]
6. Обмеження і модифікації [ правити | правити код ]
7. Складний приклад [ правити | правити код ]
8. Приклад алгоритму спрощення виразу [ правити | правити код ]
9. Приклад роботи алгоритму [ правити | правити код ]

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

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

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

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

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

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

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

Щоб дати індуктивне визначення постфіксной нотації [1] , Позначимо вираження в інфіксной нотації E {\ displaystyle E} , E 1 {\ displaystyle E_ {1}} , E 2 {\ displaystyle E_ {2}} , Еквівалентні їм вираження в постфіксной нотації E ˙ {\ displaystyle {\ dot {E}}} , E ˙ 1 {\ displaystyle {\ dot {E}} _ {1}} , E ˙ 2 {\ displaystyle {\ dot {E}} _ {2}} відповідно; o {\ displaystyle o} - довільний бінарний оператор, тоді:

1. Якщо E {\ displaystyle E} - змінна або константа, то E ˙ {\ displaystyle {\ dot {E}}} є E {\ displaystyle E} .

2. Якщо E {\ displaystyle E} - вираз виду E 1 o E 2 {\ displaystyle E_ {1} oE_ {2}} , То E ˙ {\ displaystyle {\ dot {E}}} є E ˙ 1 E ˙ 2 o {\ displaystyle {\ dot {E}} _ {1} {\ dot {E}} _ {2} o} .

3. Якщо E {\ displaystyle E} - вираз виду (E 1) {\ displaystyle (E_ {1})} , То E ˙ {\ displaystyle {\ dot {E}}} є E ˙ 1 {\ displaystyle {\ dot {E}} _ {1}} .

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

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

Наприклад, розглянемо обчислення виразу 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, після чого з'ясується, що для операції множення не вистачає операндів. Щоб все ж записати цей вислів, доведеться або переформулювати його (наприклад, записавши замість виразу - 3 вираз 0 - 3), або ввести для операції зміни знака окреме позначення, наприклад, «±» 5 3 ± 8 + *.
• Так само, як і в інфіксной нотації, в ОПН одне і те ж обчислення може бути записано в кількох різних варіантах. Наприклад, вираз (10 - 15) * 3 в ОПН можна записати як 10 15 - 3 *, а можна - як 3 10 15 - *
• Через відсутність дужок зворотна польська запис коротше інфіксной. За цей рахунок при обчисленнях на калькуляторах підвищується швидкість роботи оператора (зменшується кількість натискає клавішу), а в програмованих пристроях скорочується обсяг тих частин програми, які описують обчислення. Останнє може бути важливо для портативних і вбудованих обчислювальних пристроїв, що мають жорсткі обмеження на обсяг пам'яті.

Загальний порядок [ правити | правити код ]

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

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

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

Приклад обчислення виразів [ правити | правити код ]

Інфіксне вираз (1 + 2) × 4 + 3 {\ displaystyle (1 + 2) \ times 4 + 3} в ОПН може бути записано так: 1 2 + 4 × 3 +

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

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

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

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

Перетворення з інфіксной нотації [ правити | правити код ]

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

Простий приклад [ правити | правити код ]

Вхід: 3 + 4

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

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

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

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

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

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

алгоритм [ правити | правити код ]

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

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

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

• Якщо існують різні види дужок, поява непарної дужки також свідчить про помилку. Якщо якісь дужки одночасно є функціями (наприклад, [x] - ціла частина ), Додаємо до вихідному рядку символ цієї функції.

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

1) поки на вершині стека префиксная функція ... ... АБО операція на вершині стека приоритетнее o1 ... АБО операція на вершині стека левоассоціатівная з пріоритетом як у o1 ... виштовхуємо верхній елемент стека у вихідний рядок; 2) поміщаємо операцію o1 в стек.

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

Обмеження і модифікації [ правити | правити код ]

Алгоритм передбачає, що вихідна рядок коректна (перевіряються не всі помилки), і все префіксние / постфіксні функції унарні.

Модифікацію для багатомісних функцій з фіксованою кількістю аргументів см. в основній статті .

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

Складний приклад [ правити | правити код ]

пріоритети :

• високий: ^
• середній: * /
• низький: + -
• найнижчий: ( )

Вхід: 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 ^ / +

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

Приклад алгоритму спрощення виразу [ правити | правити код ]

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

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

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

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

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

Приклад роботи алгоритму [ правити | правити код ]

Вираз інфіксне нотація: 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

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

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

В якості практичного застосування даної методики можна привести організацію байт-коду конфігурацій прикладних рішень системи 1с Підприємство . Офіційного підтвердження компанія 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.

Мови програмування, що використовують ОПН в якості основної:

Інші посилання: