RPN: алгоритъм, методи и примери

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

пъхам

Всички програмисти, както и повечето студенти са запознати с използването на оператори. Например, стойностите на експресия х + сумиране на променливите х и у използвани знака плюс. Малко известен е фактът, че това е заимстван от математика бройна система, наречена инфикс бройна система, в действителност, е голям проблем за машините. Този оператор получава като входни две стойности се записват в ляво и дясно. В програмиране означения избор с признаци операции. Например, х + у могат да бъдат написани като функция на прегъване (х, у), при което компилатор и в крайна сметка се превръща въвирам нотация. Въпреки това, всеки знае, математиката е прекалено хубаво, за да не се използват аритметични изрази, които представляват един вид вътрешен мини език в почти всеки език за програмиране.

формула преводач

Първият наистина успешен езика Fortran програмиране е станала толкова голяма степен, тъй като аритметичен израз (т.е. формула ..) Това превръща (излъчване) в кода, откъдето идва и името му - Формула превод. Преди това те трябваше да се напише, например, сгънати във формата на функции (и да се размножават (б, в)). В COBOL проблем на изпълнителните автоматична формула преобразуване се счита за много трудно, защото програмистите трябваше да пишат такива неща Добави А до точка Б Mutliply Чрез В.

Какво не е наред с инфикс?

Проблемът е, че операторите имат такива свойства като предимство и асоциативност. Поради това, определянето на инфикс функция става не е тривиална задача. Например, умножение има по-висок приоритет от прибавяне или изваждане, което означава, че израз 2 + 3 * 4 не е равно на сумата от 2 и 3, умножена по 4, тъй като това би било в изпълнение на операторите, от ляво на дясно. В действителност, умножете 3 от 4 и добавете 2. Този пример показва, че изчисляването на изразяването на инфикс често изисква промяна в реда на оператори и операнди. Освен това, е необходимо да се използват скоби, за да изглежда по-ясно означаване. Например, (2 + 3) * (4 + 5) не може да се запише без скобите, защото 2 + 3 * 4 + 5 означава, че трябва да се размножават 3 от 4 и се добавят 2 и 5.

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

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

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

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

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

Приоритетът по реда

RPN има още едно предимство в това, че приоритет на операторите могат да бъдат представени по реда на тяхното появяване. В същото време никога не се нуждаят тиранти, въпреки че те могат да бъдат включени като герои операции за да се улесни преминаването от инфикс нотация. Например, АВ + C * - недвусмислено еквивалент (А + В) * С, така че размножаването не може да бъде изчислена, докато добавянето извършва, което дава втори операнд за умножение. Това е, ако изчисленото AB + С * от един оператор в момент, ние се AB + C * -> (AB +) * C -> (А + В) * С

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

Операторът на OPN изглежда по същия начин, като функция, която взима като аргументи две стойности, написани на лявата си. В допълнение, той е естествен нотация за използване на програмни езици, като начина на изчисляването му съответства на операциите по стека и необходимостта от разбор се елиминира. Например, отвода в израза 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) Изчисляване е завършена, резултатът се съхранява в горната част на стека.

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

OPN и стекове са тясно свързани. Този пример показва как да използвате паметта за изчисляване на стойността на обратната полски нотация. По-малко очевидно е, че можете да използвате стека, конвертиране на стандартно израз пъхам в остра бъбречна недостатъчност.

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

Паскал RPN реализира така (показва част от програмата).

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

toktype: = бр;

Прочети (и);

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

ако eoln след КН: = '' да ти чете (CN);

ако CN = '' след това

случай на

"+": Toktype: = добави; '-': toktype: = подгрупа;

"*": Toktype: = MUL; '/': Toktype: = Разделение

край

друг да започне

ако а = '-' след SGN: = -1 друг грешка: = С <> "+";

с: = CN

край

приключи;

ако (не грешка) и (toktype = NUM) след getnumber;

ако toktype <> бр след това да започне

у = поп; х: = поп;

ако не и след това грешка

При toktype на

добави: Z: = х + у; Под: Z: = X-Y; MUL: Z: = X * Y; DIV: Z: = X / Y

край

тласък (Z);

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

за (S = strtok (S, т); S; S = strtok (0, т)) {

а = strtod (S, и д);

ако (д> и) тласък (а);

# определят rpnop (х) ФОРМАТ ( "% в:", * а), б = поп (), а = поп (), тласък (х)

иначе, ако (* S == '+') rpnop (А + В);

иначе, ако (* S == '-') rpnop (а - Ь);

иначе, ако (* S == '*') rpnop (а * б);

иначе, ако (* S == "/") rpnop (а / Ь);

#undef rpnop

}

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

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

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

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

И така, какво е значението вицове за обратен полски колбаси?

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