Povratni poljski zapis: algoritem, metode in primeri

Povratni poljski zapis je bil nekoč osnova za svet računalniškega programerja. Danes ni tako dobro znano. Zato so nekateri dobro poznani programerji še vedno napačno razumeli komično ilustracijo, ki prikazuje "obratno" poljsko klobasico izven bunga. Ni šanljivo razložiti šale, vendar bo v tem primeru popolnoma upravičeno.

Infix vnos

Vsi programerji in večina študentov poznajo uporabo operaterjev. Na primer, v izrazu x + y se znak za dodajanje uporablja za seštevanje vrednosti spremenljivk x in y. Manj znano je, da je to izposojeno iz matematične oznake, imenovanega infix notacija, dejansko velik problem za stroje. Takšni operater sprejme kot vhod dve vrednosti, zapisanih v levo in desno od nje. Pri programiranju je oznaka z znaki delovanja neobvezna. Na primer, x + y lahko zapišemo kot funkcijo za dodajanje (x, y), na katerega prevajalnik končno pretvori infiksno notacijo. Vendar vsi dobro poznajo matematiko, da ne uporabljajo aritmetičnih izrazov, ki v skoraj vsakem programskem jeziku tvorijo neke vrste notranji mini-jezik.

Prevajalci formul

Prvi res uspešna Fortran programski jezik je postal tako v veliki meri zato, ker je aritmetično izraz (to je formula, ..) se pretvori (oddaja) v kodo, od tod tudi ime za to - Formula prevod. Pred tem so jih morali na primer zapisati v obliki funkcij, ki jih je treba dodati (a, pomnoži (b, c)). V Kobolu se je problem izvajanja avtomatske pretvorbe formule štel za zelo težko, saj so morali programerji pisati stvari, kot je dodajanje A v B Mutliply C.

Kaj je narobe z infixom?

Težava je v tem, da imajo operaterji lastnosti, kot sta prednost in asociativnost. Zaradi tega opredelitev funkcije infixa postane netrivialna naloga. Na primer, množenje ima večjo prednost kot dodajanjem ali odvzemanjem, kar pomeni, da je z izrazom 2 + 3 * 4 ni enak vsoti 2 in 3, pomnoženo s 4, kot bi bilo pri opravljanju operaterjev od leve proti desni. Dejansko pomnožite 3 do 4 in dodajte 2. Ta primer ponazarja, da vrednotenje izraza infix pogosto zahteva spremembo vrstnega reda operaterjev in njihovih operandov. Poleg tega moramo uporabiti oklepaje, da bo oznaka 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 z 4 in dodati 2 in 5.

Vrstni red, v katerem je potrebno izračunati operaterje, zahteva dolgotrajno zaprtje. Zaradi tega učenci, ki se začnejo učiti aritmetično, pogosto dobijo napačne rezultate, tudi če se dejansko izvajajo operacije pravilno. Treba se je naučiti reda delovanja operaterjev na srce. Najprej je treba izvesti ukrepe v oklepajih, nato razmnoževanje in delitev ter nazadnje dodajanje in odštevanje. Toda obstajajo drugi načini pisanja matematičnih izrazov, saj je infiksna notacija samo eden od možnih "majhnih jezikov", ki jih je mogoče dodati večjemu.

Predpona in postfiksna notacija

Najbolj priljubljena alternativa sta snemanje operaterja pred operandi ali pozneje. Znani so kot predpono in postfix notacije. Logician Jan Lukasevich je izumil prvega izmed njih v 1920. letih. Živel je na Poljskem, tako da se glasba imenuje poljščina. Različica Postfixa je bila imenovana obratna poljska notacija (ARF). Edina razlika med dvema metodama je smer branja zapisa (od leve proti desni ali od desne proti levi), zato je dovolj, da razmislimo le o enem od njih. V odvodniku je operater napisan po svojih operandih. Tako je izraz AB + primer povratnega poljskega zapisa za A + B.

Neomejeno število operandov

Neposredna prednost zapisa je, da povzema n-adske operaterja in Vplivajo zapis je le res deluje z dvema operandov, t. E. so same po sebi primeren samo za binarne operacije. Na primer, ABC @ je obratno poljščina izraz uporablja triadni oznako, ki je največja vrednost A, B in C. V tem primeru operater deluje na levi treh operanda samega in ustreza funkciji klica @ (A, B, C). Če skušate napisati simbol @ kot infix, na primer A @ BC ali kaj podobnega, potem postane jasno, da to preprosto ne deluje.

Prednost je naloga

Druga prednost ima povratni polski vstop, saj lahko prednost pred operaterji predstavljajo vrstni red njihovega videza. V tem primeru se oklepaji nikoli ne bodo potrebovali, čeprav jih je mogoče vključiti kot simbole transakcije, da bi olajšali konverzijo z infiksno oznako. Na primer, AB + C * - nedvoumna ekvivalent (A + B) * C, tako da množenje ni mogoče izračunati do dodatek izvedemo, ki daje drugi operand razmnoževanju. To pomeni, da je AB + C * izračunan za en operater hkrati, potem dobimo A B + C * -> (A B +) * C -> (A + B) * C.

Algoritem za izračun

V operacijskem sistemu OPN operater izgleda kot funkcija, ki kot argument vsebuje dve vrednosti, zapisanih na levi strani. Poleg tega je to naravni zapis za uporabo v programskih jezikih, saj potek njegovih izračunov ustreza operacijam skladov in ni potrebe po razčlenjevanju. Na primer, v ARS bo izraz 5 + 6 * 7 izgledal kot 5, 6, 7 *, + in ga je mogoče izračunati samo s skeniranjem od leve proti desni in zapisovanjem vrednosti v sklad. Vsakič, ko naletite na operacijski znak, se izberejo najvišja dva elementa iz pomnilnika naprave, operater se uporabi in rezultat se vrne v pomnilnik. Ko je dosežen konec izraza, bo rezultat izračuna na vrhu zloženke.

Na primer:

• S = () 5, 6, 7, *, + postavite 5 v sklad.
• S = (5) 6, 7, *, + postavite 6 v sklad.
• S = (5, 6) 7, *, + postavite 7 na sklad.
• S = (5, 6, 7) *, + izberite 2 vrednosti iz svežnja, uporabite * in dajte rezultat v sklad.
• S = (5, 6 * 7) = (5, 42) + izberite 2 vrednosti iz svežnja, uporabite + in dajte rezultat v sklad.
• S = (5 + 42) = (47) je izračun končan, rezultat je na vrhu drevesa.

Ta algoritem reverznega poljskega zapisa je mogoče večkrat preverjati, vendar vsakič, ko bo deloval, ne glede na to, kako kompleksen je aritmetični izraz.

Odvodniki in skladi so tesno povezani. Zgornji primer prikazuje, kako se lahko pomnilnik uporabi za izračun vrednosti v inverzni poljski notaciji. Manj je očitno, da lahko uporabite sklad tako, da pretvorite standardne infixne izraze v odvodnik.

Primeri v programskih jezikih

V jeziku Pascal se reverzni poljski zapis izvaja približno takole (del programa je podan).

Za branje številk in operaterjev v zanki se kliče postopek, ki določa, ali je žeton številka ali operacijski znak. V prvem primeru je vrednost zapisana v snop, medtem ko se v drugem primeru ustrezno dejanje izvaja v zgornjih dveh številkah sklada in rezultat se shrani.

toktype: = število;

beri (c);

če se v [`+`, `-`, `*`, `/`] začne

če je eolina potem cn: = `` drugje bere (cn);

če je cn = `, potem

primer s

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

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

konec

drugače se začne

če je c = `-` potem sgn: = -1 še napaka: = s <> `+`;

z: = cn

konec

konec;

če (ne gre za napako) in (toktype = num) potem dobite številko;

če tok <> num se nato začne

y: = roorx: = rop;

če ne napako potem

case toktype of

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

konec

push (z);

C-izvajanje reverznega poljskega zapisa (del programa je podan):

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

a = strtod (s, e);

če (e> s) pritisni (a);

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

drugače, če (* s == `+`) rpnop (a + b);

drugače, če (* s == `-`) rpnop (a-b);

drugače, če (* s == `*`) rpnop (a * b);

drugače, če (* s == `/`) rpnop (a / b);

#undef rpnop

}

Izvedbe strojne opreme

V tistih dneh, ko je bila računalniška tehnologija zelo draga, se je zdela dobra ideja, da bi ljudi prisilili k uporabi OPN-ja. V šestdesetih letih, kot je bilo danes, je bilo mogoče kupiti kalkulatorje, ki delujejo v obratnem poljskem snemanju. Če želite dodati 2 in 3, vnesite 2, nato 3 in pritisnite gumb plus. Na prvi pogled se vhodni operandi do operaterja zdelo zapleteno in težko zapomniti, ampak čez nekaj časa so nekateri zasvojeni s tem načinom razmišljanja in ni mogel razumeti, zakaj drugi vztrajajo pri neumno Vplivajo, ki je tako zapleten, zato je omejena.

Burroughs je celo zgradil mainframe, ki ni imel nobene druge RAM, razen sklada. Edina stvar, ki jo je naredil stroj, je bil uporabiti algoritme in metode za preusmeritev poljskega zapisa v osrednji sklad. Vse operacije so bile obravnavane kot operaterji OPN, katerih delovanje se je razširilo na n zgornje vrednosti. Na primer, ukaz Return je vzel naslov z vrha svežnja itd. Arhitektura tega stroja je bila preprosta, vendar ne dovolj hitro, da bi lahko tekmovala z bolj splošnimi arhitekturami. Mnogi pa še vedno obžalujejo, da tak preprost in eleganten pristop k računanju, kjer je bil vsak program izraz OPN, ni našel nadaljevanja.

Nekoliko so bili kalkulatorji s povratnim poljskim snemanjem priljubljeni, nekateri pa so še vedno raje. Poleg tega so bili razviti stojno usmerjeni jeziki, kot je Forth. Danes se to malo uporablja, vendar še vedno povzroča nostalgijo s strani nekdanjih uporabnikov.

Torej, v čem je šala za vračanje poljske klobase?

Če menite, da je operater klobase, potem v infix zapisu, mora biti znotraj roll, kot v normalnem hot dog. V nasprotnem poljskem zapisu je desno od obeh polovic, pripravljenih na udarce med njimi po izračunu. Zdaj se začne najtežji del - gorčica. To je že na klobasah, torej je že izračunano kot unikatni operater. Obstaja mnenje, da je gorčica prav tako treba prikazati kot nedoločeno in zato jo je treba premakniti na desno od klobase ... Ampak morda bo potrebno preveliko količino ...