Reverzni poljski rekord nekada je bio osnova svijeta računalnog programera. Danas nije tako dobro poznata. Stoga, duhovita ilustracija, koja prikazuje "obrnuti" oblik poljske kobasice izvan peciva, još uvijek može biti nerazumljiva nekim poznatim programerima. Nije dobro objašnjenje za šalu, ali u ovom slučaju to će biti potpuno opravdano.
Infix zapis
Svi programeri i većina studenata poznaju uporabu operatora. Na primjer, u izrazu x + za dodavanje vrijednosti varijabli x i y koristi se simbol dodavanja. Manje je poznato da je znak posuđen iz matematike, nazvan infixnoy notation, zapravo veliki problem za strojeve. Takav operator uzima kao ulaz dvije vrijednosti, napisane lijevo i desno od njega. U programiranju je upotreba simbola s znakovima operacija opcionalna. Na primjer, x + y može biti napisan kao funkcija kompilacije (x, y), u kojoj kompajler na kraju transformira infix notaciju. Međutim, svi znaju matematiku previše dobro da ne koriste aritmetičke izraze koji tvore neku vrstu unutarnjeg mini jezika u gotovo svakom programskom jeziku.
Prevoditelji formula
Prvi doista uspješan programski jezik za Fortran postao je toliko uvelike jer su aritmetički izrazi (to jest, formule) pretvoreni u njega (prevedeni) u kôd, odakle potječe njegovo ime - FORmula TRANslation. Prije toga, na primjer, morali su snimatiu obliku funkcija čine (a, množite (b, c)). U Kobolu se problem uvođenja automatske transformacije formula smatrao vrlo teškim, jer su programeri morali napisati stvari poput Add A To B. Mutliply By C.
Što nije u redu s infix?
Problem leži u činjenici da operatori imaju takva svojstva kao prioritet i asocijativnost. Zbog toga, definicija infix funkcije postaje ne-trivijalan zadatak. Primjerice, prioritet množenja je veći od dodavanja ili oduzimanja, što znači da izraz 2 + 3 * 4 ne odgovara zbroju 2 i 3 pomnoženih s 4, kao što bi to bio slučaj kad bi se operateri izvršavali s lijeva na desno. Zapravo, trebate pomnožiti 3 sa 4 i dodati 2. Ovaj primjer ilustrira da izračunavanje infix izraza često zahtijeva promjenu redoslijeda operatora i njihovih operanada. Osim toga, morate koristiti zagrade kako bi bilješka izgledala jasnije. Na primjer, (2 + 3) * (4 + 5) ne može se pisati bez zagrada, jer 2 + 3 * 4 + 5 znači da trebate pomnožiti 3 sa 4 i dodati 2 i 5.
Redoslijed kojim je potrebno izračunati operatore zahtijeva dugo pamćenje. Zbog toga, učenici, početnici proučavaju aritmetiku, često dobivaju netočne rezultate, čak i ako su stvarne operacije izvedene ispravno. Potrebno je naučiti postupak operatora napamet. Prvo, moraju se izvesti akcije u zagradama, zatim umnožavanje i dijeljenje, te konačno dodavanje i oduzimanje. Ali postoje i drugi načini za pisanje matematičkih izraza jer je zapis infixa samo jedan od mogućih "malih jezika" koji se može dodati većem.
Prefiks i postfixOznaka
Dvije najpoznatije alternativne varijante je zapis operatora prije ili poslije operanada. Oni su poznati kao prefiks i postfix. Logika Jan Lukasiewicz smislila je prvu od njih dvadesetih godina. Živio je u Poljskoj, tako da se zapis naziva poljski. Postfix varijanta je dobila naziv obrnute poljske oznake (OPN). Jedina razlika između ove dvije metode leži u smjeru u kojem biste trebali čitati zapisnik (slijeva nadesno ili s desna na lijevo), stoga samo jednu od njih uzmite u obzir. U OPN-u, operator se snima nakon svojih operanada. Dakle, izraz AB + je primjer nalaza obrnutog Poljskog za A + B.
Neograničen broj operanada
Izravna prednost notacije je da je generalizirana n-adičkim operatorom, a infix zapis zapravo radi samo s dva operanda, što je po prirodi prikladno samo za binarne operacije. Na primjer, ABC @ je obrnuti poljski izraz koji koristi triadični znak koji pronalazi maksimalnu vrijednost A, B i C. U ovom slučaju, operater djeluje na 3 operanda s lijeve strane i odgovara pozivu funkcije @ (A, B, C). Ako pokušate napisati "@" znak kao infix, kao što je A @ BC ili nešto slično, onda postaje jasno da to jednostavno ne radi.
Prioritet se daje redoslijedom
Reverzni poljski zapis ima još jednu prednost da se prioritet operatora može predstaviti redoslijedom njihovog pojavljivanja. U ovom slučaju zagrade nikad neće biti potrebne, iako se mogu uvrstiti kao znakovi olakšavanja operacijakonverzija s zapisom infixa. Primjerice, AB + C * je jedinstveni ekvivalent (A + B) * C, budući da se množenje ne može izračunati dok se ne izvrši dodavanje drugog operanda za operaciju množenja. To jest, ako je AB + C * izračunat od strane jednog operatora odjednom, tada A B + C * - & gt; (A B +) * C - & gt; (A + B) * C.
Algoritam izračuna
U OPC-u, operator izgleda isto kao funkcija koja prihvaća kao dva argumenta vrijednosti ispisane s lijeve strane. Osim toga, to je prirodni zapis za uporabu u programskim jezicima, budući da tijek njegovih izračuna odgovara operacijama stog i potreba za raščlanjivanjem ne postoji. Na primjer, u OPC-u, izraz 5 + 6 * 7 će izgledati kao 567 *, +, i može se izračunati jednostavno skeniranjem s lijeva na desno i zapisivanjem vrijednosti u stog. Svaki put kad se pronađe transakcija, odabiru se dva gornja elementa memorije stroja, koristi se operator i rezultat se vraća u memoriju. Kada dođe do kraja izraza, rezultat izračuna pojavit će se na vrhu stog. Na primjer:
S = () 567 *, + stavi 5 u stog.
S = 6 7 *, + stavi 6 u stog.
S = (5 6) 7 *, + stavi 7 u stog.
S = (567) *, + odaberite 2 vrijednosti iz stog, primijenite * i stavite rezultat u stack.
S = (5 6 * 7) = (542) + odaberite 2 vrijednosti iz stog, primijenite + i stavite rezultat na stog.
S = (5 + 42) = (47) Izračun je završen, rezultat je na vrhu stog. Ovaj povratni algoritam poliranja može se provjeriti mnogo puta, ali svaki put kad radi, bez obzira na to kolikoaritmetički izraz je složen. OPN-ovi i hrpe su usko povezani. Donji primjer ilustrira kako se memorija može koristiti za izračunavanje vrijednosti obrnute poljske oznake. Manje je očito da možete koristiti stog, pretvarajući standardne infix izraze u TNF.
Primjeri programskih jezika
U jeziku Pascal, obrnuti poljski zapis je implementiran približno (prikazani dio programa). Čitanje brojeva i operatora u petlji naziva se postupak koji određuje je li oznaka broj ili znak operacije. U prvom slučaju, vrijednost se upisuje u stog, au drugom iznad dva gornja broja snopa, izvršava se odgovarajuća radnja i rezultat se sprema. toktype: = num; čitati (c); ako je u ['+', '-', '*', '/'] tada početi ako eoln onda cn: = 'drugo (cn); ako cn = '' onda slučaj iz '+': toktype: = add; '-': toktype: = sub; '*': toktype: = ja; '/': toktype: = div kraj drugo početi ako c = '-' onda sgn: = -1 drugo pogreška: = s & lt; & gt; '+'; c: cn kraj; if (ne greška) i (toktype = num) zatim getnumber; ako je vrsta & lt; & gt; num tada počinju: = ro; x: = ro; ako nema pogreške onda slučaj, toktype add: z: = x + y; sub: z: = x-y; me: z: = x * y; div: z: = x /y završno guranje (z); C-realizacija obrnutog poljskog zapisa (dan je dio programa): za (s = strtok (s, w); s; s = strtok (0 w)) {a = strtod (s & e); ako (e> s) gurate (a); #define rpnop (x) printf ("% c:", * s), b = (pop), a = (pop), pritisnite (x) drugo ako (* s == '+') rpnop (a + b) ) inače ako (* s == '-') rpnop (a - b); inače ako (* s == '*') rpnop (a * b); inače ako (* s == '/') rpnop (a /b); #undef rpnop}
Realiziranje hardvera
U vrijeme kada je računalna tehnologija bila vrlo skupa, smatralo se dobrom idejom prisiliti ljude da koriste OPN. Šezdesetih godina prošlog stoljeća, kao i danas, bilo je moguće kupiti kalkulatore koji rade obrnutoPoljski zapis. Da biste dodali 2 i 3, potrebno je da unesu 2, a zatim 3 i kliknu na gumb plus. Na prvi pogled, uvođenje operanada operateru činilo se teškim i teško zapamćenim, ali nakon nekog vremena neki su bili ovisni o tom načinu razmišljanja i nisu mogli razumjeti zašto drugi inzistiraju na glupom snimanju koje je toliko složeno i toliko ograničeno. Burroughs je čak izgradio mainframe koji nije imao nijedan drugi RAM osim stog. Jedino što je auto učinio - koristili su algoritme i metode obrnutog poljskog pisanja u središnji stack. Sve njezine operacije smatrane su OPN operatorima čije se djelovanje proširilo na n gornjih vrijednosti. Na primjer, naredba Return uzela je adresu s vrha hrpe itd. Arhitektura takvog stroja bila je jednostavna, ali ne dovoljno brza da bi se mogla natjecati s općenitijim arhitekturama. Mnogi, međutim, još uvijek žale zbog činjenice da takav jednostavan i elegantan pristup računalstvu, gdje je svaki program bio izraz nekog NPN-a, nije našao svoj nastavak. Jednom su kalkulatori s obrnutim poljskim rekordom uživali popularnost, a neki im i dalje daju prednost. Osim toga, razvijeni su jezici orijentirani na stog kao što je Forth. Danas se malo koristi, ali još uvijek uzrokuje nostalgiju od svojih bivših korisnika.
Pa što je smisao šale o obrnutoj poljskoj kobasici?
Ako uzmemo u obzir operatera za kobasice, onda u notnom zapisu treba biti unutar štruce, kao u uobičajenih hot dogova. U obrnutom poljskom zapisu, to je s desne stranedva poluvremena, spreman je da se između njih izračuna. Sada počinje najteži dio - senf. Već je na kobasici, koja je već izračunata kao unarni operater. Smatra se da bi senf također trebao biti prikazan kao nekultiviran i, prema tome, trebao bi biti pomaknut desno od kobasice.
