Reverzni poljski zapis je bil nekoč osnova sveta računalniškega programerja. Danes ni tako dobro znana. Zato je lahko humoristična ilustracija, ki prikazuje »obrnjeno« poljsko klobaso izven peciva, nekaterim znanim programerjem še vedno nerazumljiva. Ni dobra razlaga za šalo, vendar bo v tem primeru popolnoma upravičena.
Infix Record
Vsi programerji in večina študentov poznajo uporabo operaterjev. Na primer, v izrazu x + dodamo vrednosti spremenljivk x in y, uporabimo dodatek. Manj znano je, da je znak, izposojen iz matematike, imenovan infixnoy notation, v resnici velik problem za stroje. Takšen operator vzame kot vhod dve vrednosti, ki sta zapisani na levo in desno od nje. Pri programiranju je uporaba simbolov z operacijskimi znaki neobvezna. Na primer, x + y lahko zapišemo kot funkcijo kompilacije (x, y), v kateri prevajalnik na koncu spremeni vpisni zapis. Vendar pa vsi poznajo matematiko preveč dobro, da ne uporabljajo aritmetičnih izrazov, ki tvorijo nekakšen notranji mini jezik v skoraj vseh programskih jezikih.
Prevajalci formula
Prvi resnično uspešen programski jezik za Fortran je postal tako v veliki meri, ker so bili aritmetični izrazi (tj. Formule) v njej prevedeni (prevedeni) v kodo, od koder prihaja njeno ime - FORmula TRANslation. Pred tem so morali na primer zapisovativ obliki funkcij sestavljajo (a, pomnožite (b, c)). V Kobolu je bil problem uvajanja avtomatske transformacije formule zelo težaven, saj so morali programerji pisati stvari kot Add A To B. Mutliply By C.
Kaj je narobe z infix?
Težava je v tem, da imajo operaterji takšne lastnosti kot prednost in asociativnost. Zaradi tega postane definicija infix funkcije nekritična naloga. Na primer, prednost množenja je višja od dodajanja ali odštevanja, kar pomeni, da izraz 2 + 3 * 4 ni enak vsoti 2 in 3, pomnožen s 4, kot bi bil, če bi bili operaterji izvedeni od leve proti desni. Pravzaprav morate pomnožiti 3 s 4 in dodati 2. Ta primer ponazarja, da računanje infix izrazov pogosto zahteva spremembo vrstnega reda operaterjev in njihovih operandov. Poleg tega morate uporabiti oklepaje, da bo opomba bolj jasna. Na primer, (2 + 3) * (4 + 5) ni mogoče zapisati brez oklepajev, ker 2 + 3 * 4 + 5 pomeni, da morate pomnožiti 3 s 4 in dodati 2 in 5.
Vrstni red, po katerem je treba izračunati operaterje, zahteva dolgo zapomnitev. Zaradi tega šolarji, začetniki učijo aritmetiko, pogosto dobijo napačne rezultate, tudi če so dejanske operacije opravljene pravilno. Postopek operaterjev se mora naučiti na pamet. Najprej je treba izvesti dejanja v oklepajih, nato množenje in deljenje ter končno dodajanje in odštevanje. Vendar obstajajo tudi drugi načini za pisanje matematičnih izrazov, saj je zapis v zapisnik samo eden od možnih "majhnih jezikov", ki se lahko dodajo večjemu.
Predpona in postfix
Dve od najbolj znanih alternativnih variant je zapis operaterja pred ali po operandih. Znane so kot predpone in postfix. Logika Jan Lukasiewicz je v dvajsetih letih ustvarila prvo od njih. Živel je na Poljskem, tako da se zapis imenuje poljski. Postfix različica je prejela ime obratnega poljskega zapisa (OPN). Edina razlika med tema dvema metodama je v smeri, v kateri bi morali brati zapis (od leve proti desni ali od desne proti levi), zato samo eno zelo podrobno. V OPN je operator zapisan po svojih operandih. Izraz AB + je torej primer obrnjenega poljskega vnosa za A + B.
Neomejeno število operandov
Neposredna prednost zapisa je, da je posplošena z n-adičnim operaterjem, infixni zapis pa dejansko deluje samo z dvema operandoma, ki je po naravi primerna le za binarne operacije. Na primer, ABC @ je povratni poljski izraz, ki uporablja triadni znak, ki najde največjo vrednost A, B in C. V tem primeru upravljavec deluje na 3 operande levo od sebe in ustreza klicu funkcije @ (A, B, C). Če poskusite napisati znak "@" kot infix, kot je A @ BC ali kaj podobnega, potem postane jasno, da samo ne deluje.
Prednost ima naročilo
Reverzni poljski zapis ima še eno prednost, da je prednost operaterjev lahko predstavljena z vrstnim redom njihovega nastanka. V tem primeru oklepaji ne bodo nikoli potrebni, čeprav jih je mogoče vključiti kot znake lažjega delovanjapretvorbo z vpisno zaporedje. Na primer, AB + C * je edinstven ekvivalent (A + B) * C, ker se množenje ne more izračunati, dokler se ne izvede dodatek drugega operanda za operacijo množenja. To pomeni, da, če AB + C * izračuna en operater naenkrat, potem A B + C * - & gt; (A B +) * C - & gt; (A + B) * C.
Algoritem izračuna
V OPC operater izgleda enako kot funkcija, ki sprejema kot dva argumenta vrednosti, zapisane levo od nje. Poleg tega je to naravni zapis za uporabo v programskih jezikih, saj potek njenih izračunov ustreza operacijam skladov in potreba po razčlenjevanju ne obstaja. Na primer, v OPC-ju bo izraz 5 + 6 * 7 izgledal kot 567 *, + in ga je mogoče izračunati preprosto s skeniranjem od leve proti desni in zapisovanjem vrednosti v sklad. Vsakič, ko je najdena transakcija, sta izbrana dva zgornja elementa pomnilnika stroja, uporabljen je operater in rezultat se vrne v pomnilnik. Ko dosežete konec izraza, se bo rezultat izračunov pojavil na vrhu kupa. Na primer:
S = () 567 *, + postavi 5 v sklad. S =
6 7 *, + postavi 6 v sklad. S = (5 6) 7 *, + postavi 7 v sklad. S = (567) *, + izbere 2 vrednosti iz sklada, uporabi * in postavi rezultat v sklad. S = (5 6 * 7) = (542) + izbira 2 vrednosti iz sklada, uporabi + in postavi rezultat na sklad. S = (5 + 42) = (47) Izračun je končan, rezultat je na vrhu kupa.Ta povratni algoritem poliranja lahko preverite večkrat, vendar vsakič, ko bo deloval, ne glede na to, kolikoaritmetični izraz je kompleksen. OPN-ji in skladi so tesno povezani. Spodnji primer prikazuje, kako je mogoče uporabiti pomnilnik za izračun vrednosti obrnjenega poljskega zapisa. Manj očitno je, da lahko uporabite sklad, preoblikovanje standardnih infix izrazov v TNF.
Primeri programskih jezikov
V jeziku Pascal je povratni poljski zapis izveden približno (prikazan del programa). Branje številk in operatorjev v zanki se imenuje postopek, ki določa, ali je žeton številka ali znak operacije. V prvem primeru se vrednost zapiše v sklad, v drugem pa nad dve zgornji številki sklada, opravi se ustrezno dejanje in rezultat se shrani. toktype: = num; (c); če v ['+', '-', '*', '/'], potem začnete, če eoln potem cn: = 'drugje (cn); če cn = '', potem primer iz '+': toktype: = add; '-': toktype: = sub; "*": toktype: = me; '/': toktype: = konec drugega dela se začne, če je c = '-' potem sgn: = -1 še napaka: = s & lt; & gt; „+“; c: končni konec cn; if (ne napaka) in (toktype = num) potem dobite številko; če je tipka & lt; & gt; num then begin: = ro; x: = ro; če ni nobene napake v tem primeru, toktype add: z: = x + y; sub: z: = x-y; me: z: = x * y; div: z: = x /y končno potiskanje (z); C-realizacija nasprotnega poljskega zapisa (podan je del programa): za (s = strtok (s, w); s; s = strtok (0 w)) {a = strtod (s & e); če (e> s) pritisnite (a); #define rpnop (x) printf ("% c:", * s); b = (pop); ); sicer če (* s == '-') rpnop (a - b); tudi če (* s == '*') rpnop (a * b); tudi če (* s == '/') rpnop (a /b); #undef rpnop}
Realizacija strojne opreme
V času, ko je bila računalniška tehnologija zelo draga, se je zdelo dobro, če bi ljudi prisilili k uporabi OPN. V šestdesetih letih prejšnjega stoletja, kot tudi danes, je bilo mogoče kupiti kalkulatorje, ki delujejo na nasprotni straniPoljski zapis. Za dodajanje 2 in 3 morata vnesti 2, nato 3 in klikniti na gumb plus. Na prvi pogled se je uvajanje operandov operaterju zdelo težko in težko zapomniti, toda po določenem času so bili nekateri odvisni od tega načina razmišljanja in niso mogli razumeti, zakaj drugi vztrajajo pri neumnem zapisu, ki je tako kompleksen in tako omejen. Burroughs je zgradil tudi mainframe, ki ni imel nobenega drugega RAM-a razen stack. Edina stvar, ki jo je naredil avto - uporabil je algoritme in metode povratnega poljskega pisanja v centralni sklad. Vse njene operacije so veljale za operaterje OPN, katerih dejavnosti so se razširile na n zgornjih vrednosti. Na primer, ukaz Return je vzel naslov z vrha skladov itd. Arhitektura takega računalnika je bila preprosta, vendar ne dovolj hitra, da bi lahko tekmovala z bolj splošnimi arhitekturami. Mnogi pa še vedno obžalujejo, da tako preprost in eleganten pristop k računalništvu, kjer je bil vsak program izraz NPN, ni našel svojega nadaljevanja. Enkrat so kalkulatorji z obrnjenim poljskim zapisom uživali popularnost, nekateri pa jim še vedno dajejo prednost. Poleg tega so bili razviti stack-oriented jeziki, kot je Forth. Danes se malo uporablja, vendar še vedno povzroča nostalgijo pri nekdanjih uporabnikih.
Torej, kaj je smisel šaliti o obratni poljski klobasi?
Če upoštevamo operaterja za klobase, potem v notnem zapisu, mora biti v hlebu, kot pri običajnih hot dogih. V nasprotnem poljskem zapisu je na desni stranidve polovici, je pripravljen, da se po izračunu prenaša med njimi. Zdaj se začne najtežji del - gorčica. Že je na klobasi, ki je že izračunana kot unarni operater. Menijo, da bi bilo treba gorčico prikazati tudi kot neobdelano in jo je zato treba premakniti na desno stran klobase, toda morda to zahteva preveč kupa.
