From Wikipedia, the free encyclopedia
Postfixová notace (též reverzní polská notace, zkráceně jako RPN) je způsob zápisu matematického výrazu, kde operátor následuje své operandy, přičemž je odstraněna nutnost používat závorky (priorita operátorů se vyjadřuje samotným zápisem výrazu). Vytvořil ji australský filozof a počítačový vědec Charles Hamblin v polovině padesátých let. Oblíbená je při implementaci vyhodnocování výrazů, například při programování překladače nebo interpretu pro různé programovací jazyky.
Postfixová notace je obdobou prefixové notace, která byla představena v roce 1920 polským matematikem Janem Łukasiewiczem. V běžném životě i programování se však používá přirozenější infixová notace, která však vyžaduje používání závorek.
V postfixové notaci (dále jen RPN) operátory následují za operandy; pro představu sčítání čísel tři a čtyři se zapíše jako „3 4 +“. Jestliže provádíme více operací, je operátor umístěn za druhý operand, takže výraz „3 - 4 + 5“ zapsaný ve standardní infixové notaci bude v RPN zapsán jako „3 4 - 5 +“; nejprve odečteme 4 od 3 a posléze přičteme 5. U RPN odpadá nutnost používání závorek používaných v infixové notaci. Výraz může být zapsán „3 - 4 + 5“, což se liší od „(3 - 4) + 5“ nebo od „3 - (4 + 5)“ a pouze závorky odlišují tyto zápisy. V RPN tento výraz bude zapsán jako „3 4 5 + -“.
Interpretry postfixové notace jsou zásobníkového typu; operandy jsou uloženy na zásobník a když je operace provedena, jsou operandy vyzvednuty ze zásobníku a výsledek je uložen zpět na zásobník. Zásobník a potažmo RPN je velmi jednoduché implementovat.
Algoritmus pro výpočet postfixového zápisu je příjemně jednoduchý:
Infixový výraz „5 + ((1 + 2) * 4) − 3“ může být přepsán do RPN jako
5 1 2 + 4 * + 3 −
Výraz je počítán zleva doprava.
Vstup | Operace | Zásobník | Popis |
---|---|---|---|
5 | Ulož operand | 5 | |
1 | Ulož operand | 5, 1 | |
2 | Ulož operand | 5, 1, 2 | |
+ | Sečti | 5, 3 | Vyber dvě hodnoty (1, 2), zpracuj a ulož výsledek (3) |
4 | Ulož operand | 5, 3, 4 | |
* | Vynásob | 5, 12 | Vyber dvě hodnoty (3, 4), zpracuj a ulož výsledek (12) |
+ | Sečti | 17 | Vyber dvě hodnoty (5, 12), zpracuj a ulož výsledek (17) |
3 | Ulož operand | 17, 3 | |
− | Odečti | 14 | Vyber dvě hodnoty (17, 3), zpracuj a ulož výsledek (14) |
Když je výpočet hotov, na vrcholu zásobníku je uložen výsledek, v tomto případě 14.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.