РПН: алгоритам, поступци и примери

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

инфикс

Све програмери, и већина су студенти упознати са употребом оператора. На пример, вредности израз к + сумарно за променљиве к и и половну плус знака. Мање позната је чињеница да је ово позајмљена из математике нотација, названа инфиксна нотација, у ствари, представља велики проблем за машине. Овај оператер прима као улазне су две вредности забележен на лево и десно. У програмирању нотација опционо користе са знакова операције. На пример, к + и може се написати као функција набора (к, и), у којој преводилац и евентуално претвара инфиксна нотација. Међутим, сви знају да је математика је превише добра да не користите аритметичке изразе, који чине неку врсту унутрашњег мини-језика у скоро сваком програмском језику.

формула транслатор

Први велики успех ФОРТРАН програмски језик је постао толико углавном због тога што је аритметичка израз (нпр формулу ..) конвертован (емитовање) у коду, отуда и назив тога - формула превод. Пре тога, они су морали да пишу, на пример, искључен у форми функција (и множите (б, ц)). У ЦОБОЛ проблем спровођења аутоматског формулу за конверзију се сматра веома тешко, јер су програмери морали да пишу такве ствари Адд А до Б Мутлипли Ц.

Шта није у реду са инфик?

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

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

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

Два од најпознатијих алтернатива је да се забележи оператера пре или после његове операнди. Они су познати као префикс и постфик нотација. Логичар Ан Лукасевицх изумео први у 1920. Он је живео у Пољској, тако да је записник се зове пољски. Постфик верзија, односно, под називом обрнута пољска нотација (АБИ). Једина разлика између ова два метода је правац у коме се прочита записник (с лева на десно или десна на лево), тако да је довољно да се размотри детаљно само један од њих. ОПН оператер је написано после његове операнди. Стога, израз АБ + представља пример РПН за А + Б.

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

Непосредни Предност ознакама је да сумира оператера н-адске и инфиксна нотација заиста ради само са два операнда т. Д. су сами по себи погодна само за бинарне операције. На пример, АБЦ @ је обрнута пољски израз користећи тријадична знак који је максимална вредност А, Б и Ц. У овом случају оператор делује на левој три самог операнд и одговара функцију позива @ (А, Б, Ц). Ако покушате да напишете @ симбол као инфик, као што је @ пне или нешто слично, постаје јасно да то једноставно не ради.

Приоритет дат по налогу

РПН има још једну предност, што је приоритет оператора може бити представљена по редоследу њиховог појављивања. Истовремено, никада требати потпора, иако могу бити укључени као знакова операције како би се олакшало конверзију из инфиксна нотација. На пример, АБ + Ц * - недвосмислена еквивалент (А + Б) * Ц, тако да множење не може израчунати све додавањем извршене, што даје други операнд за множење. То јест, ако израчуната АБ + Ц * би једног оператора у датом тренутку, добијамо АБ + Ц * -> (АБ +) * Ц -> (А + Б) * Ц.

цалцулатион алгоритам

Оператер ОПН изгледа исто као функција која узима као писане аргументе две вредности на њеном леве стране. Осим тога, то је природно нотација за употребу у програмских језика, као начин његовог обрачуна одговара операцијама стацк а потреба за парсирање је елиминисана. На пример, затварач у изразу 5 +6 * 7 ће се појавити као 5, 6, 7 *, +, и може се једноставно израчунати скенирањем са лева на десно и писати вредности наслагане једна на другу. Кад год заједнички знак операције, изабран од стране горњег елемента 2 меморију рачунара, оператор се користи и као резултат се вратио у меморију. Када ће крајњи резултат израза израчунавања бити у врху стека.

На пример:

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

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

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

Примери програмских језика

Паскал РПН схватио овако (показује део програма).

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

токтипе: = нум;

реад (с);

ако ц ин [ '+', '-', '*', '/'] тхен бегин

ако еолн онда ЦН: = '' друго реад (ЦН);

ако ЦН = '' онда

случају

'+': Токтипе: = адд; '-': токтипе: = суб;

'*': Токтипе: = мул; '/': Токтипе: = Див

крај

елсе бегин

ако је а = '-' онда СГН: = -1 друго еррор: = ц <> '+';

с: = ЦН

крај

енд;

ако (не грешка) и (токтипе = Број) онда гетнумбер;

ако токтипе <> Број тхен бегин

и = поп; к: = поп;

ако не еррор онда

Случај токтипе од

адд: з: = к + и; суб: з: = к-и; мул: з: = к * и; див: з: = к / и

крај

пусх (з);

Ц-имплементација РПН (приказан део програма):

фор (и = стрток (с, в); С; с = стрток (0, в)) {

а = стртод (с, & е);

ако (Е> а) Пусх (А);

#дефине рпноп (к) принтф ( "% ц", * с), б = поп (), а = поп (), пусх (к)

иф (* с == '+') рпноп (а + б);

иф (* с == '-') рпноп (а - б);

елсе иф (* с == '*') рпноп (а * б);

иф (* с == '/') рпноп (а / б);

#ундеф рпноп

}

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

У тим данима, када је компјутерска технологија била веома скупа, сматрало се као добра идеја да натера људе да користе одводници пренапона. У 1960-их година., Као и сада, било је могуће купити калкулатора, који раде у обрнутом пољском нотацији. Да би додали 2 и 3 од њих мора да уђе 2, па 3, па притисните дугме "плус". На први поглед, улазни операнди до оператера изгледало компликовано и тешко да се сетим, али после неког времена неки су овисни о овом начину размишљања и не може да разуме зашто су остали инсистирају на глупој инфик, која је тако компликовано и тако је ограничен.

Бароуз компанија чак гради маинфраме, који је имао никакву другу меморију, осим гомиле. Једина ствар која чини машину - применио алгоритме и методе РПН на централном стека. Све њене операције су сматрани пренапона оператера, који се односи на горње вредности н. На пример, тим је повратна адреса са врха стека, и тако даље. Д. архитектура такве машине је једноставна, али не довољно брзо да се такмиче са уобичајених архитектуре. Многи, међутим, још увек жао што тако једноставна и елегантна приступ рачунарства где сваки програм је био израз ОПН, нашао његов наставак.

Оне тиме калкулатори са РПН били популарни, и неки људи им и даље дају предност. Поред тога, они су развили гомилу оријентисаних језика, као што је напред. Данас је мало користи, али ипак носталгични од његових бивших корисника.

Дакле, шта је смисао шале о Обрнуто пољске кобасице?

Ако претпоставимо да је оператор кобасица је инфиксна нотација, требало би да буде у ролне, као у конвенционалном хот дог. РПН се налази у праву у две половине Спремите се између њих након обрачуна. Сада долази тежи део - сенф. Она је већ на кобасице, Т. Д. Већ обрачунава као Унарни оператор. Верује се да сенф такође треба приказати као унцалцулатед и стога треба померити на десно од кобасице ... Али могуће је, то би захтевало превелику гомилу ...