Poljski poljski zapis: algoritam, metode i primjeri

Polazni poljski zapis bio je nekad osnova svijeta računalnog programera. Danas to nije tako dobro poznato. Stoga, komična ilustracija koja prikazuje "preokrenuti" poljski kobasica izvan kolača može i dalje biti pogrešno razumljiva od strane nekih poznatih programera. Nije baš dobro objasniti šalu, ali u ovom slučaju to će biti potpuno opravdano.

Unos infixa

Svi programeri i većina studenata su upoznati s uporabom operatera. Na primjer, u izrazu x + y, dodatni znak se koristi za zbrajanje vrijednosti varijabli xi y. Manje poznato je da je ovo posuđeno iz matematičke oznake, nazvano infix notacija, zapravo veliki problem za strojeve. Takav operator uzima kao unos dvije vrijednosti napisane slijeva i desno od njega. Kod programiranja oznaka s oznakama operacije nije obavezna. Na primjer, x + y se može napisati kao funkcija za dodavanje (x, y) na koju prevoditelj na kraju pretvara infix zapis. Međutim, svatko dobro poznaje matematiku da ne upotrebljava aritmetičke izraze koji tvore neku vrstu unutarnjeg mini-jezika u gotovo svakom programskom jeziku.

Prevoditelji formula

Prvi stvarno uspješna Fortran programski jezik je postao tako velikoj mjeri, jer aritmetički izraz (npr formula ..) Ona pretvara (broadcast) u kodu, otuda i naziv za to - Formula prijevod. Prije su morali biti zapisani, na primjer, u obliku funkcija za dodavanje (a, pomnožiti (b, c)). U Kobolu problem provedbe automatske pretvorbe formule smatra se vrlo teškim, budući da su programeri morali napisati stvari poput Add A To B Mutliply By C.

Što nije u redu s infixom?

Problem je u tome što operatori imaju svojstva kao što su prioritet i asocijativnost. Zbog toga definicija funkcije infix postaje nevjerodostojan zadatak. Na primjer, množenje ima veću prednost od toga ili oduzimanja, što znači da je izraz 2 + 3 * 4 nije jednak zbroju 2 i 3, pomnožen 4, jer bi se u obavljanju operatora s lijeva na desno. U stvari, pomnožite 3 po 4 i dodajte 2. Ovaj primjer ilustrira da procjena infix izraza često zahtijeva promjenu redoslijeda operatera i njihovih operanda. Osim toga, moramo upotrijebiti zagrade kako bismo jasnije vidjeli oznaku. Na primjer, (2 + 3) * (4 + 5) ne može biti napisan bez zagrada, jer 2 + 3 * 4 + 5 znači da morate pomnožiti 3 po 4 i dodati 2 i 5.

Redoslijed kojim se operatori moraju izračunati zahtijeva dugu memoriju. Zbog toga učenici koji počinju učiti aritmetiku često dobivaju pogrešne rezultate, čak i ako se u stvari radi ispravno. Potrebno je naučiti redoslijed djelovanja operatora srcem. Prvo, moraju se provesti akcije u zagradama, zatim množenje i podjela, i konačno dodavanje i oduzimanje. Ali postoje i drugi načini pisanja matematičkih izraza, jer je infix notacija samo jedan od mogućih "malih jezika" koji se mogu dodati u veće.

Prefiks i postfix oznaka

Dvije najpopularnije alternative su snimka operatora prije ili poslije operanda. Poznate su kao prefiks i postfix oznake. Logičar Jan Lukasevich izumio je prvi od njih dvadesetih godina 20. stoljeća. Živio je u Poljskoj, pa se rekord zove poljski. Postfixova verzija, odnosno, nazvana je obrnuto poljski zapis (ARF). Jedina razlika između tih dviju metoda jest smjer u kojemu ćete čitati zapis (s lijeva na desno ili s desna na lijevo), pa je dovoljno razmotriti samo jedan od njih detaljno. U odvodniku, operater je napisan nakon operanda. Dakle, izraz AB + je primjer obrnutog poljskog zapisa za A + B.

Neograničeni broj operandi

Neposredna prednost zapis je da sumira n-adske operatera i utjerati notacija stvarno radi samo s dva operanda, t. E. su sami po sebi prikladan samo za binarne operacije. Na primjer, ABC `je obrnuto poljski izraz koristi trijadnoj oznaku koja je maksimalna vrijednost od A, B i C. U ovom slučaju operator djeluje na lijevo od tri operanda same i odgovara na funkciju poziva @ (A, B, C). Ako pokušate napisati @ simbol kao utjerati, kao što je @ BC ili nešto slično, postaje jasno da to jednostavno ne radi.

Prioritet je dan po nalogu

Polazni poljski unos ima drugu prednost u tome što se prioritet operatora može predstavljati redoslijedom njihovog pojavljivanja. U ovom slučaju, zagrade nikada neće biti potrebne, iako se mogu uključiti kao simbol transakcije kako bi se olakšalo pretvorbu s infix zapisom. Na primjer, AB + C * - jednoznačan ekvivalent (A + B) + C, tako da se ne može množenje izračunati do toga izvedena, što daje drugi operanda umnožavanja. To jest, ako se izračunava AB + C * za jednog operatora odjednom, dobivamo A B + C * -> (A B +) * C -> (A + B) * C.

Algoritam izračuna

U OPN-u, operator izgleda kao funkcija koja uzima kao argumente dvije vrijednosti napisane lijevo od nje. Dodatno, ovo je prirodna zapis za uporabu u programskim jezicima, budući da je njezin izračun korespondirao sa stack operacijama i da nema potrebe za parsiranjem. Na primjer, u ARS, izraz 5 + 6 * 7 izgledat će kao 5, 6, 7 *, + i može se izračunati jednostavno skeniranjem s lijeva na desno i pisanjem vrijednosti u stog. Svaki put kada se pojavi znak rada, odabiru se vrh 2 stavke iz memorije uređaja, operater se primjenjuje i rezultat se vraća u memoriju. Kada se dosegne kraj izraza, rezultat izračuna bit će na vrhu stogova.

Na primjer:

• S = () 5, 6, 7, *, + staviti 5 na stog.
• S = (5) 6, 7, *, + staviti 6 na stog.
• S = (5, 6) 7, *, + staviti 7 na stog.
• S = (5, 6, 7) *, + odaberite 2 vrijednosti iz snopa, primijenite * i stavite rezultat na snop.
• S = (5, 6 * 7) = (5, 42) + odaberite 2 vrijednosti iz stupa, primijenite + i stavite rezultat na stog.
• S = (5 + 42) = (47) izračun je završen, rezultat je na vrhu stog.

Ovaj algoritam obrnutog poljski zapis može se provjeravati mnogo puta, ali svaki put kad će raditi, bez obzira koliko složen aritmetički izraz.

Otpornik i hrpe usko su povezani. Gore navedeni primjer pokazuje kako se memorija može upotrijebiti za izračunavanje vrijednosti u inverznoj poljskoj notaciji. Manje je očito da možete koristiti stog pretvaranjem standardnih infix izraza na odvodnik.

Primjeri u programskim jezicima

Na Pascalovom jeziku obrnuto poljski zapis se provodi otprilike ovako (dio programa je dan).

Za čitanje brojeva i operatora u petlji, poziva se postupak koji određuje je li token broj ili znak operacije. U prvom slučaju, vrijednost je napisana na snop, dok u drugom slučaju, odgovarajuća akcija se vrši na prva dva broja snopa i rezultat se sprema.

toktype: = broj;

čitati (c);

ako se s [`+`, `-`, `*`, `/`] zatim počinje

ako eoln zatim cn: = `` drugo čita (cn);

ako cn = `tada

slučaj s

`+`: toktype: = add- `-`: toktype: = pod;

`*`: toktype: = mul- `/`: toktype: = div

kraj

drugo počinje

ako je c = `-` onda sgn: = -1 druga pogreška: = s <> `+`;

s: = cn

kraj

kraj;

ako (ne pogreška) i (toktype = num) zatim getnumber;

ako toktype <> num onda početi

y: = roorx: = rop;

ako nije pogreška onda

slučaj tipa

dodati: z: = x + y-sub: z: = x-y-mul: z: = x * y-div: z: = x /

kraj

push (z);

C-implementacija obrnute poljski zapis (dio programa je dan):

za (s = strtok (s, w) -s-s = strtok (0, w)) {

a = strtod (s, e);

ako (e> s) gurnu (a);

#define rpnop (x) printf ("% s:", s), b = pop (), a = pop (), push (x)

drugo ako (* s == `+`) rpnop (a + b);

drugo ako (* s == `-`) rpnop (a - b);

drugo ako (* s == `*`) rpnop (a * b);

drugo ako (* s == `/`) rpnop (a / b);

#undef rpnop

}

Implementacija hardvera

U one dane, kada je računalna tehnologija bila vrlo skupo, smatralo se dobrom idejom prisiliti ljude na korištenje OPN-a. U 1960-ima, kao i danas, bilo je moguće kupiti kalkulatore koji rade u obrnutom poljskom snimanju. Da biste dodali 2 i 3 u njih, unesite 2, a zatim 3 i pritisnite gumb plus. Na prvi pogled, ulazni operandi za operatera činilo komplicirano i teško zapamtiti, ali nakon nekog vremena neki su ovisni o tom načinu razmišljanja i ne mogu shvatiti zašto drugi inzistiraju na glupe utjerati, koji je tako kompliciran i tako je ograničen.

Burroughs je čak i izgradio glavni okvir koji nije imao drugog RAM-a, osim stupa. Jedino što je stroj učinio bilo je primijeniti algoritme i metode za preokret poljski zapis na središnji stog. Sva njegova djelovanja smatrana su OPN operaterima, čija je akcija proširena na n gornje vrijednosti. Na primjer, naredba Povratak preuzela je adresu s vrha stog itd. Arhitektura ovog stroja bila je jednostavna, ali nije dovoljno velika da se natječe s općenitim arhitekturama. Mnogi, međutim, još uvijek žale što takav jednostavan i elegantan pristup računanju, gdje je svaki program bio izraz OPN, nije pronašao njen nastavak.

U jednom trenutku kalkulatori s obrnutim poljskim snimkama bili su popularni, a neki ih još uvijek vole. Osim toga, razvijeni su i jezgreni jezici kao što je Forth. Danas se malo koristi, ali i dalje uzrokuje nostalgiju bivših korisnika.

Dakle, što je to šala o povratku poljski kobasica?

Ako uzmete u obzir operatera kobasice, a zatim u infix zapis, ona bi trebala biti unutar valjka, kao u normalnom vrućem psu. U poleđini poljski zapis, to je desno od dvije polovice, spremni za njih udariti nakon izračuna. Sada počinje najteži dio - senf. Već je na kobasicama, dakle već je izračunat kao neparan operator. Postoji mišljenje da bi senf također trebao biti prikazan kao nedefiniran i, stoga, trebao bi biti pomaknut s desne strane kobasice ... Ali možda će to previše stajati ...