reverse Polish notation

Üdvözlöm, Ön a reverse Polish notation szó jelentését keresi. A DICTIOUS-ban nem csak a reverse Polish notation szó összes szótári jelentését megtalálod, hanem megismerheted az etimológiáját, a jellemzőit és azt is, hogyan kell a reverse Polish notation szót egyes és többes számban mondani. Minden, amit a reverse Polish notation szóról tudni kell, itt található. A reverse Polish notation szó meghatározása segít abban, hogy pontosabban és helyesebben fogalmazz, amikor beszélsz vagy írsz. Areverse Polish notation és más szavak definíciójának ismerete gazdagítja a szókincsedet, és több és jobb nyelvi forráshoz juttat.

Főnév

reverse Polish notation (tsz. reverse Polish notations)

  1. (informatika) fordított lengyel jelölés

A fordított lengyel forma (RPN) egy kifejezésábrázolási mód, melyben az operátorok a műveleti operandusok után következnek. Ezzel a hagyományos, infix formára jellemző zárójelezési és precedencia‐szabályozási problémákat kiküszöböli: a kifejezés értékelése során nem kell külön ügyelni a műveleti sorrendre, hiszen minden precedencia már az RPN‐be történő átalakításkor rendeződik.



1. Történeti áttekintés

  • Lengyel jelölés: 1920‐as években Jan Łukasiewicz lengyel logikus vezette be a prefix notációt (operátor—operandus—operandus), hogy a logikai kifejezések zárójelezés‐mentesen megjeleníthetők legyenek.
  • Fordított lengyel (postfix): A prefix „fordított” változata, melyet Charles Hamblin és Douglas McIlroy dolgozott ki az 1950–60-as években számítógépes kiértékelésre.
  • Először a HP-35 asztali számológépben jelent meg hardveres RPN‐kiértékelő egységként, népszerűsítve az RPN‐alapú kalkulációt.



2. Az RPN definíciója

Egy kifejezés RPN‐ben operandusok (számok vagy változók) és operátorok (pl. +, –, *, /) olyan sora, hogy

  1. minden operandus egyszer szerepel,
  2. minden operátor közvetlenül az általa igényelt számú operandus (egy‐, két‐, vagy több‐argumentumú operátor esetén több operandus) után áll.

Példák:

  • Infix: 3 + 4 → RPN: 3 4 +
  • Infix: (2 + 5) * 3 → RPN: 2 5 + 3 *
  • Infix: 2 + 3 * 5 → RPN: 2 3 5 * + (a * precedenciája miatt változik a sorrend)



3. Miért érdemes RPN‐t használni?

  1. Egyszerű kiértékelés: Nincs szükség zárójelekre és precedencia‐táblázatra; egyetlen algoritmus—verem—elég.
  2. Determinált sorrend: Az operandusok és operátorok sorrendje egyértelműen meghatározza a műveleti sorrendet.
  3. Építőkocka‐algoritmusok: Kompilátorok és interpreterek gyakran belsőként RPN‐t (stack‐machine bytecode‐ot) használnak.
  4. Memóriahasználat: Veremben történő kiértékelés – in situ, pusztán egy verem és egy token‐olvasó; nincs szükség rekurrens függvényhívásokra.



4. RPN‐kiértékelés veremmel

Algoritmus (két‐operandumos operátorok esetén):

  1. Kezdjünk egy üres veremmel.
  2. Olvassunk be balról jobbra minden token‐t (token = szám vagy operátor):
    • Ha szám: toljuk a verembe.
    • Ha operátor (pl. +):
      1. pop‐oljuk a legfelső két elemet: legyen a = pop(), b = pop().
      2. Számoljuk ki b <operátor> a.
      3. Toljuk vissza a verembe az eredményt.
  3. A végén a veremben egyetlen szám marad: ez a kifejezés értéke.

Lépésről‐lépésre példa: RPN: 2 5 + 3 * 9 2 1 + / −

Token Verem művelet Verem állapot
2 toljuk
5 toljuk
+ pop a=5, b=2; push b+a=7
3 toljuk
* pop a=3, b=7; push b*a=21
9 toljuk
2 toljuk
1 toljuk
+ pop a=1, b=2; push b+a=3
/ pop a=3, b=9; push b/a=3
pop a=3, b=21; push b−a=18

Végül a verem tetején az 18 áll — ez a teljes kifejezés eredménye.



5. Rendszer‐ és nyelvi használat

  • Hardveres RPN‐kalkulátorok (HP‐széria): közvetlen RPN‐beviteli mód, nincs zárójel, minden gombnyomás azonnal töltődik a verembe.
  • Nyelvi belső reprezentáció:
    • Lisp‐szerű nyelvek prefixet használnak, de belsőben fordított lengyel (stack‐machine) bytecode‐ot generálnak (Java bytecode, Python bytecode).
    • Assembler‐szerű VM‐ek (például a Java Virtual Machine) RPN‐pozíciójú utasításkészletet használnak (pl. iadd előbb pop‐olja a két operandust, majd push‐olja az összeget).



6. Implementáció C++11‐ben

#include <iostream>
#include <sstream>
#include <stack>
#include <string>
#include <stdexcept>

double evalRPN(const std::string& expr) {
    std::istringstream tokens(expr);
    std::stack<double> st;
    std::string tok;

    while (tokens >> tok) {
        if (std::isdigit(tok) || 
            (tok.size()>1 && (tok=='-'||tok=='+') && std::isdigit(tok)) ) {
            // Ha szám (egész vagy lebegő)
            st.push(std::stod(tok));
        }
        else {
            // Operátor esetén legalább két operandus kell
            if (st.size() < 2)
                throw std::runtime_error("Hibás kifejezés");
            double a = st.top(); st.pop();
            double b = st.top(); st.pop();
            double res;
            if      (tok == "+") res = b + a;
            else if (tok == "-") res = b - a;
            else if (tok == "*") res = b * a;
            else if (tok == "/") {
                if (a == 0.0) throw std::runtime_error("Nullával osztás");
                res = b / a;
            }
            else throw std::runtime_error("Ismeretlen operátor: " + tok);
            st.push(res);
        }
    }
    if (st.size() != 1)
        throw std::runtime_error("Hibás kifejezés (több maradt a veremben)");
    return st.top();
}

int main() {
    std::string line;
    std::cout << "Adja meg RPN formában a kifejezést (pl. 2 5 + 3 *): ";
    std::getline(std::cin, line);
    try {
        double eredm = evalRPN(line);
        std::cout << "Eredmény: " << eredm << "\n";
    } catch (std::exception& e) {
        std::cerr << "Hiba: " << e.what() << "\n";
    }
    return 0;
}

Megjegyzések a kódhoz

  • A std::stack<double> tárolja az operandusokat.
  • Tokenizálás szóköz szerint történik, és minden token vagy szám, vagy operátor.
  • Hibakezelés: túl kevés operandus, ismeretlen operátor, nullával osztás, maradó érték a veremben.



7. Előnyök és hátrányok

Előnyök

  • Zárójel‐mentesség: nincs „(” vagy „)”, a kifejezés mindig egyértelmű.
  • Egyszerű parser: nem kell shunting‐yard vagy rekurzív leszármaztatás; csak verem kell.
  • Hatékony: egyetlen bejárás, idő és memória a verem számára.

Hátrányok

  • Emberi olvashatóság: az infix kifejezések könnyebben érthetők.
  • Manuális konverzió: ha infix szinten gépelünk, először át kell alakítani RPN‐be (shunting‐yard algoritmussal).
  • Hosszabb szintaxis: minden operátort kissé később írunk, néha nehezíti az írást.



8. Shunting‐yard: infix → RPN konverzió

Ha infix formát szeretnénk automatán RPN‐vé alakítani, használjuk a Shunting‐Yard algoritmust (Dijkstra):

  1. Használjunk két veremet (operátorok és kimeneti lista).
  2. Olvassuk a tokeneket;
    • ha szám, toljuk a kimeneti verembe;
    • ha operátor, akkor amíg a verem tetején lévő operátor precedenciája nagyobb vagy egyenlő (és bal‐asszociatív), pop‐oljuk és toljuk a kimenetre;
    • push‐oljuk az aktuális operátort;
    • ha (, push a verembe; ha ), pop‐oljuk, amíg ( nem jön;
  3. A befejezéskor ürítsük ki a veremet a kimeneti listára.

Ezzel bármilyen infix kifejezés átírható RPN‐re időben.



9. Következtetés

A fordított lengyel alak egyszerre elegáns elméleti konstrukció (prefix formából ered) és rendkívül gyakorlati eszköz a programok és kalkulátorok világában.

  • Verem‐alapú értékelés nyújt konzisztens, zárójelezés‐mentes, gyors kiértékelést.
  • A shunting‐yard algoritmus biztosítja az egyszerű átalakítást infixből RPN‐be, ha felhasználóbarát bevitelt szeretnénk együtt a belső RPN‐kiértékeléssel.

Ezért a fordított lengyel forma ismerete nélkülözhetetlen minden komolyabb compilerszemantika‐, interpreter‐, illetve beágyazott kalkulátor‐fejlesztő számára.