Omvänd polsk notation

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 28 september 2021; kontroller kräver 2 redigeringar .

Omvänd polsk notation (RPN ) är en form av att skriva matematiska och logiska uttryck där operanderna finns före operationstecknen . Även kallad omvänd parenteslös notation , postfix notation , Lukasiewiczs parentesless symbolism , polsk invers notation , POLIZ .

En stackmaskin är en algoritm som utför beräkningar med omvänd polsk notation (se nedan för ett exempel på utvärdering av uttryck ).

Historik

Omvänd polsk notation (RPN) utvecklades av den australiensiska filosofen och datorteoretikern Charles Hamblin i mitten av 1950- talet, baserat på polsk notation , som föreslogs 1920 av den polske matematikern Jan Lukasiewicz . Hamblins verk presenterades vid en konferens i juni 1957 och publicerades 1957 och 1962 .

De första datorerna som stödde omvänd polsk notation var KDF9 från English Electric Company , som tillkännagavs 1960 och släpptes (kom ut till försäljning) 1963 , och amerikanska Burroughs B5000 , tillkännagav 1961 , släpptes samma 1963. En av formgivarna av B5000, R. S. Barton , skrev senare att han utvecklade omvänd polsk notation oberoende av Hamblin runt 1958, medan han läste en bok om symbolisk logik , och innan han blev bekant med Hamblins arbete.

Friden tog med sig överspänningsavledaren till miniräknare med juni 1964 EC-130. Och 1968 utvecklade Hewlett-Packards ingenjörer den stationära miniräknaren 9100A med stöd för överspänningsavledare. Denna kalkylator gjorde omvänd polsk notation populär bland forskare och ingenjörer, även om den tidiga 9100A-reklamen inte nämnde överspänningsavledaren. 1972 blev den HP-35 SPD-aktiverade miniräknaren den första vetenskapliga fickkalkylatorn .

1971 dök det ursprungliga programmeringsspråket Forth upp , vars språkmaskin har en tvåstackstruktur och där alla beräkningar utförs på stacken . I detta språk är OPN ett naturligt sätt att skriva alla dataoperationer, även om det är möjligt att implementera den vanliga ( infix ) notationen för aritmetiska operationer om så önskas.

Avledaren användes i den sovjetiska ingenjörskalkylatorn B3-19M (utvecklad gemensamt med DDR), som släpptes 1976. Alla programmerbara mikroräknare som tillverkades i Sovjetunionen fram till slutet av 1980 -talet , med undantag för Elektronika MK-85 och Elektronika MK-90 , använde en avledare - den var lättare att implementera och gjorde det möjligt att klara sig i programmeringsberäkningar med en mindre antal kommandon, jämfört med den vanliga algebraiska notationen, och mängden programminne i dessa modeller har alltid varit en kritisk resurs. Avledaren används i moderna ryska programmerbara miniräknare " Elektronika MK-152 " och " Elektronika MK-161 ", vilket säkerställer deras kompatibilitet med program skrivna för sovjetiska miniräknare.

Definition

För att ge en induktiv definition av postfix notation [1] , låt oss beteckna uttryck i infix notation , , , deras ekvivalenta uttryck i postfix notation , respektive ; är en godtycklig binär operator, då: $E$ $E_1$ $E_2$ $\dot E$ $\dot E_1$ $\dot E_2$ $o$

1. Om - en variabel eller en konstant, det vill säga . $E$ $\dot E$ $E$

2. Om är ett uttryck för formen , det vill säga . $E$ $E_1 o E_2$ $\dot E$ $\dot E_1 \dot E_2 o$

3. Om är ett uttryck för formen , det vill säga . $E$ $(E_1)$ $\dot E$ $\dot E_1$

Beskrivning

Ett utmärkande drag för omvänd polsk notation är att alla argument (eller operander ) placeras före operationstecknet. I allmänhet ser posten ut så här:

En operationsuppsättningspost består av en sekvens av operander och operationstecken. Operander i ett uttryck separeras med mellanslag när de skrivs.
Uttrycket läses från vänster till höger. När ett operatortecken förekommer i ett uttryck, utförs motsvarande operation på de två sista operanderna som förekommer före det, i den ordning som de skrivs. Resultatet av operationen ersätter sekvensen av dess operander och dess tecken i uttrycket, varefter uttrycket utvärderas vidare enligt samma regel.
Resultatet av uttrycksutvärderingen är resultatet av den senast utvärderade operationen.

Tänk till exempel på utvärderingen av ett uttryck 7 2 3 * −(motsvarande uttryck i infixnotation: 7 − 2 * 3).

Det första tecknet på operationen är "*", så operationen med multiplikation utförs först på operanderna 2 och 3 (de är de sista före tecknet). Uttrycket omvandlas sedan till formen 7 6 −(resultatet av multiplikation - 6 - ersätter trippeln "2 3 *").
Det andra tecknet i operationen är "−". En subtraktionsoperation utförs på operanderna 7 och 6.
Beräkningen klar. Resultatet av den senaste operationen är 1, detta är resultatet av uttrycksutvärderingen.

En uppenbar utökning av omvänd polsk notation till unära, ternära och operationer med vilket annat antal operander som helst: när man använder tecknen för sådana operationer i utvärderingen av ett uttryck, tillämpas operationen på motsvarande antal senast påträffade operander.

Funktionerna för omvänd polsk notation är följande:

Ordningsföljden för utförande av operationer är entydigt specificerad av ordningen för operationstecken i uttrycket, så det finns inget behov av att använda parenteser och införa prioriteringar och associativitet för operationer.
Till skillnad från infixnotation är det inte möjligt att använda samma tecken för att skriva unära och binära operationer. Så, i infixnotation, 5 * (−3 + 8)använder uttrycket minustecknet som en symbol för en unär operation (ändring av tecken för ett tal), och uttrycket (10 − 15) * 3använder samma tecken för att beteckna en binär operation (subtraktion). Den specifika operationen bestäms av karaktärens position. Omvänd polsk notation tillåter inte detta: notationen 5 3 − 8 + *(den villkorliga analogen av det första uttrycket) kommer att tolkas som felaktig, eftersom det är omöjligt att avgöra att "minus" efter 5 och 3 inte betyder en subtraktion; som ett resultat kommer ett försök att göras att först beräkna 5 − 3, sedan 2 + 8, varefter det visar sig att det inte finns tillräckligt med operander för multiplikationsoperationen. För att fortfarande skriva detta uttryck måste du antingen omformulera det (till exempel genom att skriva uttrycket istället för − 3uttrycket 0 − 3), eller införa en separat beteckning för operationen att ändra tecknet, till exempel "±": 5 3 ± 8 + *.
Liksom i infixnotation kan i OPN en och samma beräkning skrivas i flera olika versioner. Till exempel kan ett uttryck (10 − 15) * 3i OPN skrivas som 10 15 − 3 *, eller så kan du skriva det som3 10 15 − *
På grund av avsaknaden av parenteser är omvänd polsk notation kortare än infix. På grund av detta, vid beräkning på miniräknare, ökar hastigheten på operatörens arbete (antalet nedtryckta tangenter minskas), och i programmerbara enheter minskas volymen av de delar av programmet som beskriver beräkningar. Det senare kan vara viktigt för bärbara och inbäddade datorenheter som har allvarliga begränsningar av minnesmängden.

Stackberäkningar

Allmän ordning

Automatisering av utvärderingen av uttryck i omvänd polsk notation är baserad på användningen av en stack . Beräkningsalgoritmen för stackmaskinen är elementär:

Bearbetning av inmatningssymboler
- Om en operand ges som input, skjuts den upp på toppen av stapeln.
- Om ett operationstecken ges till ingången, utförs motsvarande operation på det erforderliga antalet värden som kommer från stacken, tagna i tilläggsordningen. Resultatet av den utförda operationen placeras på toppen av stapeln.
Om den inmatade teckenuppsättningen inte är fullständigt bearbetad, gå till steg 1.
Efter att den inmatade teckenuppsättningen har bearbetats fullständigt, ligger resultatet av uttrycksutvärderingen på toppen av stacken.

Implementeringen av en stackmaskin, både i mjukvara och i hårdvara, är extremt enkel och kan vara mycket effektiv. Omvänd polsk notation är helt enhetlig - den skriver i princip unära, binära, ternära och alla andra operationer, såväl som funktionsanrop på samma sätt, vilket gör det möjligt att inte komplicera designen av datorenheter samtidigt som man utökar uppsättningen av stödda operationer. Detta var anledningen till användningen av omvänd polsk notation i vissa vetenskapliga och programmerbara miniräknare.

Exempel på utvärdering av uttryck

Ett infixuttryck i en GRE kan skrivas så här: $(1 + 2)\ gånger 4 + 3$ 1 2 + 4 × 3 +

Beräkningen görs från vänster till höger, inmatningen tolkas enligt tabellen nedan (stackens tillstånd efter operationen indikeras, toppen av stacken är markerad i rött ):

Inmatning	Drift	Stack
ett	lägga på traven	ett
2	lägga på traven	1, 2
+	tillägg	3
fyra	lägga på traven	3, 4
*	multiplikation	12
3	lägga på traven	12, 3
+	tillägg	femton

Resultatet, 15, är överst i stapeln i slutet av beräkningen.

"Enter"-tangenten (på räknare betecknad som "Enter" eller symbolen "↑") fungerar som en operandseparator när två operander är omedelbart intill varandra. Om operanden följs av operationstecknet krävs inte att den trycks ned, detta minskar antalet åtgärder som måste utföras för att få resultatet.

Konvertering från infixnotation

Edsger Dijkstra uppfann en algoritm för att konvertera uttryck från infixnotation till IPV. Algoritmen kallades "rangerbangård", för dess verksamhets likhet med vad som händer på järnvägsbangårdar. Infixnotation är den form av matematisk notation som de flesta använder (till exempel 3 + 4eller 3 + 4 * (2 − 1)). Liksom SPV-beräkningsalgoritmen är rangeringsgårdsalgoritmen baserad på en stack. Det finns två textvariabler involverade i konverteringen: input- och output-strängar. Konverteringsprocessen använder en stack som lagrar operationer som ännu inte har lagts till i utdatasträngen. Konverteringsprogrammet läser inmatningssträngen tecken för tecken i följd (ett tecken är inte nödvändigtvis en bokstav), utför några åtgärder vid varje steg, beroende på vilket tecken som lästes.

Ett enkelt exempel

Ingång:3 + 4

Lägg 3till på utdataraden (om ett nummer läses läggs det omedelbart till på utdataraden).

Tryck +(eller dess identifierare) på operationsstacken.

Lägg 4till i utgångsraden.

Vi har läst hela uttrycket, nu skjuter vi alla operationer som finns kvar på stacken till utgångsraden. I vårt exempel innehåller stacken endast +.

Utgångslinje:3 4 +

I det här exemplet visas några regler: alla nummer överförs till utgångsraden omedelbart efter läsning; när uttrycket läses fullständigt, skjuts alla återstående operationer på stacken till utgångsraden.

Algoritm

Medan det finns fler karaktärer att läsa:

Vi läser nästa karaktär.
Om tecknet är ett tal eller en postfix-funktion (till exempel ! - factorial ), lägg till det i utdatasträngen.
Om symbolen är en prefixfunktion (till exempel sin - sinus ), tryck den på stapeln.
Om tecknet är en öppen parentes, skjut den på stapeln.
Om tecknet är en avslutande parentes:

Tills det översta elementet i stacken är öppningsparentesen, skjuter du elementen från stapeln på utmatningssträngen. Detta tar bort öppningsstaget från stapeln, men lägger inte till det i utgångssträngen. Om stacken slutade innan vi träffade öppningsparentesen betyder det att antingen är avgränsaren felaktigt placerad i uttrycket, eller så är parentesen inte matchade.

Om det finns olika typer av parenteser indikerar utseendet på en oöverträffad parentes också ett fel. Om några parenteser är funktioner samtidigt (till exempel [x] är en heltalsdel ), lägger vi till symbolen för denna funktion till utdatasträngen.

Om symbolen är den binära operationen o1 , då:

1) medan högst upp i stacken finns en prefixfunktion ... … ELLER operationen överst i stacken har högre prioritet eller samma prioritetsnivå som o1 … ELLER operationen överst i stack är vänsterassocierad med prioritet som o1 ... tryck det översta elementet av stacken till utmatningssträngen; 2) skjut operationen o1 på stapeln.

När inmatningssträngen är över, poppar du alla tecken från stacken till utmatningssträngen. Endast operationssymboler skulle finnas kvar på stapeln; om det inte är det, så matchar uttrycket inte parenteser.

Begränsningar och modifieringar

Algoritmen förutsätter att källsträngen är korrekt (inte alla fel kontrolleras), och alla prefix-/postfix-funktioner är unära.

Se huvudartikeln för en modifiering av flerplatsfunktioner med ett fast antal argument .

För operationer som -x som är både binära och unära, behövs en modifiering: när en sådan operation hittas tittar systemet på det föregående tecknet och avgör om minus är en binär operation eller en unär funktion. Följaktligen behöver stacken och NPV olika symboler för binära och unära minus.

Komplext exempel

Prioriteter :

högsta: uttryck inom parentes ( )
hög: ^
medel: * /
låg: + −

Indata: 3 + 4 * 2 / (1 - 5)^2 Vi läser "3" Lägg till "3" till utdatasträngen Utgång: 3 Vi läser "+" Sätt "+" på högen Utgång: 3 Stack: + Vi läser "4" Lägg till "4" till utdatasträngen Utgång: 3 4 Stack: + Vi läser "*" Tryck "*" på stapeln Utgång: 3 4 Stack: + * Vi läser "2" Lägg till "2" till utdatasträngen Utdata: 3 4 2 Stack: + * Vi läser "/" Poppa "*" från stack till utgångssträng, tryck "/" på stack Utdata: 3 4 2 * Stack: + / Vi läser "(" Tryck "(" på högen Utdata: 3 4 2 * Stack: + / ( Vi läser "1" Lägg till "1" till utdatasträngen Utdata: 3 4 2 * 1 Stack: + / ( Vi läser "-" Tryck "-" på stapeln Utdata: 3 4 2 * 1 Stack: + / ( − Vi läser "5" Lägg till "5" till utdatasträngen Utdata: 3 4 2 * 1 5 Stack: + / ( - Vi läser ")" Poppa "−" från stapeln till utgångssträngen, pop "(" Utgång: 3 4 2 * 1 5 − Stack: + / Vi läser "^" Lägg "^" på högen Utgång: 3 4 2 * 1 5 − Stack: + / ^ Vi läser "2" Lägg till "2" till utdatasträngen Utdata: 3 4 2 * 1 5 − 2 Stack: + / ^ Slut på uttrycket Poppar alla element från stapeln till en sträng Utdata: 3 4 2 * 1 5 − 2 ^ / +

Uttrycksoptimering

Om du skriver en tolk kan utdatasträngen som erhålls efter att ha konverterat det ursprungliga uttrycket till omvänd polsk notation lagras i stället för det ursprungliga uttrycket för senare tolkning. Omvänd polsk notation gör det också möjligt för datorn att förenkla uttryck.

Ett exempel på en uttrycksförenklingsalgoritm

Betrakta en algoritm som utför förberäkning av konstanter i ett uttryck. Ett uttryck ges i OPN. Vi behöver en stack för att lagra blandad data (nummer och operatörer).

Algoritmen liknar den som används för att utvärdera uttryck. Vi skannar uttrycket från vänster till höger.

Så länge det finns tecken att läsa:

Vi läser nästa karaktär.
Om tecknet är en siffra, skjut upp det på högen.
Om tecknet är en variabel, förutsatt att variabeln är null , skjuter du in tecknet i stacken.
Om symbolen är en operator:
1) (om alla operatorargument i stacken har ett annat värde än null ) skjuter operatorargumenten från stacken och skjuter resultatet av operationen till stacken;
2) (om minst ett av argumenten är null ) om vi antar att resultatet av operationen är null lägger vi operatorsymbolen på stacken.

Efter att hela uttrycket har undersökts är det som finns kvar på stacken det optimerade uttrycket (uttryckets uttalanden är i omvänd ordning på stacken).

Ett exempel på hur algoritmen fungerar

Uttryck Infixnotation: exp(-1/2*x) Omvänd polsk notation: -1 2 / x * exp Läser: "-1" Tryck "-1" på stapeln Stack: -1 Läsning: "2" Tryck "2" på stapeln Stack: -1 2 Vi läser: "/" Vi beräknar kvoten, lägger resultatet på traven Stack: -0,5 Läser: "x" Tryck "x" på stapeln med värdet null Stack: -0,5x(null) Vi läser: "*" Tryck "*" på stack med värdet null Stack: -0,5 x(null) *(null) Vi läser "exp" Tryck "exp" på stacken med värdet null Stack: -0,5 x(null) *(null) exp(null) Optimeringsresultat: -0,5 x * exp

Denna metod inkluderar uppenbarligen inte alla möjliga optimeringsmetoder.

Implementeringsexempel

Artikeln " Omvänd polsk notation: implementeringsexempel " innehåller exempel på implementering av omvänd polsk notation i olika programmeringsspråk.

Praktiska implementeringar

Som en praktisk tillämpning av denna teknik kan vi nämna organisationen av bytekodkonfigurationerna för applikationslösningar för 1C:Enterprise- systemet . 1C ger ingen officiell bekräftelse , men användare av detta system på specialiserade forum tillhandahåller bevis och algoritmer som tillåter dekompilering av källtexter.

Litteratur

T. Pratt, M. Zelkowitz. Programmeringsspråk: Design och implementering = Terrence W. Pratt, Marvin V. Zelkowitz. Programmeringsspråk: Design och implementering. - 4:e upplagan. - Peter, 2002. - 688 sid. — (Datavetenskapens klassiker). - 4000 exemplar. - ISBN 5-318-00189-0 .

Anteckningar

↑ A. V. Aho, R. Seti, D. D. Ulman. Kompilatorer: principer, teknologier och verktyg. M .: "Williams", 2003. S. 51.

Se även

Programmeringsspråk som använder OPN som huvudspråk:

Vidare
faktor
postskriptum
BibTeX -stilmallsspråk