bélyegkép|230px|„3+4” összeadása fordított lengyel jelöléssel (RPN) 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.nehezen kiejthető neve miatt Munkásságát később, az 1954-es évben Burks, Warren, és Wright,An Analysis of a Logical Machine Using Parenthesis-Free Notation 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 HamblinMath Forum - Ask Dr. Math 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.Az ötletadó Łukasiewicz-féle lengyel jelölés sem tűnt el: például a LISP-nyelvek napjainkban is használják.

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ésA + 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 15 2 PUSH 215 + ADD 35 4 PUSH 435 * MUL 125 (12) + ADD 17 (17) 3 PUSH 317 − 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óParsing/Shunting yard algorithm is született.

Gyakorlati megvalósítások bélyegkép|230px|RPN logikájú tudományos zsebszámológép 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 ATLASTJohn Walker: ATLAST Autodesk Threaded Language Application System Toolkit 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

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

Kategória:Számítógép-tudomány Kategória:Matematikai jelölések