RPN: algoritme, metoder og eksempler

RPN engang dannede grundlag for en computer programmør i verden. I dag er det ikke så kendt. Derfor tegneserie illustration, der forestiller en "omvendt" polske pølsehorn udenfor, kan stadig blive misforstået af nogle kyndige programmører. Ikke meget vel forklare vittighed, men i dette tilfælde vil det være fuldt berettiget.

infix-typen

Alle programmører, og de fleste studerende er fortrolig med brugen af operatører. For eksempel de udtryk x + summation værdier for variablerne x og y brugte plustegn. Mindre kendt er det, at dette er lånt fra matematik notation, kaldet infix-typen notation, i virkeligheden, er et stort problem for maskinerne. Denne operator modtager som input to værdier registreres på venstre og højre. I programmering anvendte notation eventuelt med skilte operationer. For eksempel kan x + y skrives som en funktion af fold (x, y), i hvilken compiler og til sidst omdanner infix-typen notation. Men alle ved, at matematik er for godt til ikke at bruge aritmetiske udtryk, der danner en slags intern mini-sproget i næsten alle programmeringssprog.

formel oversætter

Den første virkelig vellykkede Fortran programmeringssprog er blevet så høj grad, fordi det aritmetiske udtryk (dvs. formel ..) Det konverteret (broadcast) i koden, deraf navnet på det - Formula oversættelse. Forud for, at de skulle skrive for eksempel foldet i form af funktioner (og formere (b, c)). I COBOL Problemet med at gennemføre automatisk konvertering formel blev betragtet som meget vanskeligt, fordi programmørerne skulle skrive ting som Føj A til B Mutliply Af C.

Hvad er der galt med infix-typen?

Problemet er, at operatørerne har sådanne egenskaber som forrang og associativitet. På grund af dette, at definitionen af infix-typen funktion bliver ikke-triviel opgave. For eksempel multiplikation har højere prioritet end addition eller subtraktion, hvilket betyder, at udtrykket 2 + 3 * 4 ikke er lig med summen af 2 og 3, ganget med 4, som det ville være i operatørernes indsats fra venstre mod højre. Faktisk formere 3 med 4 og tilsæt 2. Dette eksempel illustrerer, at beregningen af infix-typen ekspression ofte kræver en ændring i størrelsesordenen operatører og operander. Desuden er det nødvendigt at bruge seler til at se mere klart notation. For eksempel kan (2 + 3) * (4 + 5) ikke skrives uden parentes, fordi 2 + 3 * 4 + 5 betyder, at du har brug for at formere 3 af 4 og tilsæt 2 og 5.

Den rækkefølge, som du vil beregne operatørerne kræver lang huske. På grund af dette, studerende, der begynder at lære matematik, ofte får de forkerte resultater, selv om de faktiske operationer udføres korrekt. Det er nødvendigt at lære rækkefølgen af action udsagn udenad. For det første skal handlingen udføres i parentes, så multiplikation og division, og endelig addition og subtraktion. Men der er en anden måde at skrive matematiske udtryk som infix-typen notation er kun én af de mulige "små sprog", der kan føjes til mere.

Præfiks og postfix notation

To af de mest kendte alternativer er at registrere operatøren før eller efter dens operander. De er kendt som præfiks og postfix notation. Logiker Yan Lukasevich opfandt den første i 1920. Han boede i Polen, så pladen hedder polsk. Postfix-version, henholdsvis kaldet omvendt polsk notation (ARF). Den eneste forskel mellem disse to metoder er, i hvilken retning at læse posten (fra venstre mod højre eller højre til venstre), så er det tilstrækkeligt at foretage en grundig kun én af dem. Den OPN operatør er skrevet efter sine operander. Ekspressionen AB + repræsenterer et eksempel RPN for A + B.

Ubegrænset antal operander

Den umiddelbare fordel ved notation er, at det sammenfatter n-adic operatør og infix-typen notation er egentlig kun arbejder med to operander, t. E. ifølge sagens natur kun egnet til binær operator. For eksempel ABC @ er den omvendte polske ekspression under anvendelse triade mærke, som er den maksimale værdi af A, B og C. I dette tilfælde operatøren virker på venstre for tre operand selv og svarer til et funktionskald @ (A, B, C). Hvis du forsøger at skrive symbolet @ som infix-typen, såsom A @ BC eller sådan noget, bliver det klart, at det simpelthen ikke virker.

Den prioritering af rækkefølgen

RPN har en anden fordel ved, at prioriteringen af operatørerne kan repræsenteres ved rækkefølgen af deres udseende. Samtidig aldrig brug seler, selv om de kan indgå som tegn operationer for at lette overgangen fra infix-typen notation. For eksempel AB + C * - entydig ækvivalent (A + B) * C, så multiplikationen ikke kan beregnes, indtil den udførte tilsætning, hvilket giver en anden operand for multiplikation. Det er, hvis den beregnede AB + C * af én operatør ad gangen, får vi AB + C * -> (AB +) * C -> (A + B) * C.

beregning algoritme

Den OPN operatør ser det samme som en funktion, der tager som argumenter to værdier skrevet på hendes venstre. Desuden er det en naturlig notation til anvendelse i programmeringssprog, som måden til beregning svarer til stakken operationer og behovet for parsing elimineres. For eksempel vil det arrester i udtrykket 5 + 6 * 7 fremstå som en 5, 6, 7 *, +, og det kan beregnes ganske enkelt ved at scanne fra venstre mod højre og skrive værdierne i en stak. Når får operatøren anvendes et fælles tegn på drift og vælges af den øvre element 2 i computerens hukommelse, og det resultat, der returneres til hukommelsen. Når det endelige resultat af beregningen udtryk vil være i toppen af stakken.

For eksempel:

• S = () 5, 6, 7, *, + 5 placeret på stakken.
• S = (5) 6, 7, *, + 6 placeres på stablen.
• S = (5, 6), 7 *, 7 + placere stablen.
• S = (5, 6, 7), * 2 + vælge værdier fra stablen, brug * og placere resultatet i stablen.
• S = (5, 6 * 7) = (5, 42) + 2 værdier valgt fra stablen, at anvende + og sætte resultatet i stablen.
• S = (5 + 42) = (47) beregning er afsluttet, resultatet lagres i toppen af stakken.

Denne algoritme kan kontrolleres RPN flere gange, men hver gang det vil fungere, uanset hvor kompleks det aritmetiske udtryk.

OPN og stakke er tæt forbundet. Dette eksempel viser, hvordan du bruger hukommelse til at beregne værdien af den omvendte polsk notation. Mindre indlysende er, at du kan bruge stakken, konvertering af standard infix-typen udtryk i akut nyresvigt.

Eksempler på programmeringssprog

Pascal RPN indså ligesom dette (viser den del af programmet).

For at læse tal og operatorer i cyklussen kaldes procedure, der afgør, om det token nummer eller tegn drift. I det første tilfælde er lagret i stakken, og den anden af to øvre stack numre tilsvarende handling udført og resultatet lagres.

toktype: = num;

læse (s);

hvis ci [ '+', '-', '*', '/'] derefter begynde

hvis eoln derefter cn: = '' ellers læst (cn);

hvis cn = '' derefter

tilfælde af en

'+': Toktype: = tilføjer; '-': toktype: = sub;

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

ende

ellers begynder

hvis a = '-' så SGN: = -1 ellers fejl: = c <> '+';

med: = cn

ende

ende;

if (ikke fejl) og (toktype = num) og derefter getnumber;

hvis toktype <> num derefter begynde

y = pop; x: = pop;

hvis ikke fejl så

tilfælde toktype af

tilføje: z: = x + y; sub: z: = x-y; mul: z: = x * y; div: z: = x / y

ende

tryk (z);

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

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

a = strtod (s, & e);

if (e> s) tryk (a);

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

ellers hvis (* s == '+') rpnop (a + b);

ellers hvis (* s == '-') rpnop (a - b);

ellers hvis (* s == '*') rpnop (a * b);

ellers hvis (* s == '/') rpnop (a / b);

#undef rpnop

}

hardware implementeringer

I disse dage, hvor computerteknologi var meget dyrt, mente man en god idé at tvinge folk til at bruge overspændingsafledere. I 1960-erne., Som nu, var det muligt at købe de regnemaskiner, der arbejder i omvendt polsk notation. Hvis du vil tilføje 2 og 3 af dem skal indtaste 2, derefter 3, og tryk på "plus" knappen. Ved første øjekast, input operander til operatøren syntes kompliceret og svært at huske, men efter et stykke tid nogle er afhængige af denne tankegang og kunne ikke forstå, hvorfor de andre insisterer på dumme infix-typen, som er så kompliceret og så er begrænset.

Burroughs selskab endda bygget en mainframe, som ikke havde nogen anden hukommelse, undtagen stakken. Det eneste, der gør maskinen - anvendt algoritmer og metoder RPN til den centrale stakken. Alle dets aktiviteter blev betragtet som overspændingsbeskyttelse operatører, som gælder for de øvre n værdier. For eksempel, holdet tog Returadresse fra toppen af stakken, og så videre. D. arkitektur af en sådan maskine var enkel, men ikke hurtigt nok til at konkurrere med de mere almindelige arkitekturer. Mange er dog stadig beklage, at sådan en enkel og elegant tilgang til databehandling, hvor hvert program var et udtryk for OPN, fandt sin fortsættelse.

One Time regnemaskiner med RPN var populære, og nogle mennesker stadig give dem præference. Desuden har de udviklet en stak-orienterede sprog, såsom Forth. I dag er det lidt brugt, men stadig nostalgisk fra hans tidligere brugere.

Så hvad er meningen vittigheder om Reverse Polish pølse?

Hvis vi antager, at operatøren af pølsen, den infix-typen notation, det skal være inden rullen som i konventionel hotdog. Den RPN ligger lige i to halvdele få klar herimellem efter beregning. Nu kommer den svære del - sennep. Hun er allerede på pølsen, t. E. Allerede beregnet som en unary operatør. Det menes, at sennep også skal vises som uberegneligt, og derfor bør flyttes til højre for pølse ... Men det er muligt, ville det kræve for stor stak af ...