Postfixová notace

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.

Úvod

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.

Praktické použití

• čtení zleva doprava, výpočty se objevují jakmile je operátor načten
• závorky jsou nepotřebné
• v RPN kalkulátorech není třeba klávesa „=“
• RPN kalkulátory nicméně potřebují klávesu „Enter“ pro oddělení dvou sousedních operandů
• stav je vždy jen hodnota zásobníku očekávající další operaci

Nevýhody

• rozšířenost infixové notace ve vzdělávacích systémech činí RPN kalkulátory nepraktické a těžké k používání
• sousedící čísla musí mít mezi sebou mezeru; je potřeba dodržovat správný zápis k zabránění vzniknutí zmatků (pro představu 12 34 + může na papíře vypadat jako 123 4 +)
• spousta RPN kalkulátorů má programovatelné funkce a několik paměťových registrů. Na některých zkouškách mohou být tyto kalkulátory zakázané, zatímco používání klasických infixových kalkulátorů je dovolené.

Práce s postfixovou notací

Algoritmus pro výpočet postfixového zápisu je příjemně jednoduchý:

• pokud jsou na vstupu znaky
  • přečti další znak
  • jestliže je znak hodnota
    • ulož ji na zásobník
  • jinak znak značí funkci (operátory, jako je + jsou jednoduché funkce přebírající dva argumenty)
    • je známo, že funkce přebírá n parametrů
    • vyber nejvyšší n-tou hodnotu ze zásobníku
      • jestliže je na zásobníku méně než n hodnot
        • (Chyba) uživatel nezadal dostatečný počet parametrů
    • vypočti hodnotu funkce
    • v případě výsledku jej ulož zpět na zásobník
• jestliže je na zásobníku jen jedna hodnota
  • je to výsledek výpočtu
• jestliže je na zásobníku více hodnot
  • (Chyba) uživatel zadal příliš hodnot

Příklad

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.

Když je výpočet hotov, na vrcholu zásobníku je uložen výsledek, v tomto případě 14.

Odkazy

Související články

• Infixová notace
• Prefixová notace
• Zásobník (informatika)
• Programovací jazyk Forth
• Shunting-yard (algoritmus)

Externí odkazy

• Obrázky, zvuky či videa k tématu Postfixová notace na Wikimedia Commons