Fordított lengyel jelölés
Fordított lengyel jelölésről, ismertebb nevén RPN-ről (a Reverse Polish Notation kezdőbetűiből), vagy másképpen postfix jelölésről akkor beszélhetünk, ha egy aritmetikai műveletben az operátor az operandusok után áll. A fordított lengyel jelölésben a műveleti jelek olyan sorrendben szerepelnek, amilyen sorrendben azok végrehajtódnak a kifejezés kiértékelésekor.
Története
[szerkesztés]Az eredeti prefix jelölési forma a lengyel logika tudósa, Jan Łukasiewicz után kapta a nevét, aki 1920-ban kimutatta ennek a módszernek az előnyeit. A tudós származása után módszerét lengyel jelölésnek (Polish notation) kezdték el nevezni.[1] Munkásságát később, az 1954-es évben Burks, Warren, és Wright,[2] továbbá tőlük függetlenül F. L. Bauer és E. W. Dijkstra az 1960-as évek elején felhasználta a korabeli számítógépek memóriafelhasználásának csökkentésére. Ekkoriban kezdtek vermet (stack) használni a kifejezések kiértékelésére. A lengyel jelöléssel szemben a fordított lengyel jelölést az ausztrál filozófus, és számítógéptudós Charles Leonard Hamblin[3] vezette be. Eredményeit (elismerve Jan Łukasiewicz munkásságát) fordított lengyel jelölésként ismertette az 1950-es évek közepén. Hamblin kutatásai a következő problémákra irányultak:
- zárójeleket tartalmazó matematikai formulák gépi kiértékelése és
- a memória túlterhelődésének megakadályozása a műveletek végzése közben.
Az első problémára jó megoldást adott a Jan Łukasiewicz-féle lengyel jelölés (Polish notation), amely a matematikai műveleteket zárójel nélkül írta le. Például az összeadást a Łukasiewicz-féle lengyel jelölés így írta le: Hamblin a formális logika tanulmányozása során ismerte meg és használta fel Łukasiewicz munkásságát, majd annak alapján dolgozta ki a postfix jelölést, amely az módon ábrázolja az és összeadását. A látszólag aprócska változtatásnak óriási jelentősége volt a számítógépek működése szempontjából.[4]
Előnyei
[szerkesztés]A fordított lengyel jelölésnek számos előnye van a mindennapi életben megszokott infix jelöléssel szemben algebrai kifejezések esetén.
- Minden formula, képlet leírható zárójel nélkül.
- A leírt formulák a leírás sorrendjében értékelődnek ki.
- Kényelmesen kiértékelhetők a formulák számítógéppel verem használatával.
- Az infix operátorokra elsőbbségi szabály, más néven precedencia vonatkozik, amely tetszőleges és nem kívánatos. Például, tudjuk, hogy az jelentése és nem , mivel a szorzás nagyobb prioritású művelet, mint az összeadás.
- A számítástechnikában használt műveletek esetén bizonyos esetekben nem állapítható meg prioritás teljesen különböző műveletek között sem. Például a balra léptetés (SHL), valamint a logikai ÉS művelet között nem tudunk ilyen egyértelmű sorrendet felállítani.
A fordított lengyel jelölés kiküszöböli az összes felsorolt kellemetlenséget.
Jelölési példák
[szerkesztés]| Infix | Fordított lengyel jelölés |
|---|---|
| A + B * C | A B C * + |
| A * B + C | A B * C + |
| A * B + C * D | A B * C D * + |
| (A + B) / (C - D) | A B + C D - / |
| ((A + B) * C + D) / (E + F + G) | A B + C * D + E F + G + / |
Formulák kiértékelése
[szerkesztés]Egy postfix (RPN) kifejezés kiértékelése során a következő pszeudokód hajtódik végre:
- A bemeneti adatok mutatója eggyel balra mutat (a következő beolvasandó elemre)
- A következő adat (token) beolvasása.
- Ha beolvasott token szám:
- A verem tetejére tesszük.
- Egyébként a token egy műveleti utasítás (esetünkben lehet műveleti jel vagy függvény).
- Ha ismert a műveleti utasítás, akkor ismert a szükséges paramétereinek száma is.
- Ha túl kevés az elemek száma, akkor
- Hibajelzés: kevés operandus.
- Egyébként a verem szükséges elemeit a műveleti verembe teszi.
- Végrehajtja a műveletet.
- Ha van eredmény a verem tetejére teszi.
- Ha csak egy elem van a veremben, akkor az végeredmény.
- A számítás végeredménye..
- Egyébként, ha több elem van a veremben:
- Hiba: túl sok adat.
Példa
[szerkesztés]"5 + ((1 + 2) * 4) − 3" RPN-re átírva: 5 1 2 + 4 * + 3 -
A kifejezés balról jobbra értékelődik ki a felírás sorrendjében:
| Input | Művelet | Verem | Megjegyzés |
|---|---|---|---|
| 5 | PUSH | 5 | |
| 1 | PUSH | 1 5 |
|
| 2 | PUSH | 2 1 5 |
|
| + | ADD | 3 5 |
|
| 4 | PUSH | 4 3 5 |
|
| * | MUL | 12 5 |
(12) |
| + | ADD | 17 | (17) |
| 3 | PUSH | 3 17 |
|
| − | SUB | 14 | (14) |
| Eredmény | (14) |
A számítás elvégzése után csak egyetlen elem marad a veremben; esetünkben 14.
Az RPN jelölésmód számítógépeken való alkalmazásának hallatlan előnye a példa követése esetén is belátható:
- a műveletek végzése közben már nem kell sorrendi (precedencia) vizsgálatokat végezni (és a mindenkori műveleti sorrendnek megfelelően átrendezni az adatokat);
- egy adott művelet (például összeadás, kivonás) elvégzése során nem kell a műveleti jelet tologatni a veremben, helyes adatbevitel esetén a művelet automatikusan a helyére kerül;
- a vermet egyszerre csak nagyon kevés adat használja, függetlenül a képlet hosszától (ennek a korabeli 64-128 bájtos(!) zsebszámológépek esetén volt óriási jelentősége);
- megfelelő formára hozott képletek gyorsan, egyszerű lépésekkel feldolgozhatóak;
- átmeneti adatok csak ritkán keletkeznek;
Konverzió
[szerkesztés]Edsger Dijkstra konverziós megoldása – melynek során a hagyományos infix matematikai jelölést számítógéppel RPN jelöléssé alakítják – shunting-yard algoritmus néven vált ismertté, amelyre számos számítógépes implementáció[5] is született.
Gyakorlati megvalósítások
[szerkesztés]
RPN logikával az 1970-es évek végétől lehetett találkozni a Hewlett-Packard tudományos célú zsebszámológépeiben, mint például a HP-10, vagy a HP-29, vagy a lényegesen újabb HP-48C.
Nemcsak az egykori zsebszámológépek, hanem számítógépes programok és programnyelvek is kihasználják a jelölés erősségét. Így például napjainkban a Forth, PostScript programozási nyelvek fordított lengyel jelölést (RPN) használnak. Szoftverek közül az ismert Ghostscript, AutoCAD alatt az ATLAST[6] vagy Unix alatt a dc kalkulátor. Számos szoftveres emulátor létezik például HP számológépekre Android operációs rendszerekre is.
Jegyzetek
[szerkesztés]- ↑ nehezen kiejthető neve miatt
- ↑ An Analysis of a Logical Machine Using Parenthesis-Free Notation
- ↑ Math Forum - Ask Dr. Math
- ↑ Az ötletadó Łukasiewicz-féle lengyel jelölés sem tűnt el: például a LISP-nyelvek napjainkban is használják.
- ↑ Parsing/Shunting yard algorithm
- ↑ John Walker: ATLAST Autodesk Threaded Language Application System Toolkit
További információk
[szerkesztés]- RPN- lap.hu
- Lukasiewicz életrajza
- Reverse Polish Notation (RPN
- Charles Leonard Hamblin
- Parsing/RPN to infix conversion
- Infix to Postfix Online Convertor
- convert infix to Rpn (shunting yard)
- Parsing/Shunting yard algorithm
- The Museum of HP Calculators
- RpnCalc
- Rpn calculator hp Android Apps
Fordítás
[szerkesztés]- Ez a szócikk részben vagy egészben a Reverse Polish notation című angol Wikipédia-szócikk fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.
