Postfixová notace

Notace
	Prefixová notace;
	Infixová notace;
	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ý:

dokud 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 n hodnot 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.

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)