reverse Polish notation

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.

• 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.

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)

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.

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 + / −

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

• 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).

#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.

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, ${\textstyle O(N)}$ idő és ${\textstyle O(N)}$ 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.

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 ${\textstyle O(N)}$ időben.

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.

• reverse Polish notation - Szótár.net (en-hu)
• reverse Polish notation - Sztaki (en-hu)
• reverse Polish notation - Merriam–Webster
• reverse Polish notation - Cambridge
• reverse Polish notation - WordNet
• reverse Polish notation - Яндекс (en-ru)
• reverse Polish notation - Google (en-hu)
• reverse Polish notation - Wikidata
• reverse Polish notation - Wikipédia (angol)