RPN: algoritm, metoder och exempel

RPN bildade en gång till grund för en programmerare i världen. Idag är det inte så välkänd. Därför komisk illustration, som skildrar en "omvänd" polska korv rullar utanför, kan fortfarande missförstås av några kunniga programmerare. Inte mycket väl förklara skämt, men i detta fall kommer det att vara helt berättigat.

infix

Alla programmerare och de flesta studenter är bekanta med hjälp av operatörerna. Till exempel uttryck x + summeringsvärdena för variablerna x och y använda plustecken. Mindre känt är det faktum att detta är lånad från matematik notation, kallad infix notation, i själva verket är ett stort problem för maskinerna. Denna operatör får som ingångs två värden registreras till vänster och höger. I programmeringsspråk som används betecknings eventuellt med tecken operationer. Till exempel, kan x + y skrivas som en funktion av veck (x, y), i vilken kompilator och slutligen omvandlar infix notation. Men alla vet att matte är för bra för att inte använda aritmetiska uttryck, som bildar ett slags intern mini-språk i nästan varje programmeringsspråk.

formeln översättare

Den första riktigt framgångsrika språket Fortran programmering har blivit så stor del på grund av aritmetiska uttryck (dvs formel ..) Det konverterade (broadcast) i koden, därav namnet på det - Formula översättning. Dessförinnan var de tvungna att skriva till exempel vikta i form av funktioner (och multiplicera (b, c)). I COBOL problem att genomföra automatisk konvertering formel ansågs mycket svårt eftersom programmerarna var tvungen att skriva saker som Lägg A till B Mutliply av C.

Vad är fel med infix?

Problemet är att operatörerna har sådana egenskaper som företräde och associativitet. På grund av detta blir definitionen av infix funktion icke-trivial uppgift. Till exempel, har multiplikation högre prioritet än addition eller subtraktion, vilket betyder att uttrycket 2 + 3 * 4 inte är lika med summan av 2 och 3, multipliceras med 4, som det skulle vara i utförandet av operatörerna från vänster till höger. I själva verket multiplicerar 3 med 4 och tillsätt 2. Detta exempel åskådliggör att beräkningen av infix uttryck ofta kräver en förändring i storleksordningen operatörer och operander. Dessutom är det nödvändigt att använda hängslen för att titta mer tydlig notation. Till exempel kan (2 + 3) * (4 + 5) inte skrivas utan parenteser, eftersom 2 + 3 * 4 + 5 innebär att du måste multiplicera 3 av 4 och tillsätt 2 och 5.

Den ordning i vilken du vill beräkna operatörerna kräver en lång minnas. På grund av detta, studenter som börjar lära sig aritmetik, ofta får fel resultat, även om de faktiska operationer utförs korrekt. Det är nödvändigt att lära ordning åtgärds uttalanden utantill. För det första måste åtgärden utföras inom parentes, sedan multiplikation och division, och slutligen addition och subtraktion. Men det finns ett annat sätt att skriva matematiska uttryck som infix notation är endast en av de möjliga "små språk" som kan läggas till mer.

Prefix och postfix notation

Två av de mest kända alternativ är att spela in operatören före eller efter dess operander. De är kända som prefix och postfix notation. Logician Yan Lukasevich uppfann den första 1920. Han bodde i Polen, så skivan heter polska. Postfix version, respektive, som kallas omvänd polsk notation (ARF). Den enda skillnaden mellan dessa två metoder är den riktning i vilken för att läsa posten (från vänster till höger eller höger till vänster), så det räcker att undersöka i detalj endast en av dem. OPN Operatören skrivs efter dess operander. Således uttrycket AB + representerar ett exempel RPN för A + B.

Obegränsat antal operander

Den omedelbara fördelen med notation är att det sammanfattar n-adic operatör och infix notation är egentligen bara fungerar med två operander, t. E. är i sig lämpar sig endast för binära operationer. Till exempel, är ABC @ den omvända polska uttryck med hjälp triadic varumärke som är det maximala värdet på A, B och C. I detta fall operatören verkar på den vänstra av de tre operanden självt och motsvarar ett funktionsanrop @ (A, B, C). Om du försöker skriva @ -tecknet som infix, såsom A @ BC eller något liknande, blir det tydligt att det helt enkelt inte fungerar.

Prioriteringen av order

RPN har en annan fördel i att prioriteringen av operatörerna kan representeras på order av deras utseende. Samtidigt behöver aldrig hängslen, även om de kan ingå som tecken operationer för att underlätta omvandlingen från infix notation. Till exempel AB + C * - otvetydig ekvivalent (A + B) * C, så multiplikationen inte kan beräknas tills tillsatsen utföras, vilket ger en andra operand för multiplikation. Det vill säga, om den beräknade AB + C * av en operatör i taget, får vi AB + C * -> (AB +) * C -> (A + B) * C.

beräkningsalgoritm

OPN Operatören ser likadan ut som en funktion som tar som argument två värden skrivet på hennes vänstra. Dessutom är det en naturlig notation för användning i programmeringsspråk, som sättet för dess beräkning motsvarar stapeloperationer och behovet av parsning elimineras. Till exempel, kommer avledaren i uttrycket 5 + 6 * 7 visas som en 5, 6, 7 *, +, och det kan beräknas enkelt genom avsökning från vänster till höger och skriva värdena i en stapel. Närhelst en vanligt tecken på drift, som valts av det övre elementet 2 i datorminnet är operatören används och resultatet återförs till minnet. När slutresultatet av beräkningen uttrycket kommer att vara i toppen av stapeln.

Till exempel:

• S = () 5, 6, 7, *, + 5 placeras på stacken.
• S = (5) 6, 7, *, + 6 placeras på stacken.
• S = (5, 6), 7 *, 7 + placera stapeln.
• S = (5, 6, 7), * 2 + välja värden från stacken, användning * och placera resultatet i stapeln.
• S = (5, 6 * 7) = (5, 42) + 2 värden valda från stapeln, att tillämpa på + och sätta resultatet i stapeln.
• S = (5 + 42) = (47) Beräkningen är klar, lagras resultatet i toppen av stacken.

kan kontrolleras denna algoritm RPN flera gånger, men varje gång det kommer att fungera, oavsett hur komplex den aritmetiska uttryck.

OPN och stackar är nära sammankopplade. Detta exempel visar hur man använder minnet för att beräkna värdet av den omvända polska notation. Mindre uppenbart är att du kan använda stack, konvertera standard infix uttryck i akut njursvikt.

Exempel på programmeringsspråk

Pascal RPN insåg så här (visar delen av programmet).

För att läsa siffror och operatörer i cykeln kallas förfarande, som avgör om det token nummer eller tecken operation. I det första fallet, är det värde som lagras i stacken, och den andra av de två övre stapelnummer motsvarande åtgärd som utförs och resultatet lagras.

toktype: = num;

läs (s);

om c i [ '+', '-', '*', '/'] sedan börja

om eoln sedan cn: = '' annan läsa (CN);

om cn = '' sedan

fallet med en

'+': Toktype: = lägg; '-': toktype: = sub;

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

änden

annars börjar

om a = '-' sedan sgn: = -1 annars fel: = c <> '+';

med: = cn

änden

avsluta;

if (inte fel) och (toktype = num) därefter getnumber;

Om toktype <> num börjar sedan

y = pop; x: = pop;

om inte fel då

fall toktype av

lägg: z: = x + y; sub: z: = x-y; mul: z: = x * y; div: z: = x / y

änden

push (z);

C-genomförande RPN (visad del av programmet):

för (s = strtok (s, w); s; s = strtok (0, w)) {

a = strtod (s, & e);

if (e> s) push (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

}

hårdvaruimplementeringar

På den tiden, när datorteknik var mycket dyrt, var det tänkt en bra idé att tvinga människor att använda ventilavledare. I 1960-talet., Som nu, var det möjligt att köpa miniräknare, som fungerar i omvänd polsk notation. För att lägga till två och tre av dem måste ange två, sedan tre, och tryck på "plus" -knappen. Vid första anblicken ingångsoperander till operatören verkade komplicerat och svårt att komma ihåg, men efter ett tag en del är beroende av det här sättet att tänka och kunde inte förstå varför de andra insisterar på dumma infix, som är så komplicerat och så är begränsad.

Burroughs företaget även byggt en stordator, som inte hade någon annan minne, utom stack. Det enda som gör maskinen - tillämpat algoritmer och metoder RPN till den centrala bunten. All verksamhet betraktades som Skydd operatörer, som är tillämplig på de övre n-värden. Till exempel tog laget Return Address från toppen av stacken, och så vidare. D. Arkitekturen i en sådan maskin var enkelt, men inte tillräckligt snabbt för att konkurrera med de mer vanliga arkitekturer. Många dock fortfarande beklagar att en sådan enkel och elegant inställning till datorer där varje program var ett uttryck för OPN, funnit sin fortsättning.

Engångs räknare med RPN var populär, och vissa människor fortfarande ge dem företräde. Dessutom utvecklade de en stack orienterade språk, såsom Forth. Idag är det lite används, men fortfarande nostalgisk från hans tidigare användare.

Så vad är meningen skämt om Reverse Polish korv?

Om vi antar att operatören av korven, den infix notation, bör det vara inom rullen som vid konventionell varmkorv. Den RPN ligger mitt i två halvor får färdiga emellan efter beräkning. Nu kommer den svåra delen - senap. Hon är redan på korv, t. E. Redan beräknas som en unär operator. Man tror att senap också ska visas som oberäknat och därför bör flyttas till höger om korven ... Men det är möjligt, skulle detta kräva alltför stor trave ...