Обратниот полски запис: алгоритам, методи и примери

Обратниот полски рекорд некогаш беше основа на светот на компјутерскиот програмер. Денес тоа не е толку добро познато. Затоа, комична илустрација што ја опишува "обратната" полска колбас надвор од пунџата, сепак може да биде погрешно разбрана од некои познавања на програмерите. Не е добро да се објасни шега, но во овој случај тоа ќе биде целосно оправдано.

Внеси влез

Сите програмери и повеќето студенти се запознаени со употребата на оператори. На пример, во изразот x + y, знакот за додавање се користи за да ги сумира вредностите на променливите x и y. Помалку познато е дека ова позајмено од математичката ознака, наречено инфиксна нотација, всушност е голем проблем за машините. Таквиот оператор зема влез две вредности напишани лево и десно од него. Во програмирањето, не е неопходно да се користи нотација со оперативни знаци. На пример, x + y може да биде напишана како функција за додавање на (x, y), на кој компилерот на крајот ја конвертира инфиксната нотација. Сепак, секој знае математика премногу добро да не користи аритметички изрази, кои претставуваат еден вид на внатрешен мини-јазик во речиси секој програмски јазик.

Преведувачи на формули

Првиот навистина успешен програмски јазик Фортра стана толку во основа бидејќи аритметичките изрази (односно, формулите) во него беа конвертирани (преведени) во кодот, па оттука и неговото име - FORmula TRANslation. Пред, тие мораа да бидат напишани, на пример, во форма на функции додадете (a, множете (b, c)). Во Кобол, проблемот со имплементирањето на автоматската конверзија на формулата беше многу тешко, бидејќи програмерите мораа да пишуваат работи како што е додавање на А до B Mutliply од C.

Што не е во ред со инфиксот?

Проблемот е што операторите имаат својства како приоритет и асоцијативност. Поради ова, дефиницијата за функцијата на инфиксот станува нетривијална задача. На пример, приоритетот на множител е поголем од додавањето или одземањето, а тоа значи дека изразот 2 + 3 * 4 не е еднаков на збирот од 2 и 3, помножен со 4, како што би бил случај кога извршувате оператори од лево надесно. Всушност, множете се 3 од 4 и додадете 2. Овој пример илустрира дека оценувањето на инфиксната израз често бара промена на редот на операторите и нивните операнди. Покрај тоа, ние треба да користиме загради за да ја направиме нотацијата појасна. На пример, (2 + 3) * (4 + 5) не може да се напише без загради, бидејќи 2 + 3 * 4 + 5 значи дека мора да се умножи 3 од 4 и да додадете 2 и 5.

Редоследот во кој операторите треба да се пресметаат бара долго меморирање. Поради ова, учениците почнуваат да учат аритметички често добиваат погрешни резултати, дури и ако всушност операциите се изведуваат правилно. Потребно е да го научиме поредокот на активностите на операторите. Прво, мора да се извршат активности во загради, потоа множење и поделба, и, конечно, додавање и одземање. Но, постојат и други начини на пишување на математички изрази, бидејќи инфиксната нотација е само еден од можните "мали јазици" кои можат да се додадат на повеќе.

Префикс и постфиксна нотација

Двете најпопуларни алтернативи се снимање на оператор пред или после неговите операнди. Тие се познати како префикс и постфиксни нотации. Логичарот Јан Лукасевич го измислил првиот од нив во 1920-тите. Тој живеел во Полска, па рекордот се нарекува полски. Верзијата на Postfix, соодветно, беше наречена обратна полска нотација (OPN). Единствената разлика помеѓу двата методи е во насоката во која треба да се чита записот (од лево кон десно или од десно кон лево), така што е доволно да се разгледа само еден од нив во детали. Во OPN, операторот е напишан по своите операнди. Така, изразот AB + е пример за обратен полски запис за A + B.

Неограничен број операнди

Непосредната предност на нотација е тоа што таа е генерализирана од n-адичкиот оператор, а инфиксната нотација всушност работи само со два операнда, односно е по својата природа погодна само за бинарни операции. На пример, ABC @ е инверзна полска експресија со помош на триадичниот знак, кој ја наоѓа максималната вредност од A, B и C. Во овој случај, операторот дејствува на 3 операнди лево од себе и одговара на повикот на функцијата @ (A, B, C). Ако се обидете да го напишете @ симболот како инфикс, на пример, А @ BC или нешто слично, тогаш станува јасно дека ова едноставно не функционира.

Приоритет е даден со цел

Обратниот полски запис има уште една предност во тоа што приоритетот на операторите може да биде претставен со редоследот на нивниот изглед. Заканите никогаш нема да бидат потребни, иако тие можат да бидат вклучени како трансакциски симболи за да се олесни конверзијата со инфиксна нотација. На пример, AB + C * е еднозначен еквивалент (A + B) * C, бидејќи множењето не може да се пресмета додека не се комплетира додатокот, што го дава вториот операнд за операцијата на множење. Тоа е, ако AB + C * се пресметува за еден оператор одеднаш, тогаш добиваме AB + C * -> (AB +) * C -> (A + B) * C.

Алгоритам за пресметка

Во OPN, операторот изгледа како функција која ги зема како аргументи две вредности напишани лево од неа. Покрај тоа, ова е природна нотација за употреба во програмските јазици, бидејќи текот на неговите пресметки одговара на операциите на стек и се елиминира потребата за парсирање. На пример, во ARS изразот 5 + 6 * 7 ќе изгледа како 5, 6, 7 *, +, и може да се пресмета со едноставно скенирање од лево кон десно и пишување вредности во магацинот. Секој пат кога ќе се сретне знакот за работа, се избираат 2 горните елементи од меморијата на машината, операторот се применува и резултатот се враќа во меморијата. Кога ќе се достигне крајот на изразот, резултатот од пресметката ќе биде на врвот на стекот.

На пример:

• S = () 5, 6, 7, *, + стави 5 на магацинот.
• S = (5) 6, 7, *, + стави 6 на магацинот.
• S = (5, 6) 7, *, + ставете 7 на магацинот.
• S = (5, 6, 7) *, + одберете 2 вредности од стекот, се применуваат * и ставете го резултатот во магацинот.
• S = (5, 6 * 7) = (5, 42) + изберете 2 вредности од магацинот, аплицирајте + и ставете го резултатот на магацинот.
• S = (5 + 42) = (47) пресметката е завршена, резултатот е на врвот на стекот.

Овој алгоритам за обратен полски влез може да се провери многу пати, но секогаш кога ќе работи, без разлика колку е сложено аритметичкиот израз.

Прекинувачот и купиштата се тесно поврзани. Горенаведениот пример покажува како меморијата може да се користи за пресметување на вредноста во инверзна полска нотација. Помалку е очигледно дека можете да го користите магацинот со претворање на стандардни инфиксни изрази на заостанати долгови.

Примери во програмските јазици

На јазикот Паскал, обратниот полски запис се спроведува приближно вака (дел од програмата е дадена).

За да ги прочитате броевите и операторите во јамка, се именува постапка со која се одредува дали токенот е број или оперативен знак. Во првиот случај, вредноста е запишана во магацинот, додека во вториот случај, соодветното дејство се врши на првите два броја од магацинот и резултатот е зачуван.

Тотип: = број;

Прочитајте (в);

Ако со ['+', '-', '*', '/'] започнете

Ако eoln тогаш cn: = '' друго читај (cn);

Ако cn = '' тогаш

Случај со

'+': Toktype: = додадете; '-': toktype: = sub;

'*': Toktype: = mul; '/': Toktype: = div

Крај

Елс започнува

Ако c = '-' тогаш sgn: = -1 друго грешка: = c <> '+';

Со: = cn

Крај

Крај;

Ако (не грешка) и (toktype = num) тогаш се добиваатброј;

Доколку започнете со точката <> num тогаш

Y: = по; X: = по;

Ако не е грешка, тогаш

Случај toktype на

Додај: z: = x + y; Под: z: = x-y; Mul: z: = x * y; Div: z: = x / y

Крај

Притисни (z);

C-имплементација на обратен полски запис (дел од програмата е дадена):

За (s = strtok (s, w); s; s = strtok (0, w)) {

A = strtod (s, & e);

Ако (e> s) притиснете (a);

#define rpnop (x) printf ("% s:", * s), b = pop (), a = pop (), притисни (x)

Друго, ако (* s == '+') rpnop (a + b);

Друго ако (* s == '-') rpnop (a-b);

Друго, ако (* s == '*') rpnop (a * b);

Друго ако (* s == '/') rpnop (a / b);

#undef rpnop

}

Хардвер имплементации

Во тие денови, кога компјутерската технологија беше многу скапа, се сметаше за добра идеја да ги натера луѓето да користат OPN. Во 1960-тите, како и денес, беше можно да се купат калкулатори кои работат во обратна полска снимка. За да додадете 2 и 3 во нив, внесете 2, потоа 3 и притиснете го копчето плус. На прв поглед, влезот на операндите на операторот се чинеше комплициран и тешко да се запомни, но по некое време некои станаа зависници од овој начин на размислување и не можеа да разберат зошто други инсистираат на глупав инфикс рекорд кој е толку комплициран и толку ограничен.

Бароуз дури и изградил супер-систем кој немал друга RAM меморија, освен магацинот. Единственото нешто што машината го направи беше да се применат алгоритми и методи на обратно полско пишување до централниот оџак. Сите негови операции се сметаа за OPN оператори, чие дејство се прошири до n горните вредности. На пример, командата за враќање зеде адреса од врвот на магацинот итн. Архитектурата на таква машина беше едноставна, но не доволно брза за да се натпреварува со поопштите архитектури. Меѓутоа, многумина, сепак, жалат дека таков едноставен и елегантен пристап кон пресметката, каде што секоја програма беше израз на OPN, не го најде својот продолжение.

Во еден момент калкулатори со обратна полска снимка беа популарни, а некои сè уште ги преферираа. Покрај тоа, развиени се стек-ориентирани јазици како Форти. Денес, малку се користи, но сепак предизвикува носталгија од страна на нејзините поранешни корисници.

Значи, што е поентата на шега за грбот колбас?

Ако сметате дека операторот на колбас, тогаш во инфиксната нотација, треба да биде во ролната, како во нормален виршлаг. Во обратниот полски запис, тоа е од десно на двете половини, подготвени да се погоди меѓу нив по пресметката. Сега почнува најтешкиот дел - сенф. Веќе е на колбас, односно веќе е пресметан како унарен оператор. Има мислење дека сенф, исто така, треба да биде прикажан како недефиниран и, според тоа, треба да се премести на десната страна на колбас ... Но, можеби тоа ќе потрае премногу голем број ...