• Lekce 11
  • Úlohy
  • Co se dnes probíralo

Lekce 11

Úlohy

Vyhodnocovátko aritmetického výrazu v postfixové notaci

• Sice nepovinný, ale zato fajn procvičení
• Napište program, který na vstupu dostane výraz v postfixovém zápisu
• Předpokládejte
  • Operátory jen pro sčítání, odčítání a násobení
  • Mezery mezi vším

Co se dnes probíralo

Zápis aritmetického výrazu

Infixový zápis

• Běžně používaný zápis, operátory jsou mezi čísly: 1 + 2 + 3.
• Víceznačný, ze syntaktického hlediska nejde poznat, v jakém pořadí vyhodnocovat.
  • (1 + 2) + 3 nebo 1 + (2 + 3)?
  • Pro sčítání je to jedno, protože je asociativní. Můžeme si tedy dovolit psát prostě 1 + 2 + 3.
  • Pro odčítání to jedno není.
  • Abychom nemuseli psát tolik závorek, zadefinujeme, že odčítání má asociativitu zleva.
  • 1 - 2 - 3 tedy interpretujeme jako (1 - 2) - 3.
  • Obdobně mocnění má asociativitu zprava: 2 ^ 3 ^ 4 je 2 ^ (3 ^ 4).
  • Dále samozřejmě hraje roli priorita operátorů: 1 + 2 * 3 je 1 + (2 * 3).
• V programovacích jazycích je operátorů více, jejich priorita je určena tabulkou.
  • Menší prioritu než sčítání má například porovnání <=, ještě menší logická spojka &&.

Postfixový zápis

• Operátor je až za svými operandy.
• Pro počítače jednodušší na zpracování.
• Nepotřebujeme závorky, asociativitu ani prioritu.
• Pozice operátorů ve výrazu přesně určuje pořadí vyhodnocování.
  • 1 2 3 * + je 1 + (2 * 3).
  • 1 2 + 3 * je (1 + 2) * 3.
• Dá se vyhodnocovat pomocí zásobníku (pole, kde přidáváme pouze na konec a odebíráme pouze z konce).
  • Čteme zleva doprava.
  • Pokud narazíme na číslo, přidáme ho na zásobník.
  • Pokud narazíme na operátor, vyjmeme poslední dvě čísla ze zásobníku, provedeme na nich operaci a výsledek přidáme zpět na zásobník.
• Existují algoritmy, které umí infixový zápis převést na postfixový.
  • Shunting-yard

Prefixový zápis

• Podobné vlastnosti jako postfixový, jenom je operátor před svými operandy.
• Znáte jej jako volání funkcí.
  • add(1, multiply(2, 3)) odpovídá + 1 * 2 3, tedy 1 + (2 * 3).
• Hojně využívaný v rodině programovacích jazyků LISP

Zpracování výrazu

Abstraktní syntaktický strom

• AST
• Výraz můžeme reprezentovat pomocí stromu.
  • Každý operátor má dva syny, levý a pravý operand.
  • Na konci každé větve je číslo.
• Přesně určuje pořadí vyhodnocování.
• Používá se také například pro reprezentaci programů v překladači.
  • hezký příklad

Lexer

• Dostaneme výraz jako textový řetězec, chceme jej zpracovat.
• Jako první krok jej musíme rozdělit na čísla a operátory.
• Těmto syntaktickým jednotkám říkáme tokeny.
• Mohlo by se zdát, že stačí rozdělit řetězec podle mezer.
  • Mezer však může být více, někde nemusí být vůbec.
  • Čísla chceme mít jako celek a rovnou je převést z textu na číslo.
• Při zpracování výrazu se tokenizace může zdát zbytečná.
  • Výhodou ovšem je, že se tokenizace nezajímá o význam, takže infixový i postfixový zápis můžeme zpracovávat stejně.
  • Například u zpracování kódu je tokenizace prakticky nutná.
• Části programu, která se stará o tokenizaci, říkáme lexer.

Parser

• Lexer nám rozdělil výraz na tokeny, teď je potřebujeme zpracovat.
• Výsledkem bude AST.
• Parser dodává význam tokenům, infixový a postfixový zápis se zpracovávají jinak.