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

Обратният полски запис бе веднъж основа на света на компютърен програмист. Днес не е толкова добре познат. Следователно, комичната илюстрация, изобразяваща "обратната" полска наденица извън коня, все още може да бъде разбрана от някои познати програмисти. Не е много добре да обясняваме шегата, но в този случай ще бъде напълно оправдано.

Вмъкване на вмъкване

Всички програмисти и повечето студенти са запознати с използването на операторите. Например, в израза x + y, знакът за добавяне се използва за сумиране на стойностите на променливите x и y. По-малко известно е, че това заимствано от математическо наименование, наречено infix notation, всъщност е голям проблем за машините. Такъв оператор взема като вход две стойности, написани отляво и отдясно на него. При програмирането обозначенията с операционни знаци не са задължителни. Например, x + y може да бъде написана като функция за добавяне (x, y), към която компилаторът в крайна сметка конвертира нотацията на infix. Въпреки това, всеки знае много добре, че математиката не използва аритметични изрази, които формират един вид вътрешен мини-език на почти всеки програмен език.

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

Първият наистина успешен език на програмиране на Фортран стана така, защото аритметичните изрази (т.е. формулите) в него бяха преобразувани (преведени) в код, откъдето се нарече FORMULA TRANSlation. Преди това те трябваше да бъдат записани например под формата на функции за добавяне (а, умножаване (b, c)). В Kobol проблемът с въвеждането на автоматично преобразуване на формули се смяташе за много труден, тъй като програмистите трябваше да пишат неща като 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.

Редът, по който операторите трябва да бъдат изчислени, изисква дълго запаметяване. Поради това, учениците, които започват да учат аритметика, често получават погрешни резултати, дори и в действителност операциите да се извършват правилно. Необходимо е да се разбере постепенно реда на действията на операторите. Първо, трябва да се извършат действията в скоби, след това умножение и разделяне и накрая добавяне и изваждане. Но съществуват и други начини за писане на математически изрази, тъй като индексното означение е само един от възможните "малки езици", които могат да се добавят към по-големите.

Префикс и постфикс

Двете най-популярни алтернативи са записването на оператор преди или след неговите операнди. Те са известни като номера за префикс и постфикс. Логичът Ян Лукашевич изобретил първия от тях през 20-те години. Той живее в Полша, така че рекорда се нарича полски. Postfix версията, съответно, се нарича обратна полска нотация (ARF). Единствената разлика между двата метода е посоката, в която да се чете записът (от ляво на дясно или от дясно на ляво), така че е достатъчно да разгледаме само един от тях в детайли. В ареста, операторът е написан след неговите операнди. По този начин изразът AB + е пример за обратна полски запис за А + В.

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

Непосредственото предимство на означението е, че то се обобщава от n-adic оператор, а индексът за означаване действително работи само с два операнда, т.е. поради своя характер е подходящ само за двоични операции. Например, ABC @ е обратната полски експресията използване триадична марка, която е максималната стойност на А, В и С. В този случай операторът действа отляво на три самата операнд и съответства @ функция повикване (А, В, С). Ако се опитате да напишете символа @ като инфил, например A @ BC или нещо подобно, тогава става ясно, че това просто не работи.

Приоритет се дава от поръчката

Обратното вписване в Полша има друго предимство, тъй като приоритетът на операторите може да бъде представен по реда на тяхното появяване. В този случай, никога няма да са необходими скоби, въпреки че те могат да бъдат включени като символи за транзакции, за да се улесни преобразуването с индексно означение. Например, AB + C * е един еквивалентен еквивалент (A + B) * C, тъй като умножението не може да бъде изчислено до прибавянето, което дава втория операнд за операцията за умножение. Това означава, че ако AB + C * се изчислява за един оператор наведнъж, тогава получаваме A B + C * -> (A B +) * C -> (A + B)

Алгоритъмът за изчисляване

В 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) изчислението е завършено, резултатът е в горната част на стека.

Този алгоритъм на обратния полски запис може да бъде проверяван многократно, но всеки път ще работи, без значение колко сложен е аритметичният израз.

Задържащото устройство и стека са тясно свързани. Горният пример показва как паметта може да се използва за изчисляване на стойността в обратната полска нотация. По-малко е очевидно, че можете да използвате стека, като преобразувате стандартните индекси на индексите в задържане.

Примери в езиците за програмиране

На езика Pascal, обратният полски запис се изпълнява приблизително по този начин (част от програмата е дадена).

За да четете числа и оператори в цикъл, се извиква процедура, която определя дали символът е знак за номер или операция. В първия случай стойността се записва в стека, докато във втория случай съответното действие се изпълнява на първите два номера на стека и резултатът се записва.

toktype: = num;

прочетете (c);

ако в [`+`, `-`, `*`, `/`] след това започнете

ако eoln тогава cn: = `` друго четене (cn);

ако cn = `тогава

случай с

`+`: toktype: = add- `-`: toktype: = sub;

`*`: toktype: = мул- `/`: toktype: = div

край

Иначе започвайте

ако c = `-` тогава sgn: = -1 друга грешка: = s <> "+";

с: = cn

край

приключи;

ако (не грешка) и (toktype = num) тогава getnumber;

ако токтипе <> num започва тогава

y = = roorx = = rop;

ако не и грешка

дело toktype на

добавете: z: = x + y-sub: z: = x-y-mul: z: = x * y-div:

край

бутане (z);

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

за (s = strtok (s, w) -s-s = strtok (0, w)) {

а = струп (s, д);

ако (e> s) натиснете (a);

#define rpnop (x) printf ("% s:", * s), b = pop (), a =

else ако (* s == `+`) rpnop (a + b);

else ако (* s == `-`) rpnop (a - b);

else ако (* s == `*`) rpnop (a * b);

else ако (* s == `/`) rpnop (a / b);

#undef rpnop

}

Хардуерни реализации

В онези дни, когато компютърната технология беше много скъпа, се смяташе за добра идея да се принудят хората да използват OPN. През 60-те години на 20-ти век, както днес, беше възможно да се купят калкулатори, които работят в обратен полски запис. За да добавите 2 и 3 в тях, въведете 2, след това 3 и натиснете бутона плюс. На пръв поглед, входните операнди на оператора изглежда сложен и труден да се помни, но след известно време някои от тях са пристрастени към този начин на мислене и не можеше да разбере защо другите настояват за глупав пъхам, което е толкова сложно и така е ограничен.

Бъроуз дори построи мейнфрейм, който нямаше друга RAM, освен стека. Единственото нещо, което машината направи, беше да приложи алгоритми и методи за обръщане на полския запис до централния стак. Всички операции бяха разглеждани като OPN оператори, чието действие се разшири до n горни стойности. Например командата Return получи адрес от горната част на стека и т.н. Архитектурата на тази машина беше проста, но не достатъчно бърза, за да се конкурира с по-общите архитектури. Мнозина обаче все още съжаляват, че такъв прост и елегантен подход към изчисленията, където всяка програма е израз на OPN, не намира своето продължение.

По едно време калкулаторите с обратен полски запис бяха популярни, а някои все още предпочитат тях. Освен това са разработени и стека ориентирани езици като Forth. Днес тя се използва малко, но все пак причинява носталгия от страна на бившите потребители.

И така, какъв е смисълът на шега за завръщането на полската наденица?

Ако смятате оператора на колбаси, а след това в инфо забележка, той трябва да бъде в ролката, както при нормално горещо куче. В обратния полски запис, той е отдясно на двете половини, готови да ударят между тях след изчислението. Сега започва най-трудната част - горчица. Вече е на салам, т.е. той вече е изчислен като unary оператор. Има мнение, че горчицата също трябва да бъде показана като неопределена и следователно трябва да бъде преместена отдясно на наденицата ... Но може би ще се наложи твърде много стакове ...