RPN: Algoritme, fremgangsmåter og eksempler

RPN dannet en gang ut fra en datamaskin programmerer i verden. I dag er det ikke så godt kjent. Derfor, komisk illustrasjon, som viser en "omvendt" polske pølse ruller utenfor, kan fremdeles bli misforstått av noen kunnskapsrike programmerere. Ikke veldig godt forklare spøk, men i dette tilfellet vil det være fullt berettiget.

infiks

Alle programmerere, og de fleste studenter er kjent med bruk av operatører. For eksempel, de uttrykk x + summerte verdier for variablene x og y brukte plusstegn. Mindre kjent er det faktum at dette er lånt fra matematikk notasjon, kalt infiks notasjon, faktisk, er et stort problem for maskinene. Denne operatør mottar som inngangs to verdier er angitt på venstre og høyre. I programmering notasjon brukes eventuelt med skilter operasjoner. For eksempel, kan x + y være skrevet som en funksjon av fold (x, y), der kompilatoren og eventuelt omdanner infiks notasjon. Men alle vet at matematikk er for godt til å ikke bruke aritmetiske uttrykk, som danner en slags intern mini-språk i nesten alle programmeringsspråk.

formel etter

Den første virkelig vellykkede Fortran programmeringsspråk har blitt så stor grad fordi det aritmetiske uttrykk (dvs. formel ..) Det konvertert (kringkasting) i koden, derav navnet på det - Formula oversettelse. Før det måtte de skrive, for eksempel foldet i form av funksjoner (og formere (b, c)). I COBOL problem med å implementere automatisk konvertering formel ble ansett som svært vanskelig fordi programmerere måtte skrive ting som til A til B mutliply av C.

Hva er galt med infiks?

Problemet er at operatørene har slike egenskaper som prioriteres og assosiativitet. På grunn av dette, blir definisjonen av infiks funksjon ikke-triviell oppgave. For eksempel har multiplikasjon høyere prioritet enn addisjon eller subtraksjon, hvilket betyr at uttrykket 2 + 3 * 4 er ikke lik summen av 2 og 3, multiplisert med 4, som det ville være i utførelsen av operatørene fra venstre til høyre. Faktisk multiplisere 3 ved 4, og legge til 2. Dette eksempel illustrerer at beregningen av infiks uttrykket krever ofte en forandring i rekkefølgen av operatører og operander. I tillegg er det nødvendig å bruke tannregulering for å se mer tydelig notasjon. For eksempel kan (2 + 3) * (4 + 5) ikke skrives uten parentes, fordi 2 + 3 * 4 + 5 betyr at du trenger å multiplisere tre av fire og legg to og fem.

I hvilken rekkefølge du vil beregne operatørene krever huske lenge. På grunn av dette, studenter som begynner å lære aritmetikk, ofte får feil resultat, selv om selve operasjonene utføres riktig. Det er nødvendig å lære rekkefølgen av handlingen uttalelser utenat. For det første må handlingen utføres i parentes, deretter multiplikasjon og divisjon, og endelig addisjon og subtraksjon. Men det er en annen måte å skrive matematiske uttrykk som infiks notasjon er bare en av de mulige "små språk" som kan legges til flere.

Prefiks og postfix notasjon

To av de mest kjente alternativene er å registrere operatøren før eller etter sine operander. De er kjent som prefiks og postfix notasjon. Logician Yan Lukasevich oppfant den første i 1920. Han bodde i Polen, så posten er kalt polsk. Postfix versjon, henholdsvis kalt omvendt polsk notasjon (ARF). Den eneste forskjellen mellom disse to metodene er den retning som å lese posten (fra venstre til høyre eller høyre til venstre), så er det tilstrekkelig å vurdere i detalj bare ett av dem. Den OPN operatør er skrevet etter sine operander. Dermed, innbefatter uttrykket AB + representerer et eksempel RPN for A + B.

Ubegrenset antall operander

Den umiddelbare fordel ved notasjon er at den oppsummerer n-ADIC operatør og infiks notasjon er egentlig bare arbeider med to operander, t. E. er i seg selv er egnet bare for binære operasjoner. For eksempel, er ABC @ omvendt polsk uttrykk ved hjelp triadic merke som er den maksimale verdi av A, B og C. I dette tilfelle operatøren virker på venstre side av de tre operanden seg og svarer til et funksjonskall @ (A, B, C). Hvis du prøver å skrive @ -symbolet som infiks, slik som A @ BC eller noe sånt, blir det klart at det rett og slett ikke fungerer.

Prioriteringen av ordren

RPN har en annen fordel i at prioriteten av operatørene kan representeres ved rekkefølgen av deres opptreden. Samtidig aldri trenger tannregulering, selv om de kan inngå som tegn operasjoner for å lette overgangen fra infiks notasjon. For eksempel, AB + C * - entydig ekvivalent (A + B) * C, slik at multiplikasjonen ikke kan beregnes inntil tilsetningen utføres, noe som gir en annen operand for multiplikasjon. Det vil si, dersom den beregnede AB + C * av én operatør på en gang, får vi AB + C * -> (AB +) * C -> (A + B) * C.

beregningsalgoritme

Den OPN operatøren ser det samme som en funksjon som tar som argumenter to verdier skrevet på hennes venstre. I tillegg er det en naturlig notasjon for bruk i programmeringsspråk, som samme måte som i sin beregning tilsvarer stabel operasjonene og behovet for analyseringen er eliminert. For eksempel vil Arrester i uttrykket 5 + 6 * 7 fremstå som en 5, 6, 7 *, +, og det kan beregnes ganske enkelt ved å skanne fra venstre til høyre og skriv verdiene i en stabel. Når en vanlig tegn på operasjon, valgt av det øvre element 2 i datamaskinens minne, blir operatøren anvendt og resultatet returneres til minnet. Når det endelige resultatet av beregningen uttrykket vil være på toppen av stabelen.

For eksempel:

• S = () 5, 6, 7, * + 5 plassert på stabelen.
• S = (5) 6, 7, * + 6 som er plassert på stabelen.
• S = (5, 6), 7 *, 7 + plassere stabelen.
• S = (5, 6, 7), * 2 + velge verdier fra stabelen, anvendelse * og plassere resultatet i stabelen.
• S = (5, 6 * 7) = (5, 42) + 2 verdier valgt fra stabelen, for å anvende + og sette resultatet i stabelen.
• S = (5 + 42) = (47) utregning er fullført, blir resultatet lagret i toppen av stabelen.

Denne algoritmen kan sjekkes RPN gjentatte ganger, men hver gang det vil fungere, uansett hvor kompleks aritmetisk uttrykk.

OPN og stabler er nært knyttet. Dette eksemplet viser hvordan du bruker minnet for å beregne verdien av omvendt polsk notasjon. Mindre åpenbare er at man kan bruke stabelen, å konvertere standard infiks uttrykk ved akutt nyresvikt.

Eksempler på programmeringsspråk

Pascal RPN realisert som dette (viser en del av programmet).

For å lese tallene og operatorer i syklusen kalt prosedyre, som avgjør hvorvidt kodenummeret eller skilt operasjon. I det første tilfellet blir den verdien som er lagret i stabelen, og den andre av de to øvre stabelen tall tilsvarende handling utføres, og resultatet blir lagret.

toktype: = num;

lese (s);

hvis c i [ '+', '-', '*', '/'] og begynner deretter

hvis eoln deretter cn: = '' annet lese (cn);

hvis cn = '' da

Ved en

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

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

end

ellers begynner

hvis a = '-' deretter sgn: = -1 annet feil: = c <> '+';

med: = cn

end

end;

if (ikke feil) og (toktype = num) deretter getnumber;

hvis toktype <> num da begynne

y = pop; x: = pop;

hvis ikke feil da

Ved toktype av

legge til: z: = x + y; Sub: z: = x-y; mul: z: = x * y; div: z: = x / y

end

push (z);

C-implementering RPN (vist en del av programmet):

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

a = strtod (s, og e);

if (e> r) trykk (a);

#define rpnop (x) printf ( "% c:", * s), b = pop (), en = pop (), skyv (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

}

hardware implementeringer

I disse dager, da datateknologi var svært dyrt, var det tenkt en god ide å tvinge folk til å bruke overspenningsavledere. I 1960-tallet., Som nå, var det mulig å kjøpe kalkulatorer, som arbeider i revers polsk notasjon. Å legge to og tre av dem må skrive inn to, så tre, og trykk på "pluss" -knappen. Ved første øyekast inngangs operander til operatøren virket komplisert og vanskelig å huske, men etter en stund noen er avhengige av denne måten å tenke på, og kunne ikke forstå hvorfor de andre insisterer på dumme infiks, som er så komplisert og så er begrenset.

Burroughs selskap selv bygget en stormaskin, som hadde ingen andre minnet, bortsett fra bunken. Det eneste som gjør maskinen - anvendt algoritmer og metoder RPN til den sentrale stabelen. Alle de operasjoner ble betraktet som Avledere operatorer, som gjelder for de øvre n-verdiene. For eksempel, teamet tok Returadresse fra toppen av bunken, og så videre. D. Arkitekturen av en slik maskin var enkel, men ikke rask nok til å konkurrere med de mer vanlige arkitekturer. Mange, men fortsatt beklager det faktum at en slik enkel og elegant tilnærming til databehandling der hvert program var et uttrykk for OPN, funnet sin fortsettelse.

Engangs kalkulatorer med RPN var populære, og noen mennesker fortsatt gi dem preferanse. I tillegg har de utviklet et stakkorienterte språk, slik som Forth. I dag er det lite brukt, men fortsatt nostalgisk fra hans tidligere brukere.

Så hva er meningen vitser om Reverse Polish pølse?

Hvis vi antar at operatøren av pølse, den infiks notasjon, det bør være innenfor roll som i vanlig hot dog. RPN ligger midt i to halvdeler få klare derimellom etter beregning. Nå kommer den vanskelige delen - sennep. Hun er allerede på pølse, t. E. allerede regnet som en ensartet operatør. Det antas at sennep bør også bli vist som uncalculated og derfor bør flyttes til høyre for pølse ... Men det er mulig, vil dette kreve for stor bunke ...