Зворотний польський запис: алгоритм, методи і приклади

Зворотний польський запис колись становила основу світу комп'ютерного програміста. Сьогодні вона вже не так добре відома. Тому жартівлива ілюстрація, що зображає «зворотний» польську ковбасу за межами булочки, все ще може виявитися незрозумілою деякими добре обізнаними програмістами. Не дуже добре пояснювати жарт, але в даному випадку це буде в повній мірі виправдано.

Инфиксная запис

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

Транслятори формул

Перший дійсно успішний мова програмування Fortran став таким в основному тому, що арифметичні вирази (тобто формули) в ньому перетворювалися (транслювалися) в код, звідки і походить його назва – FORmula TRANslation. До цього їх доводилося записувати, наприклад, у вигляді функцій скласти (а, помножити (b, c)). У Коболе проблема реалізації автоматичного перетворення формул вважалася дуже важкою, оскільки програмістам доводилося писати такі речі, як Add A To B Mutliply By C.

Що не так з инфиксом?

Проблема полягає в тому, що оператори володіють такими властивостями, як пріоритет і асоціативність. З-за цього визначення функції инфикса стає нетривіальним завданням. Наприклад, пріоритет множення вище, ніж додавання або віднімання, і це означає, що вираз 2 + 3 * 4 не дорівнює сумі 2 і 3 помноженої на 4 як це було б при виконанні операторів зліва направо. Насправді слід помножити 3 на 4 і додати 2. Цей приклад ілюструє, що обчислення инфиксного вирази часто вимагає зміни порядку операторів та їх операндів. Крім того, доводиться використовувати дужки, щоб нотація виглядала більш ясно. Наприклад, (2 + 3) * (4 + 5) не можна записати без дужок, тому що 2 + 3 * 4 + 5 означає, що необхідно помножити 3 на 4 і додати 2 і 5. Порядок, в якому необхідно обчислювати оператори, вимагає тривалого запам'ятовування. З-за цього школярі, початківці вивчати арифметику, часто отримують неправильні результати, навіть якщо фактично операції виконуються правильно. Необхідно вчити порядок дії операторів напам'ять. Спершу повинні виконуватися дії в дужках, потім множення і ділення і, нарешті, додавання і віднімання. Але є й інші способи запису математичних виразів, оскільки инфиксная нотація є всього лише одним з можливих «малих мов», які можна додати до більшого.

Префіксна та постфіксна нотація

Двома найбільш відомими альтернативними варіантами є запис оператора до або після його операндів. Вони відомі як префіксна та постфіксна нотації. Логік Ян Лукасевич придумав першу з них у 1920-ті роки. Він жив у Польщі, тому запис називають польською. Постфиксный варіант, відповідно, отримав назву зворотної польської нотації (ОПН). Єдина різниця між цими двома методами полягає у напрямку, у якому слід читати запис (зліва направо або справа наліво), тому досить докладно розглянути лише один з них. В ОПН оператор записується після його операндів. Так, вираз АВ + являє собою приклад зворотного польського запису для A + B.

Необмежена кількість операндів

Безпосереднім перевагою нотації є те, що вона узагальнюється n-адическим оператором, а инфиксная нотація насправді працює тільки з двома операндами, тобто по своїй природі підходить тільки для бінарних операцій. Так, наприклад, ABC @ є зворотним польським виразом з використанням триадического знака, який знаходить максимальне значення A, B і C. У цьому випадку оператор діє на 3 операнда зліва від себе і відповідає викликом функції @ (A, В, С). Якщо спробувати записати символ " @ " в якості инфиксного, наприклад A @ BC або щось подібне, то стає зрозуміло, що це просто не працює.

Пріоритет задається порядком

Зворотний польський запис має ще одна перевага в тому, що пріоритет операторів може бути представлений порядком їх появи. При цьому ніколи не знадобляться дужки, хоча вони можуть бути включені в якості знаків операцій, щоб полегшити конвертацію з инфиксной нотацією. Наприклад, АВ + С * – однозначний еквівалент (А + В) * С, так як множення не може бути обчислено, поки не буде виконано додавання, яке дає другий операнд для операції множення. Тобто якщо обчислюється AB + C * по одному оператору за раз, то вийде A B + C * -> (A B +) * C -> (A+B)*C.

Алгоритм обчислення

В ОПН оператор виглядає так само, як функція, що приймає в якості аргументів два значення, записані зліва від неї. Крім того, це природна нотація для використання в мовах програмування, оскільки хід її обчислень відповідає стековим операцій і необхідність в синтаксичному аналізі відпадає. Наприклад, в ОПН вираз 5 + 6 * 7 буде виглядати як 567 *, +, і воно може бути обчислено просто шляхом сканування зліва направо і запису значень в стек. Кожен раз, коли зустрічається знак операції, вибираються 2 верхніх елемента з машинної пам'яті, застосовується оператор і результат повертається в пам'ять. При досягненні кінця виразу результат обчислень виявиться в вершині стека. Наприклад: S = () 567 *, + помістити 5 в стек. S = (5) 6 7 *, + помістити 6 в стек. S = (5 6) 7 *, + помістити 7 в стек. S = (567) *, + вибрати 2 значення зі стека, застосувати * і помістити результат в стек. S = (5 6 * 7) = (542) + вибрати 2 значення зі стека, застосувати + і помістити результат в стек. S = (5 + 42) = (47) обчислення завершено, результат знаходиться в вершині стека. Цей алгоритм зворотного польського запису можна перевіряти багато разів, але кожен раз він буде працювати, незалежно від того, наскільки складним є арифметичне вираження. ОПН та стеки тісно пов'язані між собою. Наведений приклад наочно демонструє, як можна використовувати пам'ять, щоб обчислити значення зворотної польської нотації. Менш очевидно, що можна використовувати стек, перетворивши стандартні інфіксние вираження в ГНН.

Приклади мовами програмування

На мові Паскаль зворотний польський запис реалізується приблизно так (наведена частина програми). Для зчитування чисел і операторів в циклі викликається процедура, яка визначає, чи є токен числом або знаком операції. В першому випадку значення записується в стек, а в другому над двома верхніми числами стека виконується відповідні дія і результат зберігається. toktype := num; read(с); if in['+', '-', '*', '/']then begin if eoln then cn := '' else read(cn); if cn = '' then case із of '+': toktype := add; '-': toktype := sub; '*': toktype := mul; '/': toktype := div end else begin if c = '-' then sgn := -1 else error := з <> '+'; с := cn end end; if (not error) and (toktype = num) then getnumber; if toktype <> num then begin у := рор; х := рор; if not error then case toktype of add: z := х+у; sub: z := х-у; mul: z := х*у; div: z := x/у end push(z); C-реалізація зворотного польського запису (наведено частина програми): for (s = strtok(s, w); s; s = strtok(0 w)) { a = strtod(s &e); if (e > s) push(a); #define rpnop(x) printf("%c:", *s), b = (pop), a = (pop), push(x) else if (*s == '+') rpnop(a + b); else if (*s == '-') rpnop(a - b); else if (*s == '*') rpnop(a * b); else if (*s == '/') rpnop(a /b); #undef rpnop }

Апаратні реалізації

В ті часи, коли обчислювальна техніка коштувала дуже дорого, вважалося хорошою ідеєю змушувати людей користуватися ОПН. У 1960-х рр., як і сьогодні, можна було придбати калькулятори, які працюють у зворотній польський запис. Для додавання 2 і 3 у них необхідно ввести 2 потім 3 і натиснути кнопку "плюс". На перший погляд, введення операндів до оператора здавався складним і важко запам'ятовується, але через деякий час деякі пристрастилися до такого способу мислення і не могли зрозуміти, чому інші наполягають на дурною инфиксной запису, яка так складна і так обмежена. Компанія Burroughs навіть побудувала мэйнфрейм, у якого не було ніякої іншої оперативної пам'яті, крім стека. Єдине, що робила машина, – застосовувала алгоритми і методи зворотного польського запису до центрального стеку. Всі її операції, розцінювалися як оператори ОПН, дія яких поширювалася на n верхніх значень. Наприклад, команда Return брала адресу з вершини стеку і т. д. Архітектура такої машини була простою, але недостатньо швидко, щоб конкурувати з більш загальними архітектурами. Багато хто, однак, до цих пір шкодують про те, що такий простий і елегантний підхід до обчислень, де кожна програма була виразом ОПН, не знайшов свого продовження. Один час калькулятори з зворотної польської записом користувалися популярністю, і дехто досі віддають їм перевагу. Крім того, були розроблені стек-орієнтовані мови, такі як Forth. Сьогодні він мало використовується, але досі викликає ностальгію з боку колишніх його користувачів.

Так в чому сенс жарти про зворотної польської сосиску?

Якщо вважати сосиску оператором, то в инфиксной нотації вона повинна знаходитися всередині булки, як у звичайному хот-догів. У зворотнього польського запису вона знаходиться правіше двох половинок, готова потрапити між ними після обчислення. Тепер починається найважча частина – гірчиця. Вона вже знаходиться на сосисці, тобто вже обчислена як унарний оператор. Існує думка, що гірчиця також має бути показана як невычисленная і, отже, повинна бути переміщена вправо від сосиски Але можливо, для цього буде потрібно занадто великий стек