Käänteinen puolalainen merkintä

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 28.9.2021 tarkistetusta versiosta . tarkastukset vaativat 2 muokkausta .

Reverse Polish notation (RPN ) on tapa kirjoittaa matemaattisia ja loogisia lausekkeita , joissa operandit sijaitsevat ennen operaatiomerkkejä . Kutsutaan myös nimellä käänteinen hakasuljeton merkintä , postfix-merkintä , Lukasiewiczin hakasuljeton symboliikka , puolalainen käänteismerkintä , POLIZ .

Pinokone on algoritmi, joka suorittaa laskutoimituksia käyttämällä käänteistä puolalaista merkintää (katso alla esimerkki lausekkeiden arvioinnista ).

Historia

Käänteinen puolalainen notaatio (RPN) kehitti australialainen filosofi ja tietokoneteoreetikko Charles Hamblin 1950-luvun puolivälissä perustuen puolalaiseen notaatioon , jota puolalainen matemaatikko Jan Lukasiewicz ehdotti vuonna 1920 . Hamblinin työ esiteltiin konferenssissa kesäkuussa 1957 ja julkaistiin vuosina 1957 ja 1962 .

Ensimmäiset tietokoneet, jotka tukivat käänteistä puolalaista merkintää, olivat englantilaisen Electric Companyn KDF9 , joka julkistettiin vuonna 1960 ja julkaistiin (näytettiin myyntiin) vuonna 1963 , ja vuonna 1961 julkistettu amerikkalainen Burroughs B5000 , joka julkaistiin samana vuonna 1963. Yksi B5000:n suunnittelijat R. S. Barton kirjoittivat myöhemmin, että hän kehitti käänteisen puolalaisen merkinnän Hamblinista riippumatta noin 1958 lukiessaan kirjaa symbolisesta logiikasta ja ennen kuin hän tutustui Hamblinin työhön.

Friden toi ylijännitesuojan pöytälaskimiin kesäkuun 1964 EC-130:lla. Ja vuonna 1968 Hewlett-Packardin insinöörit kehittivät 9100A - pöytälaskimen , jossa on ylijännitesuojan tuki. Tämä laskin teki käänteisestä puolalaisesta merkinnästä suositun tutkijoiden ja insinöörien keskuudessa, vaikka varhaisessa 9100A-mainoksessa ei mainittu ylijännitesuojaa. Vuonna 1972 HP-35 SPD - yhteensopivasta laskimesta tuli ensimmäinen tieteellinen taskulaskin .

Vuonna 1971 ilmestyi alkuperäinen ohjelmointikieli Forth , jonka kielikoneessa on kaksipinorakenne ja jossa kaikki laskelmat suoritetaan pinolle . Tällä kielellä OPN on luonnollinen tapa kirjoittaa mitä tahansa dataoperaatiota, vaikka haluttaessa on mahdollista toteuttaa aritmeettisten operaatioiden tavallinen ( infix ) merkintätapa.

Pysäytyslaitetta käytettiin vuonna 1976 julkaistussa Neuvostoliiton suunnittelulaskimessa B3-19M (yhteisesti kehitetty DDR:n kanssa). Kaikki Neuvostoliitossa 1980-luvun loppuun asti valmistetut ohjelmoitavat mikrolaskimet , paitsi Elektronika MK-85 ja Elektronika MK-90 , käyttivät pysäytintä - se oli helpompi toteuttaa ja mahdollisti ohjelmointilaskelmien suorittamisen pienemmällä laskurilla. komentojen määrä verrattuna tavanomaiseen algebralliseen merkintään, ja ohjelmamuistin määrä näissä malleissa on aina ollut kriittinen resurssi. Pidätintä käytetään nykyaikaisissa venäläisissä ohjelmoitavissa laskimissa " Elektronika MK-152 " ja " Elektronika MK-161 ", mikä varmistaa niiden yhteensopivuuden Neuvostoliiton laskimille kirjoitettujen ohjelmien kanssa.

Määritelmä

Induktiivisen määritelmän antamiseksi jälkiliitteen merkinnällä [1] merkitään lausekkeet infix-merkinnöissä , , , niiden vastaavat lausekkeet postfix-merkinnöissä , vastaavasti ; on mielivaltainen binäärioperaattori, niin: $E$ $E_1$ $E_2$ $\piste E$ $\piste E_1$ $\piste E_2$ $o$

1. Jos - muuttuja tai vakio, eli . $E$ $\piste E$ $E$

2. Jos on muodon ilmaus , se on . $E$ $E_1 tai E_2$ $\piste E$ $\piste E_1 \piste E_2 o$

3. Jos on muodon ilmaus , se on . $E$ $(E_1)$ $\piste E$ $\piste E_1$

Kuvaus

Käänteisen puolan merkinnän erottuva piirre on, että kaikki argumentit (tai operandit ) sijoitetaan ennen operaatiomerkkiä. Yleisesti ottaen levy näyttää tältä:

Operaatiosarjatietue koostuu operandeista ja operaatiomerkeistä. Lausekkeen operandit erotetaan välilyönnillä kirjoitettaessa.
Lause luetaan vasemmalta oikealle. Kun lausekkeessa esiintyy operaattorimerkki, vastaava operaatio suoritetaan kahdelle viimeiselle sitä edeltävälle operandille siinä järjestyksessä, jossa ne kirjoitetaan. Toiminnon tulos korvaa sen operandijonon ja sen etumerkin lausekkeessa, minkä jälkeen lauseke arvioidaan edelleen saman säännön mukaan.
Lausekkeen arvioinnin tulos on viimeisimmän arvioidun operaation tulos.

Harkitse esimerkiksi lausekkeen arviointia 7 2 3 * −(vastaava lauseke infix-merkinnässä: 7 − 2 * 3).

Operaation ensimmäinen merkki on "*", joten kertolasku suoritetaan ensin operandeille 2 ja 3 (ne ovat viimeisiä ennen merkkiä). Lauseke muunnetaan sitten muotoon 7 6 −(kertolasku - 6 - korvaa kolminkertaisen "2 3 *").
Operaation toinen merkki on "−". Operandeille 7 ja 6 suoritetaan vähennysoperaatio.
Laskenta suoritettu. Viimeisen operaation tulos on 1, tämä on lausekkeen arvioinnin tulos.

Käänteisen puolalaisen merkinnän ilmeinen laajennus koskemaan unaarista, kolmiosaista ja operaatioita millä tahansa muulla operandimäärällä: käytettäessä tällaisten operaatioiden merkkejä lausekkeen arvioinnissa, operaatiota sovelletaan vastaavaan määrään viimeksi havaittuja operandeja.

Käänteisen puolan merkinnän ominaisuudet ovat seuraavat:

Toimintojen suoritusjärjestys määritellään yksiselitteisesti lausekkeen operaatiomerkkien järjestyksen avulla, joten ei tarvitse käyttää hakasulkuja ja esitellä toimintojen prioriteetteja ja assosiatiivisuutta.
Toisin kuin infix-merkintä, ei ole mahdollista käyttää samoja merkkejä unaari- ja binääritoimintojen kirjoittamiseen. Joten infix-merkinnässä lauseke 5 * (−3 + 8)käyttää miinusmerkkiä unaarioperaation symbolina (luvun etumerkin muutos), ja lauseke (10 − 15) * 3käyttää samaa merkkiä binäärioperaation (vähennyslasku) kuvaamiseen. Erityisen toiminnon määrää hahmon sijainti. Käänteinen puolalainen merkintätapa ei salli tätä: merkintä 5 3 − 8 + *(ensimmäisen lausekkeen ehdollinen analogi) tulkitaan virheelliseksi, koska on mahdotonta määrittää, että "miinus" numeroiden 5 ja 3 jälkeen ei tarkoita vähennyslaskua; seurauksena yritetään ensin laskea 5 − 3, sitten 2 + 8, minkä jälkeen käy ilmi, että kertooperaatioon ei ole tarpeeksi operandeja. Jos haluat edelleen kirjoittaa tämän lausekkeen, sinun on joko muotoiltava se uudelleen (esimerkiksi kirjoittamalla lauseke lausekkeen sijasta − 3) 0 − 3tai otettava käyttöön erillinen nimitys merkin vaihtotoiminnolle, esimerkiksi "±": 5 3 ± 8 + *.
Infix-merkinnän lisäksi OPN:ssä yksi ja sama laskutoimitus voidaan kirjoittaa useissa eri versioissa. Esimerkiksi (10 − 15) * 3OPN:n lauseke voidaan kirjoittaa muodossa 10 15 − 3 *, tai voit kirjoittaa sen muodossa3 10 15 − *
Sulkujen puuttumisen vuoksi käänteinen puolalainen merkintä on lyhyempi kuin infix. Tästä johtuen laskimilla laskettaessa operaattorin työn nopeus kasvaa (painattujen näppäinten määrä vähenee) ja ohjelmoivissa laitteissa laskelmia kuvaavien ohjelman osien äänenvoimakkuus pienenee. Jälkimmäinen voi olla tärkeä kannettaville ja sulautetuille tietokonelaitteille, joilla on vakavat rajoitukset muistin määrälle.

Pinolaskelmat

Yleinen järjestys

Lausekkeiden arvioinnin automatisointi käänteisessä puolan merkinnässä perustuu pinon käyttöön . Pinokoneen laskenta-algoritmi on alkeellinen:

Symbolien käsittely
- Jos operandi annetaan syötteenä, se työnnetään pinon yläosaan.
- Jos syötteeseen annetaan operaatiomerkki, vastaava toiminto suoritetaan tarvittavalle määrälle pinosta ponnattuja arvoja, jotka on otettu lisäysjärjestyksessä. Suoritetun toimenpiteen tulos asetetaan pinon päälle.
Jos syötettyä merkistöä ei ole käsitelty kokonaan, siirry vaiheeseen 1.
Kun syötetty merkistö on käsitelty kokonaan, lausekkeen arvioinnin tulos on pinon päällä.

Pinokoneen toteuttaminen sekä ohjelmistossa että laitteistossa on erittäin yksinkertaista ja voi olla erittäin tehokasta. Käänteinen puolalainen merkintätapa on täysin yhtenäinen - se kirjoittaa periaatteessa unaari-, binääri-, kolmi- ja kaikki muut toiminnot sekä funktiokutsut samalla tavalla, mikä mahdollistaa tietokonelaitteiden suunnittelun monimutkaisuuden samalla kun laajennat tuettujen toimintojen joukkoa. Tästä syystä joissakin tieteellisissä ja ohjelmoitavissa olevissa laskimissa käytettiin käänteistä puolalaista merkintää.

Lausekkeen arviointiesimerkki

Infix-lauseke GRE:ssä voidaan kirjoittaa näin: $(1 + 2)\ kertaa 4 + 3$ 1 2 + 4 × 3 +

Laskenta suoritetaan vasemmalta oikealle, syöte tulkitaan alla olevan taulukon mukaisesti (pinon tila toimenpiteen jälkeen, pinon yläosa on korostettu punaisella ):

Syöte	Operaatio	Pino
yksi	laittaa pinoon	yksi
2	laittaa pinoon	1, 2
+	lisäys	3
neljä	laittaa pinoon	3, 4
*	kertolasku	12
3	laittaa pinoon	12, 3
+	lisäys	viisitoista

Tulos, 15, on pinon yläosassa laskennan lopussa.

"Enter"-näppäin (merkitty laskimissa "Enter" tai symboli "↑") toimii operandin erottimena, kun kaksi operandia on välittömästi vierekkäin. Jos operandia seuraa operaatiomerkki , sen painamista ei tarvita, tämä vähentää toimintojen määrää, jotka on suoritettava tuloksen saamiseksi.

Muunnetaan infix-merkinnästä

Edsger Dijkstra keksi algoritmin lausekkeiden muuntamiseksi infix-merkinnästä IPV:hen. Algoritmia kutsuttiin "järjestelypihaksi" sen toimintojen samankaltaisuuden vuoksi rautateiden järjestelypihoilla tapahtuvan kanssa. Infix-merkintä on useimpien ihmisten käyttämä matemaattisen merkintätavan muoto (esimerkiksi 3 + 4tai 3 + 4 * (2 − 1)). Kuten SPV-laskentaalgoritmi , myös järjestelypiha-algoritmi perustuu pinoon. Konversiossa on mukana kaksi tekstimuuttujaa: syöttö- ja lähtömerkkijonot. Muunnosprosessi käyttää pinoa, joka tallentaa toiminnot, joita ei ole vielä lisätty tulostemerkkijonoon. Muunnosohjelma lukee syötetyn merkkijonon merkki kerrallaan peräkkäin (merkki ei välttämättä ole kirjain), suorittaa jokaisessa vaiheessa joitain toimintoja sen mukaan, mikä merkki luettiin.

Yksinkertainen esimerkki

Sisäänkäynti:3 + 4

Lisää 3tulosriville (jos luku luetaan, se lisätään välittömästi tulosriville).

Työnnä +(tai sen tunniste) käyttöpinoon.

Lisää 4lähtöriville.

Olemme lukeneet koko lausekkeen, nyt työnnämme kaikki pinossa jäljellä olevat toiminnot tulosriville. Esimerkissämme pino sisältää vain +.

Lähtölinja:3 4 +

Tässä esimerkissä näkyy joitain sääntöjä: kaikki numerot siirretään lähtöriville heti lukemisen jälkeen; Kun lauseke luetaan kokonaan, kaikki pinon jäljellä olevat toiminnot työnnetään tulosriville.

Algoritmi

Vaikka luettavia hahmoja on enemmän:

Luimme seuraavan hahmon.
Jos merkki on numero tai postfix-funktio (esimerkiksi ! - factorial ), lisää se tulostemerkkijonoon.
Jos symboli on etuliitefunktio (esimerkiksi sin - sini ), työnnä se pinoon.
Jos hahmo on avoin sulkumerkki, työnnä se pinoon.
Jos merkki on sulkeva hakasulku:

Kunnes pinon ylin elementti on avaussulku, ponna elementit pois pinosta tulostemerkkijonoon. Tämä poistaa avaussulun pinosta, mutta ei lisää sitä tulostemerkkijonoon. Jos pino päättyi ennen kuin tapasimme aloitussulkeen, tämä tarkoittaa, että joko erotin on asetettu väärin lausekkeeseen tai hakasulkeet eivät täsmää.

Jos sulkuja on eri tyyppejä, myös vertaansa vailla olevan hakasulkeen ilmestyminen osoittaa virheen. Jos jotkut hakasulkeet ovat samanaikaisesti funktioita (esimerkiksi [x] on kokonaislukuosa ), lisäämme tämän funktion symbolin tulostemerkkijonoon.

Jos symboli on binäärioperaatio o1 , niin:

1) kun pinon yläosassa on etuliitetoiminto ... … TAI toiminnolla pinon yläosassa on korkeampi prioriteetti tai sama prioriteettitaso kuin o1 … TAI pinon yläosan operaatio on vasen assosiatiivinen prioriteetin ollessa o1 ... työnnä pinon ylin elementti tulostemerkkijonoon; 2) työnnä operaatio o1 pinoon.

Kun syöttömerkkijono on ohi, siirrä kaikki merkit pinosta tulostemerkkijonoon. Vain operaatiosymbolit saivat jäädä pinoon; jos ei ole, lauseke ei vastaa sulkeita.

Rajoitukset ja muutokset

Algoritmi olettaa, että lähdemerkkijono on oikea (kaikkia virheitä ei tarkisteta) ja kaikki etuliite/postfix-funktiot ovat unaarisia.

Katso pääartikkelista muokkaus monipaikkafunktioille, joissa on kiinteä määrä argumentteja .

Operaatioille, kuten -x , jotka ovat sekä binaarisia että unaarisia, tarvitaan muutos: kun tällainen operaatio löytyy, järjestelmä tarkastelee edellistä merkkiä ja määrittää, onko miinus binääritoiminto vai unaarifunktio. Vastaavasti pino ja NPV tarvitsevat eri symboleja binääri- ja unaarimiinuksille.

Monimutkainen esimerkki

Prioriteetit :

korkein: lausekkeet suluissa ( )
korkea: ^
keskiverto: * /
alhainen: + -

Syöttö: 3 + 4 * 2 / (1 - 5)^2 Luimme "3" Lisää "3" tulostemerkkijonoon Lähtö: 3 Luimme "+" Laita "+" pinoon Lähtö: 3 Pino: + Luimme "4" Lisää "4" tulostemerkkijonoon Lähtö: 3 4 Pino: + Luemme "*" Työnnä "*" pinoon Lähtö: 3 4 Pino: + * Luimme "2" Lisää "2" tulostemerkkijonoon Tulos: 3 4 2 Pino: + * Luemme "/" Pop "*" pinosta lähtömerkkijonoon, paina "/" pinoon Tulos: 3 4 2 * Pino: + / Luemme "(" Työnnä "(" pinoon Tulos: 3 4 2 * Pino: + / ( Luimme "1" Lisää "1" tulostemerkkijonoon Tulos: 3 4 2 * 1 Pino: + / ( Luemme "-" Paina "-" pinoon Tulos: 3 4 2 * 1 Pino: + / ( − Luimme "5" Lisää "5" tulostemerkkijonoon Tulos: 3 4 2 * 1 5 Pino: + / ( - Luemme ")" Pop "−" pinosta lähtömerkkijonoon, pop "(" Tulos: 3 4 2 * 1 5 − Pino: + / Luimme "^" Laita "^" pinoon Tulos: 3 4 2 * 1 5 − Pino: + / ^ Luimme "2" Lisää "2" tulostemerkkijonoon Tulos: 3 4 2 * 1 5 − 2 Pino: + / ^ Ilmaisun loppu Kaikkien elementtien lisääminen pinosta merkkijonoon Lähtö: 3 4 2 * 1 5 − 2 ^ / +

Lausekkeen optimointi

Jos kirjoitat tulkkia, alkuperäisen lausekkeen muuntamisen jälkeen käänteiseksi puolalaiseksi merkintämuodoksi saatu tulostemerkkijono voidaan tallentaa alkuperäisen lausekkeen tilalle myöhempää tulkintaa varten. Käänteinen puolalainen notaatio antaa myös tietokoneen yksinkertaistaa lausekkeita.

Esimerkki lausekkeen yksinkertaistamisalgoritmista

Harkitse algoritmia, joka suorittaa vakioiden esilaskennan lausekkeessa. OPN:ssä annetaan lauseke. Tarvitsemme pinon sekatietojen (numerot ja operaattorit) tallentamiseen.

Algoritmi on samanlainen kuin lausekkeiden arvioinnissa käytetty. Skannaamme lausekkeen vasemmalta oikealle.

Niin kauan kuin luettavia merkkejä on:

Luimme seuraavan hahmon.
Jos merkki on numero, työnnä se pinoon.
Jos merkki on muuttuja, olettaen, että muuttuja on null , työnnä merkki pinoon.
Jos symboli on operaattori:
1) (jos kaikilla pinon operaattoriargumenteilla on muu arvo kuin null ) ponna operaattoriargumentit pinosta ja työnnä operaation tulos pinoon;
2) (jos ainakin yksi argumenteista on null ) olettaen, että operaation tulos on null , laitamme pinoon operaattorisymbolin.

Kun koko lauseke on tutkittu, pinoon jää optimoitu lauseke (lausekkeen lauseet ovat pinossa käänteisessä järjestyksessä).

Esimerkki algoritmin toiminnasta

Ilmaisu Infix-merkintä: exp(-1/2*x) Käänteinen puolalainen merkintä: -1 2 / x * exp Lukema: "-1" Paina "-1" pinoon Pino: -1 Lukeminen: "2" Työnnä "2" pinoon Pino: -1 2 Luemme: "/" Laskemme osamäärän, laitamme tuloksen pinoon Pino: -0,5 Lukeminen: "x" Työnnä "x" pinoon, jonka arvo on null Pino: -0,5x (nolla) Luemme: "*" Paina "*" pinoon, jonka arvo on null Pino: -0,5 x (nolla) * (nolla) Luimme "exp" Työnnä "exp" pinoon, jonka arvo on null Pino: -0,5 x(nolla) *(nolla) exp(nolla) Optimoinnin tulos: -0,5 x * exp

Tämä menetelmä ei tietenkään sisällä kaikkia mahdollisia optimointimenetelmiä.

Toteutusesimerkkejä

Artikkeli " Käänteinen puolalainen merkintä: toteutusesimerkkejä " sisältää esimerkkejä käänteisen puolan merkinnän toteutuksesta eri ohjelmointikielillä.

Käytännön toteutukset

Tämän tekniikan käytännön sovelluksena voimme mainita 1C:Enterprise -järjestelmän sovellusratkaisujen tavukoodikonfiguraatioiden organisoinnin . 1C ei anna virallista vahvistusta , mutta tämän järjestelmän käyttäjät erikoistuneilla foorumeilla tarjoavat todisteita ja algoritmeja, jotka mahdollistavat lähdetekstien purkamisen .

Kirjallisuus

T. Pratt, M. Zelkowitz. Ohjelmointikielet: suunnittelu ja toteutus = Terrence W. Pratt, Marvin V. Zelkowitz. Ohjelmointikielet: suunnittelu ja toteutus. - 4. painos. - Peter, 2002. - 688 s. — (Tietojenkäsittelytieteen klassikot). - 4000 kappaletta. - ISBN 5-318-00189-0 .

Muistiinpanot

↑ A. V. Aho, R. Seti, D. D. Ulman. Kääntäjät: periaatteet, tekniikat ja työkalut. M .: "Williams", 2003. S. 51.

Katso myös

Ohjelmointikielet, jotka käyttävät OPN:ää pääasiallisena:

Eteenpäin
tekijä
jälkikirjoitus
BibTeX- tyylitaulukon kieli