Prefiksna notacija
|
| Prefiksna notacija |
| Infiksna notacija |
| Postfiksna notacija |
Prefiksna notacija ili prefiksni sustav oznaka je oblik notacije u logici, aritmetici i algebri. Njena istaknuta osobina jest ta da su operatori postavljeni lijevo od operanada. Ako je mjesnost operatora čvrsta (tj. fiksirana), kao rezultat se dobiva sintaksa bez ikakvih zagrada a koja i dalje može biti parsirana bez ikakve nejednoznačnosti. Poljski je logičar Jan Lukasiewicz izmislio ovu notaciju oko 1920. kako bi pojednostavnio sustav oznaka propozicijskog računa. Ponekad se ova notacija naziva i poljska notacija, kako bi se naglasila njegova nacionalnost.
Iako se više ne koristi toliko učestalo u logici, našla je uporabu u računarstvu.
Izraz za zbrajanje brojeva jedan i dva je u prefiksnoj notaciji zapisan kao "+ 1 2", mjesto kao "1 + 2". U složenijim izrazima, operatori još uvijek prethode operande, ali i sami operandi mogu biti netrivijalni izrazi koji uključuju svoje operatore. Na primjer, izraz koji bi bio zapisan kao
- 5 - (6 + 7)
u konvencionalnoj infiksnoj notaciji, bi bio zapisan kao
- - 5 (+ 6 7)
ili jednostavno
- - 5 + 6 7
u prefiksnoj notaciji
S obzirom na to da su jednostavni aritmetički operatori svi binarne funkcije (barem binarne, u aritmetičkim kontekstima), njihove prefiksne reprezentacije su stoga nejednoznačne, pa je zagrađivanje prefiksnih izraza stoga nepotrebno. U prethodnom su primjeru zagrade u infiksnoj verziji bile obavezne, pošto bi njihovo odstranjivanje
- (5 - 6) + 7
ili jednostavno premještanje
- 5 - 6 + 7
promijenilo značenje i rezultat cijelog izraza. S druge strane, odgovarajuća prefiksna verzija ovog drugog izračuna bi bila zapisana kao
- + - 5 6 7
Obrađivanje zbrajanja se odgađa sve dok oba operanda operacije oduzimanja nisu pročitana. Kao i s bilo kojom notacijom, krajnji unutarnji izrazi su prvi evaluirani (vrednovani), s tim da u prefiksnoj notaciji se ovaj "krajnji unutarnji" kriterij može ostvariti redoslijedom čitanja mjesto zagrađivanjem.
Prefiksna notacija jednostavne aritmetike je uglavnom od čisto akademskog interesa. Za razliku od slične postfiksne notacije (poznate i kao RPN), prefiksna je notacija korištena tek u ponekom, ako i bilo kojem, komercijalnom kalkulatoru. S druge strane, prefiksna aritmetika se često koristi u prvom, konceptualnom koraku podučavanja računalnih programskih jezika koji koriste prefiksnu notaciju.
Prefiksna notacija ima široku primjenu u Lispovim S-izrazima, gdje su zagrade potrebne zbog aritmetičkih operatora promjenjive mjesnosti (ariteta). Srodna postfiksna notacija (ili "obrnuta poljska notacija") se često koristi u stogovno orijentiranim programskim jezicima, te predstavlja načelo djelovanja određenih kalkulatora, posebice onih od tvrtke Hewlett-Packard.
Iako se čini naizgled očitim, važno je naglasiti da broj operanada u izrazu mora biti jednak broju operatora plus jedan, inače naredba nema smisla (pretpostavljajući samo da su binarne operacije korištene u izrazu). Ovo se lako može previdjeti prilikom baratanja s dužim, složenijim izrazima s po nekoliko operatora, te stoga valja pripaziti da izraz ima smisla prilikom korištenja prefiksne notacije.
Redoslijed operacija je definiran strukturom prefiksne notacije i može lako biti odlučen. Jedna stvar koju treba imati na umu jest da je, prilikom izvršavanja operacije, operacija primjena NA prvi operand OD STRANE drugog operanda. Ovo ne čini problem kod operacija koje komutiraju, ali za nekomutirajuće operacije poput dijeljenja ili oduzimanja je ova činjenica od krucijalne važnosti prilikom raščlambe izraza. Na primjer, sljedeći izraz:
/ 10 5
se čita kao "Dijeli 10 sa 5". Stoga je rezultat 2, ne ½ kao što bi već dala netočna raščlamba.
Prefiksna je notacija osobito popularna kod stogovno baziranih operacija zbog svoje urođene sposobnosti da lako razlikuje redoslijed operacija bez potrebe za zagradama. Da bi se evaluirao redoslijed operacija u prefiksnoj notaciji, nije ni potrebno zapamtiti hijerarhiju prednosti operatora, kao što je već potrebno s infiksom notacijom. Umjesto toga, izravno se gleda u zapis da bi se otkrio operator koji se prvi evaluira. Čitanjem izraza slijeva na desno, prvo se traži operator te potom dva operanda. Ako se naiđe na drugi operator prije nego što su operandi pronađeni, stari se operator stavi sa strane sve dok se ne razriješi ovaj novi operator. Ovaj proces se iterira sve dok svaki operator nije razriješen, što se pak mora sigurno jednom dogoditi, pošto treba biti jedan više operand nego što je operatora u izrazu. Jednom razriješen, operator i dva operanda su zamijenjena s novim operandom. Budući da su jedan operator i dva operanda odbačena i jedan operand dodan, ukupan gubitak se sastoji od jednog operatora i jednog operanda, što znači da je još uvijek jedan više operand nego operator baš kao i prije zamjene, što dopušta završavanje iterativnog procesa. Ovo je općenit teoretski model iza korištenja stogova u programskim jezicima za evaluiranje izraza u prefiksnoj notaciji, iako postoje raznorazni algoritmi koji manipuliraju takvim procesom. Jednom raščlanjen, izraz u prefiksnoj notaciji postaje znatno manje zastrašujućeg izgleda. Sljedeći primjer pokazuje lakoću s kojom složen izraz u prefiksnoj notaciji može biti raščlanjen kroz redoslijed operacija:
- * / 15 - 7 + 1 1 3 + 2 + 1 1 = - * / 15 - 7 2 3 + 2 + 1 1 = - * / 15 5 3 + 2 + 1 1 = - * 3 3 + 2 + 1 1 = - 9 + 2 + 1 1 = - 9 + 2 2 = - 9 4 = 5
Donja tablica prikazuje suštinu notacije Jana Lukasiewicza za propozicijsku logiku. "Dogovorna" (konvencionalna) notacija nija bila toliko dogovorna sve do 70-ih i 80-ih godina 20. stoljeća.
| Koncept | Dogovorna notacija |
Poljska notacija |
|---|---|---|
| Negacija | ¬φ | Nφ |
| Konjunkcija | φ∧ψ | Kφψ |
| Disjunkcija | φ∨ψ | Aφψ |
| Materijalna pogodba | φ→ψ | Cφψ |
| Dvopogodba | φ↔ψ | Eφψ |
| Shefferov operator | Dφψ | |
| Mogućnost | ♢φ | Mφ |
| Nužnost | ☐φ | Lφ |
| Univerzalni kvantifikator | ∀φ | Πφ |
| Egzistencijalni kvantifikator | ∃φ | Σφ |
Valja uočiti da su kvantifikatori djelovali nad propozicijskim vrijednostima u Lukasiewiczom radu na viševrijednosnim logikama.
- Postfiksna notacija ili obrnuta poljska notacija
Jan Lukasiewicz, "Philosophische Bemerkungen zu mehrwertigen Systemen des Aussagenkalküls", Comptes rendus des séances de la Société des Sciences et des Lettres de Varsovie 23:51-77 (1930). Prevedeno od strane H. Webera kao "Philosophical Remarks on Many-Valued Systems of Propositional Logics", u Storrs McCall, Polish Logic 1920-1939, Clardendon Press: Oxford (1967).