RPN: algoritm, meetodid ja näited

RPN kord olid aluseks programmeerija maailmas. Täna ei ole nii hästi teada. Seetõttu koomiline illustratsioon, mis kujutab "reverse" Poola vorsti rullides väljaspool, saab veel valesti mõned asjatundlikud programmeerijad. Mitte väga hästi seletada nali, kuid sel juhul on see täiesti õigustatud.

Siseliidete

Kõik programmeerijad, ja enamik õpilasi on tuttav kasutamine operaatorid. Näiteks väljend x + liitmise väärtused muutujate x ja y kasutatud plussmärk. Vähem tuntud on asjaolu, et see on laenatud matemaatika märge, mida nimetatakse Siseliidete märge tegelikult on suur probleem masinatega. See operaator võtab sisendina salvestatakse kaks väärtust vasakul ja paremal. Programmeerimiskoodis tähistusena kasutatakse valikuliselt märkidest operatsioone. Näiteks x + y saab kirjutada funktsioonina korda (x, y), milles koostaja ja lõpuks muundab Siseliidete märke. Kuid igaüks teab matemaatika on liiga hea mitte kasutada matemaatilisi, mis moodustavad omamoodi sisemise mini-keelt peaaegu iga programmeerimiskeelt.

valemiga tõlkija

Esimene tõeliselt edukas Fortran programmeerimiskeelt on muutunud nii suures kuna aritmeetiline ekspressiooni (st valemi ..) See muundatakse (saade) kood, seega nimeks - Formula tõlge. Enne seda oli neil kirjutada, näiteks volditud kujul funktsioone (ja korrutada (b, c)). In COBOL rakendamise probleemidele automaat Ümberarvestusvalem peeti väga raske, sest programmeerijad tuli kirjutada asju Lisa A punkti B Mutliply C.

Mis on valesti Siseliidete?

Probleem on, et operaatorid on sellised omadused nagu tähtsam ja assotsiatiivsuse. Selle tõttu mõiste Siseliidete funktsioon muutub mitte-triviaalne ülesanne. Näiteks, korrutamine on kõrgem tähtsamaks kui lisamine või lahutamine, mis tähendab, et väljend 2 + 3 * 4 ei võrdu summaga 2 ja 3, mis on korrutatud 4, sest see oleks täitmisel operaatorite vasakult paremale. Tegelikult korrutada 3 4 ja lisage 2. See näide illustreerib, et arvutamise Siseliidete ekspressiooni sageli vaja muutust, et ettevõtjate ja operandi. Lisaks on vaja kasutada traksid vaadata rohkem selge märge. Näiteks (2 + 3) * (4 + 5) ei saa kirjutada ilma sulgudes, sest 2 + 3 * 4 + 5 tähendab, et teil on vaja korrutada 3 4 ja lisada 2 ja 5.

Järjekord, milles soovite arvutada operaatorid nõuab pikka mäleta. Sellepärast õpilast, kes hakkavad õppima aritmeetika, sageli saada vale tulemusi, isegi kui tegelikku toimingut ei tehta õigesti. On vaja õpetada, et hagi avaldused peast. Esiteks tuleb hagi läbi sulgudes, siis korrutamine ja jagamine, ja lõpuks liitmise ja lahutamise. Kuid on veel üks viis kirjalikult matemaatilisi avaldisi nagu Siseliidete märge on ainult üks võimalik "väikeste keelte", mida saab lisada rohkem.

Eesliide ja postfix märge

Kaks kõige tuntud alternatiive on jäädvustada operaator enne või pärast oma operandi. Nad on tuntud kui eesliide ja postfix märge. Loogik Yan Lukasevich leiutatud esimene 1920. aastal. Ta elas Poolas, nii et rekord nimetatakse Poola. Postfixi versioon, vastavalt nn tagurpidi Poola Märge (ARF). Ainus erinevus nende kahe meetodi vahel on suund, mis lugeda rekord (vasakult paremale või paremalt vasakule), nii et see on piisav, et kaaluda üksikasjalikult ainult üks neist. OPN operaator on kirjutatud pärast selle operandi. Seega väljend AB + kujutab näitena RPN A + B

Piiramatu arv operandi

Vahetus ära märge, et see kokkuvõte n-adic operaator ja Siseliidete märge on tõesti töötab ainult kaks operandi, t. E. on oma olemuselt sobib ainult binaartoiminguid. Näiteks ABC @ on vastupidine Polish ekspressiooni lehe triaadiline kaubamärk, mis on kõrgeim väärtus A, B ja C. Sellisel juhul operaator tegutseb vasakul kolme operandi ennast ning vastab funktsioon kõne @ (A, B, C). Kui proovite kirjutada @ sümbol nagu Siseliidete nagu @ BC või midagi sellist, selgub, et see lihtsalt ei tööta.

Kui prioriteetseks järjekorras

RPN on teine eelis, et prioriteet operaatorid võivad olla esitatud järjekorras nende välimust. Samal ajal ei pea kunagi traksid, kuigi nad võivad olla ka märke tegevuse hõlbustamiseks konverteerimine Siseliidete märge. Näiteks AB + C * - ühemõtteline ekvivalent (A + B) * C, nii mitmekordistumine ei ole võimalik arvutada kuni Lisaks teostati, mis annab teise operandi paljundamiseks. See tähendab, et kui arvutatud AB + C * ühe operaatori ajal, saame AB + C * -> (AB +) * C -> (A + B) * C.

arvutamise algoritmi

OPN operaator näeb sama funktsioon, mis võtab argumentideks kaks väärtust kirjutatud tema vasakul. Lisaks on looduslik märge kasutamiseks programmeerimiskeeli, nõnda nagu tema arvutus vastab virna operatsioonide ja vajadust sõelumisel on kõrvaldatud. Näiteks peataja väljendis 5 + 6 * 7 ilmub 5, 6, 7 * +, ja see saab arvutada lihtsalt skaneerimine vasakult paremale ja kirjutada väärtused virna. Kui ühine märk operatsiooni poolt valitud ülemine element 2 arvuti mälu, operaator kasutatakse ja tulemus tagastatakse mälu. Kui lõpuks arvutuse tulemusena väljend olla magasini tippu.

Näiteks:

• S = () 5, 6, 7, *, + 5 asetatakse virna.
• S = (5) 6, 7, *, + 6 avaldatud virna.
• S = (5, 6), 7 *, 7 + paigutada virna.
• S = (5, 6, 7), * 2 + valige väärtuseks virna, kasutamise * ning asetage tulemus virnas.
• S = (5, 6 * 7) = (5, 42) + 2 väärtused valitud virna, kohaldada + ja pane tulemus virnas.
• S = (5 + 42) = (47) arvutus on lõpetatud, tulemus on salvestatud riidale.

See algoritm saab kontrollida RPN korduvalt, kuid iga kord, kui see töötab, ükskõik kui keeruline aritmeetika ekspressiooni.

OPN ja korstnad on tihedalt seotud. See näide demonstreerib, kuidas kasutada mälu arvutada väärtus vastupidine Poola märge. Vähem selge on, et saate kasutada virna, teisendades standard Siseliidete ekspressiooni äge neerupuudulikkus.

Näited programmeerimiskeelte

Pascal RPN aru niimoodi (näitab programmi osa).

Et lugeda numbreid ja operaatorite tsükli nimetatakse protseduuri, mis määrab, kas sümboolne number või märk operatsiooni. Esimesel juhul, salvestatud väärtuse virna ning teine kahest ülemisest virna vastaval hulgal toiming ning tulemus salvestatakse.

toktype: = num;

loe (s);

kui c all [ '+', '-', '*', '/'] siis algab

kui eoln siis cn: = '' teine lugeda (CN);

kui cn = '' siis

puhul

"+": Toktype: = lisage; "-": toktype: = sub;

'*': Toktype: = mitmekordsed; "/": Toktype: = div

lõpp

muidu hakkavad

Kui a = '-' seejärel sgn: = -1 teisega vea: = c <> '+';

koos: = cn

lõpp

lõpetamiseks;

if (ei vea) ja (toktype = num) seejärel getnumber;

kui toktype <> num siis algab

y = pop; x: = pop;

Kui ei ole viga siis

juhul toktype kohta

lisage: z: = x + y; sub: z: = x-y; mitmekordsed: z: = x * y; div: z: = x / y

lõpp

push (z);

C-rakendamist RPN (näidatud osa programmist):

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

a = strtod (s, & e);

if (e> s) vajutusega (a);

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

else if (* s == '+') rpnop (a + b);

else if (* s == '-') rpnop (a - b);

else if (* s == '*') rpnop (a * b);

else if (* s == '/') rpnop (a / b);

#undef rpnop

}

riistvara rakendused

Neil päevil, kui arvuti tehnoloogia oli väga kallis, arvati hea mõte, et sundida inimesi kasutama liigpingepiirikud. 1960. aastatest. Nagu nüüd, see oli võimalik osta kalkulaatorid, mis töötavad tagurpidi Poola märge. Lisada 2 ja 3 neist tuleb sisestada 2, siis 3, ja vajutage "pluss" nuppu. Esmapilgul sisend operandi operaatorile tundus keeruline ja raske meeles pidada, kuid mõne aja pärast mõned on sõltuvuses selle mõtteviisi ja ei saanud aru, miks teised rõhutavad loll Siseliidete, mis on nii keeruline ja nii on piiratud.

Burroughs firma isegi ehitatud Suurarvutis mis ei olnud muud mälu, välja arvatud virna. Ainus asi, mis muudab masina - rakendada algoritme ja meetodeid RPN keskse virna. Kõik tema tegevust pidada pidurdajad operaatorid, mis kehtib ülemine n väärtusi. Näiteks meeskond võttis Tagasi Aadress alates magasini tippu, ja nii edasi. D. arhitektuur selline masin oli lihtne, kuid mitte piisavalt kiiresti, et konkureerida sagedamini arhitektuuri. Paljud aga ikka on kahju, et selline lihtne ja elegantne lähenemine arvuti, kus iga programmi oli väljendus OPN leitud selle jätkamist.

Üks kord kalkulaatorid RPN olid populaarsed, ja mõned inimesed ikka neile eelistus. Lisaks nad välja virna orienteeritud keeltes, nagu Forth. Täna on vähe kasutatud, kuid siiski nostalgiline oma endise kasutajad.

Mis on tähendus nalju Reverse Poola vorsti?

Kui me eeldame, et ettevõtja vorsti, siis Siseliidete märge, peaks jääma valtsi tavalised hot dog. RPN asub otse kaheks pooleks saada valmis nendevahelise pärast arvutamist. Nüüd tuleb raskem osa - sinepit. Ta on juba vorsti, t. E. Juba arvutatakse unaarse operaator. Arvatakse, et sinepi tuleks ka näidatud uncalculated ja seetõttu tuleks see viia paremal vorsti ... Aga see on võimalik, see nõuaks liiga suur pakk ...