A | B | C | D | E | F | G | H | CH | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
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
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
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
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
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
"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ó
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
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
- ↑ 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
- 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
- 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.
A lap szövege Creative Commons Nevezd meg! – Így add tovább! 3.0 licenc alatt van; egyes esetekben más módon is felhasználható. Részletekért lásd a felhasználási feltételeket.
Analóg multiméterek túlterhelés elleni védelme
Egyenáram
Egyenáram mérése
Egyenirányítós lengőtekercses műszer
Elektromágnes (fizika)
Elektromos feszültség
Elektromos térerősség
Fáziseltolódás
Fázismutató
Fajlagos ellenállás
Feszültséggenerátor
Feszültségváltó
Forgó mágneses tér
Háromfázisú hálózat
Hőelektromosság
Hatásos ellenállás
A lap szövege Creative Commons Nevezd meg! – Így add tovább! 3.0 licenc alatt van; egyes esetekben más módon is felhasználható. Részletekért lásd a felhasználási feltételeket.