Käänteinen puolalainen merkintä - Reverse Polish notation

Postfix-dia.svg

Infix -merkintä

Käänteinen puolalainen merkintätapa ( RPN ), joka tunnetaan myös nimellä Polish Postfix merkintätapa tai yksinkertaisesti postfix merkintätapa , on matemaattinen jossa operaattorit seurata heidän operandit , toisin kuin Puolan merkintätapa (PN), jossa operaattorit ennen kohdemuuttujiaan. Se ei tarvitse sulkeita, kunhan jokaisella operaattorilla on kiinteä määrä operandeja . Nimityksen "puolalainen" viittaa kansallisuus on logician Jan Łukasiewicz , joka keksi puolalainen merkintätapa vuonna 1924.

Päinvastainen Puolan järjestelmää ehdotti vuonna 1954 Arthur Burks , Don Warren, ja Jesse Wright ja sen itsenäisesti uusittu jonka Friedrich Ludwig Bauer ja Edsger Dijkstra 1960-luvun alussa vähentää tietokoneen muistiin pääsyn ja käyttää pinoa arvioida ilmaisuja . Tämän järjestelmän algoritmeja ja merkintöjä laajensi australialainen filosofi ja tietojenkäsittelytieteilijä Charles L. Hamblin 1950-luvun puolivälissä.

1970- ja 1980 - luvuilla Hewlett-Packard käytti RPN: ää kaikissa pöytäkoneissaan ja kämmenlaskimissaan ja jatkoi sen käyttöä joissakin malleissa 2020-luvulle asti. Vuonna tietojenkäsittelytiede , kääntää Puolan merkintätapa käytetään pinon ohjelmointikieliä kuten Forth , stoalaista , PostScript , RPL ja Joy .

Selitys

Käänteisessä puolalaisessa merkinnässä operaattorit noudattavat operandejaan ; esimerkiksi lisätä 3 ja 4 yhteen, voisi kirjoittaa 3 4 + pikemminkin kuin 3 + 4 . Jos operaatioita on useita, operaattorit annetaan heti viimeisten operandiensa jälkeen (usein operaattori ottaa kaksi operandia, jolloin operaattori kirjoitetaan toisen operandin jälkeen); joten lauseke, joka on kirjoitettu tavanomaisella merkinnällä 3 - 4 + 5 , kirjoitettaisiin 3 4 - 5 + käänteisellä puolalaisella notaatiolla: 4 vähennetään ensin kolmesta ja sitten lisätään siihen 5. Puolalaisen käänteisen merkinnän etuna on, että se poistaa tarran sulkeista, joita infix -merkintä edellyttää . Vaikka 3-4 × 5 voidaan kirjoittaa myös 3 - (4 × 5) , se tarkoittaa jotain aivan muuta kuin (3-4) × 5 . Käänteisessä puolalaisessa merkinnässä edellinen voitaisiin kirjoittaa 3 4 5 × - , mikä tarkoittaa yksiselitteisesti 3 (4 5 ×) -mikä pienenee 3 20 - (joka voidaan edelleen pienentää -17); jälkimmäinen voidaan kirjoittaa 3 4 - 5 × (tai 5 3 4 - × , jos säilytetään samanlainen muotoilu), mikä tarkoittaa yksiselitteisesti (3 4 -) 5 × .

käytännön seuraukset

Vertailun vuoksi käänteisen puolalaisen merkintätestin testaus algebrallisella merkintätapauksella käänteisen puolalaisen on havaittu johtavan nopeampiin laskelmiin kahdesta syystä. Ensimmäinen syy on se, että puolalaiset käänteislaskimet eivät tarvitse lausekkeita suluissa, joten tyypillisten laskelmien suorittamiseksi on syötettävä vähemmän toimintoja. Lisäksi puolalaisten käänteislaskimien käyttäjät tekivät vähemmän virheitä kuin muuntyyppiset laskimet. Myöhempi tutkimus selvensi, että käänteinen puolalainen merkintä lisääntyi nopeuden vuoksi pikemminkin pienempään näppäinpainallukseen, joka tarvitaan tämän merkinnän syöttämiseen, kuin käyttäjien pienempään kognitiiviseen kuormaan. Anekdoottiset todisteet viittaavat kuitenkin siihen, että käänteinen puolalainen merkintä on käyttäjien vaikeampi oppia kuin algebrallinen merkintä.

Muuntaminen infix -merkinnöistä

Pääartikkeli: Shunting-yard-algoritmi

Edsger Dijkstra keksi vaihtokulkutie jaardin algoritmi muuntaa infix ilmauksia postfixin ilmaisuja (Käänteinen puolalainen notaatio), joten nimeksi, koska sen toiminta muistuttaa on rautatie ratapiha .

On muitakin tapoja tuottaa postfix -lausekkeita infix -lausekkeista. Useimpia operaattoripreferenssejä voidaan muokata postfix-lausekkeiden tuottamiseksi; erityisesti kun abstrakti syntaksipuu on muodostettu, vastaava postfix-lauseke annetaan puun yksinkertaisella tilauksen jälkeisellä läpikäynnillä .

Toteutukset

Historia

Ensimmäinen tietokoneet toteuttaa arkkitehtuurit mahdollistavat Käänteinen puolalainen notaatio olivat Englanti Electric Company : n KDF9 koneen, joka julkistettiin vuonna 1960 ja kaupallisesti saatavilla vuonna 1963, ja Burroughs B5000 , ilmoitti vuonna 1961 ja toimitettiin myös vuonna 1963:

Oletettavasti KDF9 -suunnittelijat saivat ideoita Hamblinin GEORGE (General Order Generator) -autokoodiohjelmointijärjestelmästä , joka on kirjoitettu DEUCE -tietokoneelle, joka on asennettu Sydneyn yliopistoon , Australiaan, vuonna 1957.

Yksi B5000: n suunnittelijoista, Robert S.Barton, kirjoitti myöhemmin kehittäneensä käänteisen puolalaisen notaation Hamblinista riippumattomana joskus vuonna 1958, kun hän oli lukenut Irving Copin vuoden 1954 symbolisen logiikan oppikirjan , josta hän löysi viittauksen puolalaiseen merkintätapaan. hän luki myös Jan Łukasiewiczin teoksia, ja ennen kuin hän oli tietoinen Hamblinin teoksesta.

Friden esitteli käänteisen puolalaisen merkintäpöytälaskinmarkkinoille Robert "Bob" Appleby Ragenin suunnittelemalla EC-130: lla , joka tuki nelitasoista pinoa kesäkuussa 1963. Seuraaja EC-132 lisäsi neliöjuuritoiminnon huhtikuussa 1965. Noin Vuonna 1966 Monroe Epic -laskin tuki myös nimeämätöntä syöttöjärjestelmää, joka muistuttaa RPN: ää.

Hewlett Packard

Pääartikkeli: HP -laskimet
Image
Myynnissä oleva Hewlett-Packardin "No Equals" -hattu 1980-luvulta-sekä ylpeys että viittaus RPN: ään

Hewlett-Packard insinöörit suunniteltu 9100A Desktop Laskin 1968 käänteisen Puolan merkintätapa vain kolme pinon tasolla, käänteinen Puolan merkintätapa variantti myöhemmin kutsutaan kolmen tason RPN . Tämä laskin popularisoi käänteistä puolalaista merkintää tiede- ja insinööriyhteisöjen keskuudessa. HP-35 , maailman ensimmäinen handheld tieteellinen laskin , esitteli klassinen neljän tason RPN 1972. HP käyttää Käänteinen puolalainen notaatio jokaisella laskin se myi, tieteellisten, taloudellisten tai ohjelmoitava, kunnes se otettiin käyttöön HP-10 lisääminen konelaskin vuonna 1977. Tuolloin HP oli johtava laskimien valmistaja ammattilaisille, mukaan lukien insinöörit ja kirjanpitäjät.

Myöhemmät laskimet, joissa oli LCD-näyttö 1980-luvun alussa, kuten HP-10C , HP-11C , HP-15C , HP-16C ja taloudellinen HP-12C- laskin käyttivät myös käänteistä puolalaista merkintää. Vuonna 1988 Hewlett-Packard esitteli yrityslaskurin, HP-19B , ilman käänteistä puolalaista merkintää, mutta sen vuoden 1990 seuraaja, HP-19BII , antoi käyttäjille mahdollisuuden käyttää algebrallista tai käänteistä puolalaista merkintää.

Noin vuonna 1987 HP esitteli RPL: n , olio-seuraajan puolalaisen merkinnän kääntämiseksi. Se poikkeaa klassisesta käänteisestä puolalaisesta merkinnästä käyttämällä pinoa, jota rajoittaa vain käytettävissä oleva muisti (kolmen tai neljän kiinteän tason sijasta) ja johon mahtuu kaikenlaisia ​​dataobjekteja (mukaan lukien symbolit, merkkijonot, luettelot, matriisit, grafiikka, ohjelmat) jne.) pelkästään numeroiden sijasta. Se muutti myös pinon käyttäytymistä siten, että se ei enää kopioi ylimpää rekisteriä pudotuksissa (koska rajoittamattomassa pinossa ei enää ole ylärekisteriä) ja ↵ Enteravaimen käyttäytymistä niin, että se ei enää kopioi arvoja Y: ksi tietyissä olosuhteissa, molemmat osa ns. automaattisen muistipinon tai toiminnallisen (muistipinon) erityissääntöjä klassisessa käänteisessä puolalaisessa merkinnässä joidenkin laskelmien helpottamiseksi ja näppäinpainallusten säästämiseksi, mutta jotka olivat myös osoittaneet toisinaan aiheuttavan sekaannusta käyttäjien keskuudessa, jotka eivät tunne nämä ominaisuudet. Vuosina 1990–2003 HP valmisti HP-48-sarjan graafisia RPL-laskimia ja esitteli vuonna 2006 HP 50g: n .

Vuodesta 2011 lähtien Hewlett-Packard tarjosi laskinmalleja 12C, 12C Platinum, 17bII+ , 20b , 30b , 33s , 35s , 48gII (RPL) ja 50g (RPL), jotka tukevat käänteistä puolalaista merkintää. Vaikka klassisia malleja emuloivat laskimet tukevat edelleen klassista käänteistä puolalaista merkintätapaa, uusissa käänteisissä puolalaisissa merkintämalleissa on käänteisen puolalaisen notaation muunnelma, jossa ↵ Enternäppäin toimii kuten RPL: ​​ssä. Tämä jälkimmäinen variantti tunnetaan joskus nimellä RPN . Vuonna 2013 HP Prime esitteli 128-tasoisen sisäänpääsyn RPN - muodon nimeltä Advanced RPN . Vuoden 2017 loppuun mennessä vain 12C, 12C Platinum, 17bii+, 35s ja Prime pysyvät aktiivisina HP -malleina, jotka tukevat käänteistä puolalaista merkintää.

WP 31S ja WP 34S

Yhteisön kehittämät laskimet WP 31S ja WP 34S , jotka perustuvat HP 20b/HP 30b -laitteistoalustaan, tukevat Hewlett-Packard-tyylistä klassista käänteistä puolalaista merkintää joko neljän tai kahdeksan tason pinolla. Seitsemätasoinen pino oli toteutettu tieteellisessä pöytälaskimessa MITS 7400C vuonna 1972 ja kahdeksan tason pinoa ehdotti jo John A. Ball vuonna 1978.

Sinclair Radionics

Britanniassa, Clive Sinclair n Sinclair tieteellinen ja tieteellinen Ohjelmoitava käytetyt mallit Käänteinen puolalainen notaatio.

Kommodori

Vuonna 1974 Commodore tuotti Minuteman *6 (MM6) ilman ↵ Enteravainta ja Minuteman *6X (MM6X) ↵ Enteravaimella, molemmat toteuttavat kaksitasoisen RPN- muodon . SR4921 RPN mukana variantin neljän tason RPN pinon tasot nimeltä X, Y, Z ja W (mieluummin kuin T). Toisin kuin Hewlett-Packardin käänteinen puolalainen merkintätapa, W täytettiin 0: lla sen sijaan, että sen sisältö toistettaisiin pinopisaralla.

Prinztronic

Prinz ja Prinztronic olivat brittiläisten Dixons- valokuva- ja elektroniikkamyymälöiden vähittäiskauppaketjun omia tuotemerkkejä , jotka myöhemmin muutettiin Currys Digital -myymälöiksi, ja niistä tuli osa DSG Internationalia. Erilaisia ​​laskinmalleja myytiin 1970 -luvulla Prinztronic -tuotemerkillä, kaikki muut ovat niitä valmistaneet.

Näiden joukossa oli PROGRAM -ohjelmoitava tieteellinen laskin, jossa oli käänteinen puolalainen merkintä.

Heathkit

Aircraft navigointitietokone Heathkit OC-1401 / OCWCP-1401 käytetty viiden tason RPN 1978.

Neuvostoliitto

Neuvostoliiton ohjelmoitavat laskimet ( MK-52 , MK-61 , B3-34 ja aiemmat B3-21- mallit) käyttivät käänteistä puolalaista merkintää sekä automaattisessa tilassa että ohjelmoinnissa. Nykyaikaiset venäläiset laskimet MK-161 ja MK-152 , jotka on suunniteltu ja valmistettu Novosibirskissa vuodesta 2007 ja jotka tarjoaa Semico, ovat taaksepäin yhteensopivia niiden kanssa. Niiden laajennettu arkkitehtuuri perustuu myös käänteiseen puolalaiseen merkintään.

Muut

Nykyisiä toteutuksia, joissa käytetään käänteistä puolalaista merkintää, ovat:

Katso myös

Viitteet

Lue lisää

Ulkoiset linkit