Úvod do programování - Cvičení č. 9

Úkoly

1. Binární vyhledávací strom. Prostudujte implementaci binárního vyhledávacího stromu. Doplňte do třídy SearchTreeImpl metodu insert, která do stromu vloží nový prvek.

   Podobně jako v metodě contains hledejte při implementaci vkládání nejprve vkládanou hodnotu. Jestliže se hodnota ve stromu už najde, operace končí. Pokud při hledání narazíme na null, vytvoříme nový uzel s vkládanou hodnotou a odkaz na něj zapíšeme místo null. Pro nastavení reference na levý nebo pravý podstrom budete muset rozšířit rozhraní Node o příslušné operace a třídu TreeNode o jejich implementaci.

   Třídy: Node, NodeImpl, SearchTree, SearchTreeImpl, Priklad1

2. Reprezentace výrazu stromem. Prostudujte implementaci tříd reprezentujících operandy a operátory výrazu. Doplňte k nim třídy pro operátory násobení (binární operace) a změny znaménka (unární operace) včetně metody eval(), která provede vyhodnocení operací.

   Třídu pro unární operátor změny znaménka odvoďte podobně jako u binárních operátorů nejprve z abstraktní třídy UnaryExpr, která ponese výraz představující operand.

   Třídy: Expr, BinaryExpr, PlusExpr, ConstExpr, Priklad2

3. Převod stromu výrazu na řetězec. Dopňte do tříd pro reprezentaci výrazu standardní metodu toString(), která převede výraz na ekvivalentní textový řetězec.

   Při převodu operátorů na řetězec nezapomeňte brát v úvahu i prioritu operátorů tak, aby byl zachován význam výrazu. To znamená, že výraz musíte v některých případech (resp. pro jednoduchost vždy) obalit závorkami, např. ((2+3)*(-5)). Pokud to zvládnete, pokuste se najít takové řešení, které bude závorky přidávat jen v nezbytně nutných případech.