RPN: algoritme, wurkfoarmen en foarbylden

RPN ienris foarme de basis fan in kompjûterprogrammeur yn 'e wrâld. Tsjintwurdich wurdt it net sa goed bekend. Dêrom, comic yllustraasje, ôfbyldzjen fan in "reverse" Poalsk worst rollen bûten, kinne noch ferkeard begrepen te wurden troch guon saakkundich programmeurs. Net hiel goed útlizze de grap, mar yn dit gefal wurdt it folslein terjochte.

infix

Alle programmeurs, en de measte studinten binne bekend mei it brûken fan de operators. Bygelyks, de útdrukking x + summation wearden foar de fariabelen x en y used plus teken. Minder bekend is it feit dat dit is ûntliend wiskunde notaasje, neamd infix notaasje, yn feite, is in grut probleem foar de masines. Dit operator krijt as ynput twa wearden binne opnommen op links en rjochts. Yn Programming muzyknotaasje brûkt mooglik mei buorden operaasjes. Bygelyks, x + y skreaun wurde kin as in funksje fan fold (x, y), wêryn de gearstaller en úteinlik konvertearret infix notaasje. Lykwols, elkenien wit it wiskunde is te goed net te brûken rekkenkunde útdrukkings, dy't foarmje in soarte fan ynterne mini-taal yn hast alle programmeartaal.

formule oersetter

De earste echt suksesfol Fortran programmeartaal is wurden dus foar it grutste part om't de rekkenboek útdrukking (dws formule ..) It bekearde (útstjoering) yn 'e koade, dêrfandinne de namme fan it - Formula oersetting. Foarôfgeand oan dat, hja moasten skriuwe, bygelyks, gear yn 'e foarm fan funksjes (en formannichfâldigje (b, c)). Yn COBOL probleem fan útfiering automatyske conversion formule is beskôge hiel lestich omdat de programmeurs moasten skriuwen saken lykas Add A To B Mutliply By C.

Wat is der mis mei infix?

It probleem is, dat de operators hawwe sokke eigenskippen as foarrang en associativity. Fanwege dit, de definysje fan infix funksje wurdt net-triviale taak. Bygelyks, fermannichfâldigjen hat heger streekje foar as oanfolling of subtraction, wat betsjut dat de útdrukking 2 + 3 * 4 is net lyk oan de som fan de 2 en 3, fermannichfâldige mei 4, sa't it soe wêze yn 'e foarstelling fan' e eksploitanten fan links nei rjochts. Yn feite, fermannichfâldigje 3 by 4 en heakje 2. Dit foarbyld yllustrearret dat de berekkening fan 'e infix útdrukking faak freget om in feroaring yn' e folchoarder fan operators en operands. Dêrneist is it nedich om te brûken beugels te sjen mear dúdlik notaasje. Bygelyks, (2 + 3) * (4 + 5) kin net skreaun wurde sûnder de heakjes, om't 2 + 3 * 4 + 5 betsjut dat jo moatte fermannichfâldigje 3 by 4 en heakje 2 en 5.

De folchoarder wêryn jo wolle calcular operators fereasket in lang ûnthâlde. Fanwegen dit, studinten dy't begjinne te learen rekkenkunde, faak krije it ferkearde resultaten, sels as de werklike operaasjes wurde útfierd korrekt. It is needsaaklik om te learen de folchoarder fan aksje útspraken troch hert. Earst, De aksje moat wurde útfierd tusken heakjes, dan fermannichfâldigjen en dieling, en by einsluten oanfolling en subtraction. Mar der is in oare wize fan skriuwen wiskundige uteringen as infix notaasje is mar ien fan de mooglike "lytse talen" dat kin tafoege wurde oan mear.

Foarheaksel en Postfix notaasje

Twa fan 'e meast ferneamde alternativen bestiet út it fêstlizzen fan de operator foar of nei syn operands. Se binne bekend as it foarheaksel en Postfix notaasje. Dialektyk Yan Lukasevich betocht de earste ien yn 1920. Hy wenne yn Poalen, dus it rekôr wurdt neamd Poalsk. Postfix ferzje, respektivelik, neamd Reverse Poalsk It opskriuwen (ARF). It iennige ferskil tusken dizze twa metoaden is de rjochting wêryn te lêzen trochslach (fan lofts nei rjochts of rjochts nei lofts), dus it folstiet en beskôgje yn detail mar ien fan harren. De OPN operator is skreaun nei syn operands. Sa, de útdrukking AB + fertsjintwurdiget in foarbyld RPN foar A + B.

In ûneinich tal operands

De direkte foardiel fan de skriuwwize is dat it fettet de n-adic operator en infix skriuwwize is eins allinnich wurket mei twa operands, t. E. Binne djip geskikt allinnich foar binêre operaasjes. Bygelyks, ABC @ is it tsjinoerstelde Poalske útdrukking mei help triadic mark dat is de maksimale wearde fan it A, B en C. Yn dat gefal wurdt de operator beslút, op lofts fan 'e trije operand sels en oerienkomt mei in funksje oprop @ (A, B, C). As jo besykje te skriuwen de @ symboal as infix, lykas A @ BC of sokssawat, wurdt dúdlik dat it gewoan net wurket.

De prioriteit jûn troch de opdracht

RPN hat noch in foardiel oan dat de prioriteit fan de ûndernimmers kin wurde fertsjintwurdige troch de opdracht fan harren uterlik. Tagelyk nea nedich beugels, hoewol't se meie wurde opnommen as karakters operaasjes te fasilitearjen de omsetting út fan infix notaasje. Bygelyks, AB + C * - unambiguous ekwivalint (A + B) * C, sadat it fermannichfâldigjen kin net berekkene oant de tafoeging útfierd, dat jout in twadde operand foar multiplication. Dat is, as it troch him berekkene AB + C * by ien operator op in tiid, we krije AB + C * -> (AB +) * C -> (A + B) * C.

berekkening algoritme

De OPN operator sjocht der itselde as in funksje dy't duorret as arguminten twa wearden skreaun op har linker. Dêrneist is it in natuerlike skriuwwize foar gebrûk yn programmearring talen, as de wize fan syn berekkening komt oerien mei de trochslach operaasjes en it ferlet fan it parsen is eliminearre. Bygelyks, de arrester yn de útdrukking 5 + 6 * 7 sil ferskine as in 5, 6, 7 *, +, en it kin berekkene gewoan troch it skennen fan links nei rjochts en skriuw de wearden yn in stapel. Alle kearen dat in mienskiplike teken fan funksjonearjen, selektearre troch de boppeste elemint 2 fan 'e kompjûter ûnthâld, de operator wurdt brûkt en it resultaat werom nei ûnthâld. Doe't de ein resultaat fan de berekkening útdrukking sil wêze yn 'e top fan de trochslach.

Bygelyks:

• S = () 5, 6, 7, *, + 5 pleatst op de trochslach.
• S = (5) 6, 7, *, + 6 pleatst op de trochslach.
• S = (5, 6), 7 *, 7 + plak de trochslach.
• S = (5, 6, 7), * 2 + kieze wearden út de trochslach, gebrûk * en pleats it resultaat yn de trochslach.
• S = (5, 6 * 7) = (5, 42) + 2 wearden selektearre út de trochslach, ta te passen op de + en sette it resultaat yn de trochslach.
• S = (5 + 42) = (47) berekkening is klear, it resultaat wurdt opslein yn 'e top fan de trochslach.

Dit algoritme kin wurde kontrolearre RPN herhaaldelijk, mar elke kear dat wurkje sil, gjin saak hoe kompleks de rekkenkunde útdrukking.

OPN en Stacks binne nau ferbûn. Dit foarbyld lit hoe te brûken fan it ûnthâld te berekkenjen de wearde fan 'e tsjinoerstelde Poalske notaasje. Minder fanselssprekkend is dat kinst gebrûk meitsje fan de steapel, it omsette standert infix útdrukking yn akute werom mislearjen.

Foarbylden fan de programmearring talen

Pascal RPN realisearre lykas dizze (lit it part fan it programma).

Om lêzen de oantallen en brûkers yn de syklus neamde proseduere, dy't bepaalt oft de token getal of teken operaasje. Yn it earste gefal, de wearde opslein yn de trochslach, en de twadde fan 'e beide boppeste stack nûmers oerienkommende aksje wurdt útfierd en it resultaat wurdt opslein.

toktype: = num;

lêzen (s);

as c yn [ '+', '-', '*', '/'] dan begjinne

as eoln dan cn: = '' oars lêzen (CN);

as cn = '' dan

gefal fan in

'+': Toktype: = add; '-': toktype: = sub;

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

ein

oars begjinne

As in = '-' dan FyN: = -1 oars flater: = c <> '+';

mei: = cn

ein

end;

as (net error) en (toktype = Num), dan getnumber;

as toktype <> num dan begjinne

y = Pop; x: = pop;

sa net error dan

case toktype fan

add: z: = x + y; sub: z: = x-y; Mul: z: = x * y; div: z: = x / y

ein

push (z);

C-útfiering RPN (oanjûn part fan it programma):

foar (s = strtok (s, w); s; s = strtok (0, w)) {

a = strtod (s, & e);

as (e> s) push (a);

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

oars as (* s == '+') rpnop (a + b);

oars as (* s == '-') rpnop (a - b);

oars as (* s == '*') rpnop (a * b);

oars as (* s == '/') rpnop (a / b);

#undef rpnop

}

hardware ymplemintaasje

Yn dy dagen, doe't computer technology wie tige djoer, waard tocht in goed idee om twinge minsken te brûken surge arresters. Yn 1960-ies., As no, it wie mooglik om te keapjen de rekkenmasines, dy't wurkje yn omkearde Poalsk notaasje. Om heakjen 2 en 3 fan harren moatte 2, dan 3, en druk op de "plus" knop. Op het eerste gezicht, de ynfier operands oan de operator like yngewikkelde en net maklik te ûnthâlden, mar nei in skoftke guon binne ferslave oan dizze wize fan tinken en koenen net begripe wêrom't de oaren tige belangryk fine dom infix, dat is sa yngewikkeld en sa is beheind.

Burroughs bedriuw sels boud in mainframe, dy hie gjin oar ûnthâld, útsein stack. It iennichste ding dat makket de masine - tapast de algoritmen en metoaden RPN ta de sintrale stack. Alle fan syn operaasjes waarden beskôge as arresters operators, dat jildt foar de boppeste n wearden. Bygelyks, de ploech naam it weromkommen Adres út 'e top fan' e steapel, ensafuorthinne. D. De arsjitektuer fan sa'n masine wie ienfâldich, mar net hurd genôch om te konkurrearje mei de mear mienskiplike Architectures. In protte, lykwols noch spijt it feit dat sa'n ienfâldige en elegante oanpak fan Computing dêr't alle programma wie in útdrukking fan OPN, fûn syn fuortsetting.

Ien kear rekkenmasines mei RPN wienen populêr, en guon minsken noch jaan harren foarkar. Boppedat, se ûntwikkele in steapel-rjochte talen, lykas Forth. Tsjintwurdich is it in bytsje brûkt, mar noch nostalgysk út syn eardere brûkers.

Dus wat is de betsjutting grappen oer Reverse Poalsk woarst?

As wy der fan út dat de eksploitant fan de worst, de infix notaasje, it moat binnen de rol as yn konvinsjonele hot hûn. It RPN leit rjocht yn twa helten krije klear therebetween nei berekkening. No komt it drege part - moster. Se is al op 'e worst, t. E. al berekkene as in unary operator. Oannomd wurdt dat mosterd moat ek te sjen wêze as uncalculated en dêrom moat ferpleatst wurde nei it rjocht fan de woarst ... Mar it is mooglik, dat soe nedich te grut steapel ...