Obrnjeni poljski zapis
Obŕnjeni póljski zapís (tudi pripónski ~ ali póstfiksni ~; pogosta je tudi angleška tričrkovna kratica RPN) je zapis aritmetičnih izrazov, izpeljan iz poljskega zapisa, ki ga je leta 1920 predlagal poljski filozof in matematik Jan Łukasiewicz.
Način obrnjenega poljskega zapisa sta predlagala Friedrich Bauer in Edsger Dijkstra v zgodnjih 1960-ih zaradi zmanjšanja pomnilniškega prostora in izkoriščanje sklada pri računanju izrazov. Zapis in algoritme je sredi 1960. let razvil avstralski filozof in računalnikar Charles Hamblin, saj je omogočal breznaslovni pomnilnik.[1][2]
Kot uporabniški vmesnik za izračune in zapis je bil prvič uporabljen pri namiznih računalih Hewlett-Packard v poznih 1960., zatem pa v ročnem računalu HP-35, ki je prišel na trg leta 1972. V obrnjenem poljskem zapisu operator sledi operandom, s čimer je odpravljena potreba po oklepajih. Izraz »3 · (4 + 7)« tako zapišemo kot »3 4 7 + ·«, kar na računalih z obrnjenim poljskim zapisom opravimo z zaporedjem tipk »3«, »Enter«, »4«, »Enter«, »7«, »Enter«, »+«, »*« (nekaj tipkanja si prihranimo s prepisom v enakovreden zapis »4 7 + 3 ·«, ki mu ustreza zaporedje tipk »4«, »Enter«, »7«, »+«, »3«, »*«).
Izvedbe obrnjenega poljskega zapisa temeljijo na skladu – operandi so vzeti s sklada, rezultat izračuna pa je vrnjen na sklad. Čeprav se zdi načelo sprva obskurno, pa ima obrnjeni poljski zapis prednost, da ga računalnik zelo preprosto in zategadelj hitro razčleni.
Praktične posledice
[uredi | uredi kodo]- Izračuni si sledijo od leve proti desni.
- Aritmetični izrazi ne vsebujejo oklepajev, saj ti niso potrebni.
- Operator sledi operandom. Ti so odstranjeni s sklada, ko je izraz ovrednoten.
- Po izvedeni operaciji postane rezultat sam operand za naslednje operacije.
- Ni skritega stanja – ni vprašanje, ali ste zadeli operator ali ne.
Zgled
[uredi | uredi kodo]Izračun: »((1 + 2) * 4) + 3« lahko zapišemo v obrnjenem poljskem zapisu kot
1 2 + 4 * 3 +
Izraz se ovrednoti na naslednji način (stolpec »sklad« pomeni stanje po opravljeni »operaciji«):
| vhod | sklad | operacija |
|---|---|---|
| 1 | 1 | Dodaj operand na sklad |
| 2 | 1, 2 | Dodaj operand na sklad |
| + | 3 | Seštevanje |
| 4 | 3, 4 | Dodaj operand na sklad |
| * | 12 | Množenje |
| 3 | 12, 3 | Dodaj operand na sklad |
| + | 15 | Seštevanje |
Končni rezultat, 15, leži po opravljenem izračunu na vrhu sklada.
Sklici
[uredi | uredi kodo]- ↑ Peter McBurney, Charles L. Hamblin and his work Arhivirano 2008-12-06 na Wayback Machine.
- ↑ Peter McBurney (27. julij 2008), Charles L. Hamblin: Computer Pioneer Arhivirano 2003-12-24 na Wayback Machine.. "»Hamblinu sta kmalu postala jasna problema (a) računanja matematičnih formul, ki vsebujejo oklepaje, in (b) velik pomnilnik pri hranjenju. Ena rešitev prvega problema je bil poljski zapis Jana Lukasiewicza, ki je omogočal piscu matematičnega zapisa da je napotil bralca na vrstni red v katerem se naj izvedejo operacije (na primer seštevanje, množenje itd) brez rabe oklepajev. Poljski zapis to doseže tako da so operatorji (+, * itd) napisani pred operandi na katere delujejo; na primer +ab, namesto običajnega zapisa a+b. Hamblin je poznal formalno logiko in Lukasiewiczevo delo.«