První série osmnáctého ročníku KSP

Celý leták, který posíláme také papírově, v PDF.

Řešení úloh

18-1-1 Dimenze X (Zadání)

Roboti se v naprosté většině došlých řešení šťastně shledali. Ne vždy však po setkání došlo ke zničení Dimenze X, neboť občas jim hledání trvalo tak dlouho, že se jejich zásoba plutonia rozpadla až na bismut, který se k výbuchu již tolik neměl.

Došlá řešení lze rozdělit na dvě zhruba stejně velké skupiny. V první prohledávali roboti své okolí do stále se zvětšující vzdálenosti a když narazili na hromadu šrotu toho druhého, tak na něj buď počkali, nebo v lepším případě mu šli naproti. Myšlenka je to správná, bohužel implementace pokulhávala. Většina zvětšovala amplitudu prohledávání o konstantu, což dává složitost O(N2). Pouze menšina amplitudu zvětšovala konstantněkrát, čehož výsledkem je pro Dimenzi X nepříznivější složitost O(N).

Druhá skupina řešila úkol tak, že vyslala roboty nižší rychlostí libovolným směrem. Jeden z robotů tak zákonitě musel narazit na hromadu druhého z robotů, což pochopil jako povel zrychlit na plnou rychlost a dohnat tak robota, který se nerušeně vzdaloval stále nízkou rychlostí. Myšlenka je to opět správná, bohužel i tentokrát nebyla implementace vždy v pořádku. Většina totiž řešila snížení rychlosti tak, že robot dělal mezi posuny pauzu. V zadání však bylo, že robot umí udělat v jednom kroku pouze posun o 1 metr na sever nebo na jih (o zastavení tam řeč nebyla). Řešitelné to však je. Například udělat dva posuny jedním směrem a jeden posun zpět, atd. Obecně je ale jakékoliv řešení založené na této myšlence v čase O(N).

Všechny algoritmy si vystačily s maximálně 3 proměnnými, což dává velmi příznivou paměťovou složitost O(1). Bohužel paměťový obvod nemusel mít poruchou omezenou pouze kapacitu, ale i spolehlivost uchovávání informací a proto byla nejcennější řešení ta, které si kromě ukazatele pozice v programu nemusela pamatovat vůbec nic.

Abych byl konkrétní, tak uvádím příklad možného postupu, který pracuje v čase O(N), nepotřebuje žádné pomocné proměnné a za které bylo možné získat plný počet bodů:

{ posun na sever nižší rychlostí }
{  dokud nenajdu druhou hromadu  }
repeat
  Posun_Na_Sever; Posun_Na_Sever; Posun_Na_Jih;
until Stojím_Na_Hromadě;
 
{ narazil jsem na hromadu druhého }
{  robota => zrychlím a doženu ho }
while true do
  Posun_Na_Sever;

Zbyněk Falt

18-1-2 Úřad (Zadání)

U mnoha řešitelů byla znát vcelku oprávněná zášť vůči úřednímu šimlovi, jež mnohdy vyústila v zákeřné chyby, které měly znemožnit další bujení byrokracie. Ve snaze znemožniti kontrolorovi jejich odhalení je důvtipně skrývali v moři rekurze a záplavě cyklů. Někteří z vás se dokonce uchýlili k zákeřné fintě známé jako vypouštění komentářů a popisů řešení. Kvílení kontrolorů a otázky proč to děláš? a jak to funguje?, budiž jim odměnou za dobře odvedenou práci. Ale zpět k úloze.

Jak většina z vás správně poznala, použijeme zásobník. Pokud ze vstupu načteme otevírací závorku, pak ji uložíme na zásobník. Na vrcholu zásobníku tak bude vždy poslední nespárovaná otevírací závorka O. Pokud načtu zavírací závorku Z, mohou nastat tyto tři situace:

  1. Barvy si odpovídají. Pak je vše v pořádku. Navíc je tato závorka použitá a už nikdy ji nebudu potřebovat. Můžeme ji tedy ze zásobníku odebrat.
  2. Barvy si neodpovídají. Takové uzávorkování nemůže být správné, protože O může být uzavřena až za Z. Zároveň ale i otevírací závorka pro Z se může nacházet jedině před O. Tím by se nám zkřížily dva šanony a to je chybné.
  3. V zásobníku nic není. Velmi často opomíjená možnost nám říká, že nalevo od uzavírací závorky není žádná nepoužitá otevírací závorka. V tomto případě samozřejmě končíme s výpisem „ne“.
Pokud program dojde na konec vstupu, tak zjistí, zda je zásobník prázdný. Pokud ano, tak to znamená, že všechny otevírací závorky byly zavřeny a uzávorkování je korektní. V opačném případě jsme něco neuzavřeli a končíme s „ne“. Časová složitost je stejně jako paměťová O(N), s každým prvkem provedeme konstantní počet operací a prvků v pomocném poli je nejvýše N/2.

Někteří z vás zbytečně načítali vstupní data do pole, i když to nebylo nutné. Naštěstí pro ně si tím asymptotickou složitost nezhoršili. Za chybějící nebo špatné popisy, odhady složitosti a hlavně zdůvodnění správnosti se dle míry provinění daly dohromady ztratit až dva body. Pokud se v programu vyskytla chyba, která způsobila nefunkčnost programu, tak jsem strhával dle nefunkčnosti až 4 body, podobně pro pomalá (typicky O(N2)) řešení docházelo ke srážkám úměrným pomalosti.

Program

Jan Bulánek

18-1-3 Keřík (Zadání)

Velká lístečková žranice skončila ve většině případů dle libosti nenasytné píďalky. Kdo už jednou vymyslel ten správný výpočet pohybu housenky, neudělal už většinou žádnou chybu, takže bodové zisky od spokojeně nadládbnuté žížalky byly hojné. Zbytek řešitelů se více či méně úspěšně snažil spouštět z každého význačného bodu prohledávání do hloubky, případně generovat všechny možné dvojice význačných bodů (dále je budeme v souladu s grafovou teorií nazývat vrcholy), za což zaplatil zvýšením časové složitosti. Taková řešení pak získala maximálně 5 bodů. Jak tedy nakrmit žravou housenku v lineárním čase?

Nejprve je třeba si ujasnit, jaký typ grafu náš keřík vlastně je. Víme, že se jedná o obecný strom s neorientovanými hranami. Někteří předpokládali, že máme dán zakořeněný strom s hranami orientovanými a snažili se hledat vrchol, do nějž nevede žádná hrana, aby z něj pak vesele začali počítat. Nikdo ale neříkal, že graf má hrany orientované, právě naopak, logicky hrany musí být obousměrné. Navíc nám nikdo nedal záruku, že takový vrchol, ze kterého nevede žádná hrana, je právě jeden!

Mějme tedy náš obecný neorientovaný strom. Tento strom si „zakořeníme“, čili jeden vrchol prohlásíme za kořen, jeho sousedy za jeho syny, jejich sousedy za syny synů, atd. Uvidíme, že náš algoritmus tím nijak nepoškodíme, děláme to jenom proto, abychom si vše mohli lépe představit. Navíc uvidíme, že kořenem může být libovolný vrchol.

Jistě mi budete věřit, že nejvýživnější cesta musí začínat a končit v listu, to jest ve vrcholu stupně jedna. Kdyby tomu tak nebylo a cesta by končila v nějakém vrcholu stupně >1, pak bychom cestu mohli z tohoto vrcholu ještě prodloužit až do nějakého listu.

Dobře, ale pak cesta musí vypadat tak, že začíná v nějakém listu, pak míří nahoru směrem ke kořeni, dorazí do nějakého vrcholu, ve kterém se jakoby láme a míří zase dolů až do nějakého jiného listu a skončí.

Představme si, že se nacházíme v nějakém vrcholu v a chtěli bychom vědět, jaká nejlepší cesta přes něj prochází, čili láme se v něm. Hodilo by se nám, kdybychom u každého jeho syna měli spočítáno, jaká nejlepší cesta vede od nějakého listu v jeho podstromě až do něj. Pak bychom si ze všech synů vrcholu v vybrali ty dva nejvýhodnější, sečetli jejich hodnoty, přičetli bychom počet lístečků ve vrcholu v a kýženou výživnost cesty lámající se ve vrcholu v bychom znali. Je pro nás těžké spočítat tyto hodnoty u všech synů? Kdepak, uděláme to úplně stejným způsobem, tedy rekurzí.

Algoritmus tedy funguje tak, že pro každičký vrchol ve stromě spočítáme dvě hodnoty: Jak výhodná cesta se v něm láme (tuto informaci získáme rekurzivním voláním synů) a jaká nejlepší cesta vedoucí z nějakého listu v některém z jeho podstromů v něm končí (tuto informaci předáme nahoru jeho otci).

Nakonec stačí projít všechny vrcholy a najít ten s nejvyšší hodnotou lámající se cesty a z něj pak spustit výpis na obě strany. Samozřejmě, že jedna strana nemusí existovat, to například když má strom tvar cesty (např. 1→2→3→4).

Jak rychlá je tato rekurze? Do každého vrcholu přijdu jenom jednou, tedy O(N), a na každou hranu se podívám také jenom jednou, tedy O(M). My ale víme, že pracujeme se stromem, tedy pro něj platí, že M=N-1, takže složitost rekurze je opravdu O(N). Načtení hodnot, závěrečné vyhledání nejvýhodnějšího vrcholu a výpis cesty nám též trvá O(N). Paměťová složitost je při reprezentaci seznamem sousedů také lineární.

Program

Jana Kravalová

18-1-4 Dortík (Zadání)

Sfoukněte svíce, uchopte do ruky nůž, nakrojte dort a vydatně se posilněte na následující vzorové řešení.

Nejprve několik poznámek k došlým řešením. Někteří řešitelé si bohužel do zadání domysleli některé dodatečné podmínky, které jsme ve skutečnosti nikde netvrdili. Například to, že úhly jsou vždy jen celá čísla a že se nikdy nevyskytnou dvě svíčky na stejném místě. Takové podmínky ovšem úlohu zjednodušují, proto jsem za takové věci strhával body. Pokud si příště nebudete jisti, řešte raději tu těžší variantu, případně není problém se nás zeptat.

Ale teď již k věci. Ukážeme si řešení, které kdyby dostalo na vstupu úhly svíček vzestupně setříděné, seběhlo by v lineárním čase vzhledem k počtu svíček. Nejprve si uvědomíme, že mezi každými dvěma sousedními svíčkami v K-úhelníku musí být úhel 360/K. Další naše pozorování bude, že každá svíčka může ležet maximálně v jednom K-úhelníku.

Mějme tedy na vstupu setříděné úhly U. Dle našich úvah z nich teď můžeme klidně vyházet duplikáty, tedy ze svíček na stejné pozici nechat jen jednu. Poté projdeme seznam svíček od nejmenšího úhlu k největšímu a budeme si pro i-tou svíčku s úhlem Ui počítat následující věci: Kde (a jestli vůbec) má nějakého „předchůdce“ Pi na potenciálním K-úhelníku (tedy svíčku na úhlu Ui-360/K), a kolikátá svíčka Ci s rozestupem 360/K v řadě to je (čili kde se v potenciálním K-úhelníku nachází).

Když budeme mít tato data spočítána, stačí se podívat, jestli existuje svíčka s právě K-1 pravidelnými předchůdci. Jestliže ano, potom touto svíčkou končí K-úhelník a proskáčeme skrz zpětné odkazy P po svíčkách a výsledek vypíšeme.

Zbývá si rozmyslet, jak efektivně počítat žádaná data. Použijeme k tomu metodu dvou posuvných indexů. Mějme indexy i a j, kde j bude vždycky ten více vepředu. Na začátku nastavíme i na 1 a j na 2. Pokud je rozdíl úhlů Ui a Uj roven 360/K, j-tá svíčka má přechůdce i a je (Ci+1)-ní v pořadí, nastavíme tedy příslušně hodnoty Pj a Cj. Pokud je Uj-Ui>360/K, tedy svíčky jsou příliš daleko, zvýšíme i o 1, čímž je k sobě přiblížíme, pokud Uj-Ui<360/K, zvýšíme o 1 j, čímž je oddálíme. Všimněte si, že pokud jsou úhly setříděné, náš postup skutečně najde všechny dvojice správně vzdálených svíček.

Vyházení duplikátů zvládneme jedním průchodem přes U v lineárním čase, stejně tak výpis výsledků proskákáním pole P a C. Při posouvání dvou indexů oba pouze rostou, tedy se nad každým prvkem vykonají maximálně dvě operace, máme tedy časovou složitost O(N). Ještě je potřeba započítat čas na třídění na počátku, to umíme například použitím nějakého rychlého kuchařkového algoritmu v čase O(N log N), dohromady tak máme časovou složitost O(N log N). Všimněte si, že třídění je nejpomalejší částí našeho algoritmu. Paměťová složitost je O(N), pamatujeme si tři pole délky N.

Ještě poznámka k programu: ve skutečnosti bychom se obešli bez jednoho z polí P či C, pro větší srozumitelnost však v programu používáme obě.

Program

Tomáš Valla

18-1-5 Matlalové (Zadání)

Matlalové jsou již za vysokým drátěným plotem a jen občas hromada přebytečného pletiva zaclání ve výhledu. Spíše byl problém postavit plot dříve, než Matlalové zase odletí.

Nebudu déle zdržovat a rovnou přejdu ke vzorovému řešení. Stoly si rozdělíme na dvě vodorovné a dvě svislé hrany stolu. Nejprve zjistíme, které vodorovné hrany tvoří obvod stolů. Pak můžeme stoly otočit o 90° a použít stejný algoritmus na vertikální hrany. Proto se zabývejme pouze horizontálními hranami.

Představme si horizontální přímku, kterou posunujeme přes naši soustavu stolů, hledanému sjednocení stolů budeme říkat oblast. Jak přecházíme přímkou do vnitřku oblasti a ven z ní, připočítáváme tyto hrany přechodu k celkovému obvodu. Horizontální část obvodu se může změnit pouze na místě, kde začíná nebo končí nějaký stůl vodorovnou hranou. To je hlavní idea algoritmu.

Mějme tedy pole 2n vodorovných hran. Zvolíme si směr průchodu podle rostoucí y-nové souřadnice. U každé hrany si zapamatujeme

Nyní pole setřídíme podle dvou kritérií. Prvním je y-nová souřadnice. Pokud ji mají dvě hrany stejnou, pak upřednostníme tu, která je otevírající. To proto, abychom mezi stoly stojícími těsně vedle sebe nepostavili plot.

Při průchodu přímkou přes oblast můžeme na přímce zobrazit oblast jako několik intervalů. Pokud si budeme tyto intervaly pamatovat, změna intervalu znamená konec nebo začátek oblasti čili příspěvek do obvodu. Je vidět, že intervaly mohou začínat a končit pouze na místě, kde začínají nebo končí stoly. Těchto bodů je maximálně 2n. Místo celé přímky si stačí pamatovat pouze 2n - 1 bloků. Intervaly se pak mohou skládat až z O(n) těchto bloků. Jak budeme aktualizovat intervaly? Pokud projdeme otevírající hranou, znamená to, že jsme uvnitř nějakého stolu, pokud projdeme ukončující hranou, právě jsme stůl opustili. Stolů ale může na sobě ležet více a proto si pro každý blok zapamatujeme číslo ci, kolik stolů je právě na jeho místě. Projdeme hrany jednu po druhé tak, jak je máme setříděny a pokud je to hrana otevírající, přidáme interval na místě hrany, jinak interval odebereme. Přidání a odebrání intervalu znamená přičtení nebo odečtení jedničky od ci všech bloků, do kterých hrana zasahuje. Pokud se přitom změní ci některého bloku z 0 na 1 nebo z 1 na 0, znamená to, že jsme na tomto bloku vstoupili do oblasti nebo ji opustili, a proto délku tohoto bloku přičteme k obvodu. Říkáme, že blok je pokryt, pokud má ci > 0.

Popsaný algoritmus spočte horizontální obvod jako součet délek bloků při změně jejich pokrytí. Jak dlouho mu to bude trvat? Třídení nám bude trvat čas O(n log n). Pak pro každou hranu aktualizujeme O(n) bloků. Celkem tedy O(n2). Paměti spotřebujeme pouze lineárně – O(n).

Pokud si budeme intervaly uchovávat trochu chytřeji, dá se časová složitost trochu zlepšit. Použijeme k tomu tzv. intervalový strom. Intervalový strom je binární vyvážený strom, který v našem případě vypadá následovně. Každému uzlu přiřadíme interval. Listům přiřadíme naše bloky, jak je známe, seřazené zleva doprava. Vnitřnímu uzlu přiřadíme interval daný sjednocením intervalů jeho synů. Kořen stromu má tedy přiřazen celý interval. Protože strom je vyvážený a má O(n) listů, je jeho hloubka O(log n). Každý uzel má tyto vlastnosti:

Potřebujeme umět přidat do stromu a odebrat z něj interval v lepším čase než O(n). Jak asi u stromu očekáváte, bude to O(log n). Protože se interval skládá až z O(n) bloků, nemůžeme si dovolit při jeho přidání zaktualizovat všechny bloky, z kterých se skládá. Rozmyslíme si, že se každý interval dá rozložit do O(log n) intervalů reprezentovaných uzly našeho stromu. Tento rozklad najdeme podobně jako při přidávání intervalu, označme ho I. Budeme ho realizovat rekurzivní funkcí find. Začneme v kořeni stromu. Aktualní uzel označme u, interval uzlu uznačme Iu. Pokud I a Iu mají prázdný průnik, skončíme. Pokud Iu je podinterval I, Iu je jeden z hledaných intervalů. Jinak se částečně překrývají a zavoláme funkci find na oba syny. Průběh volání funkce bude vypadat takto. Z kořene projdeme po synech až k uzlu, kde interval I zasahuje do obou synů. Zde se průchod rozdělí na dvě větve. Jedna jde po levé straně intervalu, druhá po pravé. Všechny intervaly mezi nimi spadají zcela do intervalu I. Zkuste si nakreslit obrázek. Protože při zavolání funkce find na kořen projdeme maximálně dvě cesty z kořene k listům, je časová složitost této operace O(log n).

Vkládání a odebírání intervalu bude podobné funkci find. V každém z uzlu, na který se interval rozložil, aktualizujeme vlastnosti tables a covered. Vlastnost tables je počet stolů, jejichž rozklad intervalu obsahuje tento uzel. Pokrytí intervalu, covered, udává v reálných souřadnicích, kolik z intervalu je pokryto stoly. Pokrytí je větší než nula i v případě, kdy tables je rovno nula a některé intervaly v jeho synech jsou pokryty. Tyto vlastnoti se vztahují pouze k podstromům daného uzlu, nikoli k jeho rodičům. Rozmyslete si, že je dokážeme při vkládání a odebíraní intervalu aktualizovat. Funkce pro vkládání a odebírání bude vracet změnu pokrytí v daném podstromě. Proto pokud je interval uzlu pod stolem a uvnitř jeho podstromu se změní pokrytí, tento uzel ho znuluje. Jinak se propaguje až do kořene a nakonec je celková změna pokrytí přičtena k počítanému obvodu.

Protože přidání a odebrání intervalu nám trvá čas O(log n) a stálé máme celkem 2n hran, celkový čas algoritmu je O(n log n). Paměťová složitost zůstala lineární.

Program

Petr Škoda

18-1-6 Kompilované komplikátory (Zadání)

Jak si mnoho řešitelů uvědomilo, tuto úlohu šlo řešit i podstatně přímočařeji než v textu seriálu naznačeným postupem, například konstrukci syntaktického stromu lze přeskočit a generovat rovnou požadovaný mezikód. My si nejprve implementujeme jedno takové jednoduché řešení a poté si ukážeme, jak si ho vylepšit – kvůli tomu již bude nutné se přidržet postupu popsaného v seriálu. Abychom šetřili naše lesy a nervy méně otrlých řešitelů, asi 700-řádkový program k tomuto rozšířenému řešení zde netiskneme. Můžete ho nalézt na adrese http://ksp.mff.cuni.cz/h/ulohy/18/ksp1816b.c.

Lexikální analýza je v našem případě triviální – načteme znak ze vstupu a rozhodneme, zda je to jeden z operátorů. Je-li tomu tak, rovnou vrátíme jemu odpovídající token. Další možností je začátek jména identifikátoru nebo číslo, pak načteme jeho zbytek.

V jednoduchém řešení bude sémantická analýza spojena se syntaktickou a místo stavby syntaktického stromu budeme rovnou vypisovat výpočet v mezikódu. Pro syntaktickou analýzu se prakticky se používají dva hlavní přístupy. Jeden z nich je zkonstruovat si zásobníkový automat, který rozpoznává danou gramatiku. Tento postup je vysvětlen například v řešení úlohy 9-3-3. Druhý přístup je složit analyzátor ze vzájemně rekurzivních funkcí, které odpovídají symbolům gramatiky. Implementace tohoto postupu bývá pro člověka o něco čitelnější a dají se v ní lépe ošetřovat chyby a jiné speciální případy. My se přidržíme druhého postupu. Syntaktickou analýzu budou zajišťovat funkce cti_vyraz, která zpracovává celý výraz nebo jeho podvýraz uvnitř závorkek, cti_faktor, která zpracovává podvýraz, jehož operátory jsou násobení či dělení, a cti_term, která vyhodnotí podvýraz tvořený identifikátorem, číslem, nebo uzávorkovaným výrazem. Každá z těchto funkcí přečte co nejdelší kus kódu, který jí odpovídá, vypíše příkazy nutné pro jeho vyhodnocení a vrátí identifikátor proměnné, v níž je uložena jeho hodnota. Například funkce cti_vyraz pomocí funkce cti_faktor čte postupně kusy výrazu oddělené znaménky plus a mínus, dokud nenarazí na konec výrazu či závorky, a sčítá či odčítá odpovídající hodnoty. Funkce cti_faktor se chová podobně, volá cti_term a kontroluje, zda po nich následuje krát či děleno. Funkce cti_term se podívá, zda následuje proměnná či číslo (pak ho rovnou vrátí), nebo otevírací závorka, na jejíž vnitřek zavolá cti_vyraz. Každá z těchto funkcí také posune ukazatel ve vstupu na první znak, který nezpracovala.

Celý tento postup lze realizovat s paměťovou i časovou složitostí lineární v délce zadaného výrazu. Pro časovou složitost stačí nahlédnout, že je omezená počtem volání funkce cti_term, a ta vždy načte alespoň jeden token ze vstupu.

Nyní si popíšeme možná vylepšení tohoto postupu. U každé fáze si řekneme něco k tomu, co jde udělat lépe. Mimo jiné se budeme zabývat zotavením se z chyb. Pokud se v kódu programu vyskytne chyba (v našem případě třeba nespárované závorky), je poněkud nešikovné s překladem okamžitě skončit, například proto, že už se nevypíšou hlášení pro další chyby. Nejde tedy opravit všechny chyby naráz a je nutné po každé z nich program znovu kompilovat, což může být dost pomalé. Je zřejmě lepší se s chybou nějak vypořádat a pokračovat v překladu.

Smysluplné ošetření chyb při lexikální analýze je obtížné, protože v této fázi toho o vstupu mnoho nevíme. Chyby se proto řeší prostým zahozením nerozpoznaných znaků. Dojde-li k chybě v syntaktické analýze (například proto, že po sobě následují dva operátory a podobně), příslušná funkce si domyslí nějaký token, který se jí hodí, nebo ten aktualní zahodí, podle toho, co dává víc smysl.

Co se týče vylepšení lexikální analýzy, všimneme si, že syntaktická analýza čte vstup postupně a nikdy se nevrací. Je tedy zbytečné si vstup rozložený na tokeny pamatovat celý. Lexikální analýzu proto budeme realizovat funkcí, která ze vstupu načte a vrátí další token (dalsi_token), a sémantická analýza si ji bude volat podle potřeby. Ve skutečnosti se občas hodí se ve vstupu o jeden token vrátit – například když cti_faktor narazí na plus, ukončí se, ale toto plus by měla zpracovat funkce cti_vyraz. Proto cti_faktor nejdřív vrátí plus zpět do vstupu. K tomu slouží funkce vrat_token.

Dalším drobným trikem je, že si udržujeme tabulku identifikátorů hodnota_na_promennou, a když načteme dvakrát identifikátor se stejným jménem, vrátíme místo něj jeho pořadí v tabulce, takže nemusíme nikde dál testovat, zda jsou dva identifikátory stejné (promenna_na_hodnotu je vlastně hešovací tabulka, která nám umožní záznamy v tabulce hodnota_na_promennou hledat rychle – víc k hešování viz kuchařka druhé série sedmnáctého ročníku).

Syntaktickou analýzu si oddělíme od sémantické. Syntaktická analýza už nebude přímo generovat mezikód, ale místo toho každému zpracovanému podvýrazu přiřadí nějaké číslo. Tato čísla by měla být taková, že výrazy s různou hodnotou dostanou vždy různé číslo, zatímco výrazy se stejnou hodnotou dostanou stejné číslo – například výrazy x + y a x - y dostanou různá čísla, protože jejich hodnoty se mohou lišit, zatímco výrazům x - x a 0 by mělo být přiřazeno stejné číslo. To děláme tak, že si udržujeme tabulku hodnot výrazů, které jsme již viděli (hodnota_na_vyraz a vyraz_na_hodnotu, opět používáme hešování), v níž si pamatujeme, jak se každé číslo hodnoty spočítá. Pokud narazíme na výraz, který už v tabulce je, vrátíme jeho číslo, jinak mu přidělíme nové číslo a přidáme ho do tabulky. Podrobnější vysvětlení tohoto postupu viz řešení úlohy 17-2-1. Snadno nahlédneme, že toto je v podstatě jen jiná reprezentace syntaktického stromu – čísla hodnot odpovídají vrcholům, a abychom určili syny vrcholu, podíváme se do tabulky hodnota_na_vyraz. Číslování hodnot nám ale umožní zajistit, že stejnou hodnotu nebudeme počítat dvakrát – když na ni narazíme podruhé, budeme místo ní používat pomocnou proměnnou, do níž jsme ji poprvé spočítali.

Navíc se nám toto očíslování hodnot hodí při zjednodušování výrazů. Budeme chtít rovnou vyhodnocovat konstantní výrazy a také aplikovat jednoduché algebraické identity typu x - x = 0. Abychom mohli tuto optimalizaci provést, je potřeba zjistit, zda oba operandy mínusu jsou stejné. Vzhledem k tomu, jak si výrazy reprezentujeme, stačí porovnat čísla jejich hodnot, není potřeba procházet stromy výrazů a ověřovat, zda si odpovídají (to by nám mohlo zhoršit časovou složitost na kvadratickou). Zjednodušování výrazů provádíme tak, že kdykoliv vytváříme vrchol stromu, který odpovídá nějakému operátoru, podíváme se na jeho operandy a určíme, zda ho můžeme nějak zjednodušit. Toto provádí funkce postav_strom. Například pokud vyhodnocujeme výraz (x+1) + 2, postav_strom dostane plus, jehož parametry mají čísla hodnot h1 a h2, a z tabulek zjistíme, že h2 je ve skutečnosti konstanta 1, a že h1 je součet hodnot h3 a h4, kde h4 je konstanta 2. Konstanty sečteme, dostaneme 3 a zjistíme si, že číslo hodnoty pro 3 je h5. Zjednodušený výraz tedy bude h3 + h5, což odpovídá x+3. Tomuto výrazu přidělíme nové číslo hodnoty h6, dáme ho do tabulek a h6 vrátíme.

Jednou z komplikací, které se v tomto řešení vyhýbáme, ale prakticky je nutné se jí zabývat, je provedení vedlejších účinků zjednodušovaných výrazů. Například máme-li výraz funkce () * 0, jeho hodnota je vždy 0, ale přesto je nutné funkci zavolat. Prakticky tedy nestačí pouze vracet hodnotu zjednodušeného výrazu, ale je nutné zajistit, aby se také provedly tyto vedlejší akce. V našem případě jediný takový problém je dělení 0 – například výraz x/y - x/y by mohl způsobit chybu, pokud y=0, ale zjednodušený výraz 0 chybu způsobit nemůže. Tento problém pro jednoduchost řešit nebudeme – konec konců, v platném programu se dělení nulou vyskytnout nesmí (až na výjimky).

Vedlejší účinky by navíc mohly měnit hodnoty proměnných, které se ve výrazu používají. Například při vyhodnocování výrazů v C je nutné při dosažení sequence pointu (což je místo, na kterém je zaručeno, že se vedlejší účinky vykonají) upravit čísla hodnot ovlivněných proměnných.

Poslední fází je sémantická analýza, tj. expanze do mezikódu. V ní vypíšeme výrazy nutné pro spočtení hodnoty, která odpovídá číslu hodnoty celého výrazu. Podíváme se tedy do tabulek, jak jsme toto číslo dostali, rekurzivně vyhodnotíme čísla hodnot podvýrazů a vypíšeme příslušnou operaci, která z nich spočte výsledek. Abychom nepočítali nějaký výraz dvakrát, u každého čísla hodnoty si pamatujeme, zda jsme ho už počítali, a když ho potřebujeme podruhé, použijeme místo něj příslušnou pomocnou proměnnou. Přidělování jmen pomocným proměnným řešíme jednoduše, k prefixu tmp připojíme číslo hodnoty.

Je snadné si rozmyslet, že všechna tato rozšíření stále fungují v lineárním čase.

Jednodušší program

Složitější program

Zdeněk Dvořák