RPN: algoritme, metodes en voorbeelde

RPN gevorm wanneer die basis van 'n rekenaarprogrammeerder in die wêreld. Vandag is dit nie so goed bekend. Daarom, komiese illustrasie, uitbeelding van 'n "reverse" Poolse worsbroodjies buite, kan nog steeds misverstaan deur sommige kundige programmeerders. Nie baie goed verduidelik die grap, maar in hierdie geval sal dit ten volle geregverdig wees.

voeg sels

Alle programmeerders, en die meeste studente vertroud is met die gebruik van operateurs. Byvoorbeeld, die uitdrukking x + opsomming waardes vir die veranderlikes x en y gebruik plus teken. Minder bekende is die feit dat dit geleen van wiskunde notasie, genoem voeg sels notasie, in werklikheid, is 'n groot probleem vir die masjiene. Dit operateur ontvang as insette twee waardes is aangeteken op die links en regs. In programmering gebruik notasie opsioneel met tekens bedrywighede. Byvoorbeeld, kan x + y geskryf word as 'n funksie van vou (x, y), waarin die samesteller en uiteindelik vat voeg sels notasie. Maar almal weet die wiskunde is te goed rekenkundige uitdrukkings, wat 'n soort van interne mini-taal vorm in amper elke programmeertaal gebruik te maak nie.

formule vertaler

Die eerste werklik suksesvolle Fortran programmeertaal geword so grootliks omdat die rekenkundige uitdrukking (dws formule ..) Dit omskep (uitgesaai) in die kode, vandaar die naam daarvan - Formule vertaling. Voor dit, het hulle om te skryf, byvoorbeeld, gevou in die vorm van funksies (en vermeerder (b, c)). In COBOL probleem van die implementering van 'n outomatiese omskakeling formule was beskou as baie moeilik omdat die programmeerders het om dinge soos by A na B Mutliply Deur C. skryf

Wat is verkeerd met voeg sels?

Die probleem is dat die operateurs het sulke eiendomme soos voorrang en associativity. As gevolg van hierdie, die definisie van infix funksie word nie-triviale taak. Byvoorbeeld, vermenigvuldiging het hoër voorrang as optelling of aftrekking, wat beteken dat die uitdrukking 2 + 3 * 4 is nie gelyk aan die som van 2 en 3, vermenigvuldig met 4, as dit in die prestasie van die operateurs sal wees van links na regs. Trouens, vermenigvuldig 3 deur 4 en voeg 2. Hierdie voorbeeld illustreer dat die berekening van die voeg sels uitdrukking dikwels vereis 'n verandering in die volgorde van operateurs en operande. Daarbenewens is dit nodig om draadjies gebruik om meer duidelik notasie kyk. Byvoorbeeld, kan (2 + 3) * (4 + 5) nie geskryf word sonder die hakies, want 2 + 3 * 4 + 5 beteken dat jy nodig het om te vermeerder 3 deur 4 en voeg 2 en 5.

Die volgorde waarin jy die operateurs te bereken vereis 'n lang onthou. As gevolg van hierdie, studente wat begin om rekenkundige leer, dikwels kry die verkeerde resultate, selfs al is die werklike bedrywighede korrek uitgevoer word. Dit is nodig om die volgorde van optrede state leer deur die hart. In die eerste plek die aksie moet in hakies, dan vermenigvuldig en deel, en uiteindelik optel en aftrek gedra. Maar daar is nog 'n manier van die skryf van wiskundige uitdrukkings soos voeg sels notasie is slegs een van die moontlike "klein tale" wat meer kan bygevoeg word.

Voorvoegsel en postfix notasie

Twee van die mees bekende alternatiewe is om die operateur te teken voor of na sy operande. Hulle staan bekend as die voorvoegsel en postfix notasie. Logikus Yan Lukasevich uitgevind die eerste een in 1920. Hy het in Pole, so die rekord staan bekend as Pools. Postfix weergawe, onderskeidelik, genaamd Reverse Pools notasie (ARF). Die enigste verskil tussen die twee metodes is die rigting waarin die rekord te lees (van links na regs of van regs na links), so is dit voldoende om te oorweeg in detail net een van hulle. Die opn operateur is geskryf nadat sy operande. So, die uitdrukking AB + verteenwoordig 'n voorbeeld RPN vir A + B

Onbeperkte aantal operande

Die onmiddellike voordeel van notasie is dat dit 'n opsomming van die N-adische operateur en voeg sels notasie is regtig net werk met twee operande, t. E. inherent slegs geskik vir binêre operasies. Byvoorbeeld, ABC @ is die omgekeerde Pools uitdrukking met behulp van triadiese merk wat is die maksimum waarde van A, B en C. In hierdie geval is die operateur tree aan die linkerkant van die drie operand self en kom ooreen met 'n funksie oproep @ (A, B, C). As jy probeer om die @ simbool as voeg sels, skryf soos 'n @ BC of iets soos dit, word dit duidelik dat dit eenvoudig nie werk nie.

Die prioriteit gegee word deur die volgorde

RPN nog 'n voordeel in dat die prioriteit van die operateurs kan voorgestel word deur die einde van hul voorkoms. Terselfdertyd het nooit nodig draadjies, hoewel hulle kan ingesluit word as karakters bedrywighede om die omskakeling van infix notasie te fasiliteer. Byvoorbeeld, AB + C * - ondubbelsinnige ekwivalent (A + B) * C, so die vermenigvuldiging nie bereken kan word totdat die toevoeging uitgevoer, wat 'n tweede operand vir vermenigvuldiging gee. Dit is, indien die berekende AB + C * deur een operateur by 'n tyd, kry ons AB + C * -> (AB +) * C -> (A + B) * C.

berekening algoritme

Die opn operateur lyk dieselfde as 'n funksie wat neem as argumente twee waardes op haar linker geskryf. Daarbenewens is dit 'n natuurlike notasie vir gebruik in programmeertale, soos die gewoonte van die berekening stem ooreen met die stapel bedrywighede en die behoefte aan parsing word uitgeskakel. Byvoorbeeld, sal die dover in die uitdrukking 5 + 6 * 7 verskyn as 'n 5, 6, 7 *, + en dit kan eenvoudig bereken deur die skandering van links na regs en skryf die waardes in 'n stapel. Wanneer 'n algemene teken van die operasie, wat deur die boonste element 2 van die rekenaar geheue, die operateur gebruik en die resultaat terug na geheue. Wanneer die eindresultaat van die berekening uitdrukking sal wees in die top van die stapel.

Byvoorbeeld:

• S = () 5, 6, 7, *, + 5 op die stapel geplaas.
• S = (5) 6, 7, *, + 6 op die stapel geplaas.
• S = (5, 6), 7 * 7 + plaas die stapel.
• S = (5, 6, 7), * 2 + kies waardes van die stapel, gebruik * en plaas die resultaat in die stapel.
• S = (5, 6 * 7) = (5, 42) + 2 waardes gekies uit die stapel, op die + van toepassing en sit die resultaat in die stapel.
• S = (5 + 42) = (47) berekening voltooi, die resultaat is gestoor in die top van die stapel.

Hierdie algoritme kan herhaaldelik nagegaan RPN, maar elke keer as dit sal werk, maak nie saak hoe kompleks die rekenkundige uitdrukking.

Opn en stapels is nou gekoppel. Hierdie voorbeeld toon hoe om die geheue te gebruik om die waarde van die omgekeerde Pools notasie te bereken. Minder voor die hand liggend is dat jy die stapel kan gebruik, herlei van standaardeenhede voeg sels uitdrukking in akute nierversaking.

Voorbeelde van programmeertale

Pascal RPN besef dit soos (toon die deel van die program).

Om die getalle en operateurs lees in die siklus genoem prosedure, wat bepaal of die teken nommer of teken operasie. In die eerste geval, is die gestoor in die stapel waarde, en die tweede van die twee boonste stapel getalle ooreenstemmende aksie uitgevoer en die resultaat word gestoor.

toktype: = num;

lees (s);

As c in [ '+', '-', '*', '/'] dan begin

as dan eoln CN: = '' anders lees (CN);

As CN = '' dan

geval van 'n

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

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

einde

anders begin

As a = '-' toe SGN: = -1 anders fout: = c <> '+';

met: = cn

einde

eindig;

indien (nie fout) en (toktype = num) dan getnumber;

As toktype <> num dan begin

y = pop; x: = pop;

Indien nie fout dan

geval toktype van

voeg: z: = x + y; sub: z: = x-y; MUL: z: = x * y; div: z: = x / y

einde

druk (Z);

C-implementering RPN (getoon deel van die program):

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

a = strtod (s, & e);

indien (e> s) druk (a);

# define rpnop (x) printf ( "% c:", * s), b = pop (), 'n = pop (), druk (x)

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

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

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

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

#undef rpnop

}

hardeware implementering

In dié dae toe rekenaartegnologie was baie duur, is dit gedink 'n goeie idee om mense te dwing om stuwingsafleiers gebruik. In 1960-er jare., Soos nou, was dit moontlik om die sakrekenaars, wat werk in omgekeerde Pools notasie te koop. Om by te voeg 2 en 3 van hulle moet 2, dan 3 betree, en druk die "plus" knoppie. Met die eerste oogopslag, die insette operande om die operateur gelyk ingewikkeld en moeilik om te onthou, maar na 'n ruk 'n paar is verslaaf aan hierdie manier van dink en kon nie verstaan waarom die ander dring aan op dom voeg sels, wat is so ingewikkeld en so is beperk.

Burroughs maatskappy selfs gebou 'n mainframe, wat geen ander geheue gehad, behalwe stapel. Die enigste ding wat die masjien maak - toegepas die algoritmes en metodes RPN om die sentrale stapel. Al sy bedrywighede beskou as arresters operateurs, wat van toepassing is op die boonste N waardes. Byvoorbeeld, die span het die Adres van die top van die stapel, en so aan. D. Die argitektuur van so 'n masjien was eenvoudig, maar nie vinnig genoeg om te kompeteer met die meer algemene argitektuur. Baie het egter nog spyt die feit dat so 'n eenvoudige en elegante benadering tot rekenaar waar elke program was 'n uitdrukking van opn, gevind die voortsetting daarvan.

Een keer sakrekenaars met RPN was baie gewild, en 'n paar mense nog gee hulle voorkeur. Daarbenewens ontwikkel hulle 'n stapel georiënteerde tale, soos meer. Vandag is dit min gebruik word, maar nog nostalgiese van sy voormalige gebruikers.

So, wat is die betekenis grappies oor Reverse Pools wors?

As ons aanvaar dat die operateur van die wors, die infix notasie, dit moet binne die rol wees as in konvensionele warm hond. Die RPN is geleë reg in twee helftes om gereed te wees therebetween na berekening. Nou kom die moeilike deel - mosterd. Sy is reeds op die wors, t. E. Reeds bereken as 'n unêre operateur. Daar word geglo dat mosterd ook moet getoon word as uncalculated en moet dus verskuif na die regterkant van die wors ... Maar dit is moontlik, sal dit ook 'n groot stapel van vereis ...