reverse Polish notation (tsz. reverse Polish notations)
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.
Egy kifejezés RPN‐ben operandusok (számok vagy változók) és operátorok (pl. +, –, *, /) olyan sora, hogy
Példák:
3 + 4
→ RPN: 3 4 +
(2 + 5) * 3
→ RPN: 2 5 + 3 *
2 + 3 * 5
→ RPN: 2 3 5 * +
(a *
precedenciája miatt változik a sorrend)
Algoritmus (két‐operandumos operátorok esetén):
+
):
a = pop()
, b = pop()
.b <operátor> a
.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.
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
std::stack<double>
tárolja az operandusokat.
Előnyök
Hátrányok
Ha infix formát szeretnénk automatán RPN‐vé alakítani, használjuk a Shunting‐Yard algoritmust (Dijkstra):
(
, push a verembe; ha )
, pop‐oljuk, amíg (
nem jön;Ezzel bármilyen infix kifejezés átírható RPN‐re 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.
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.