OOP prakticky: Zjednodušování

…aneb dost bylo nulových výrazů!
24. 12. 2008

Už u derivací jsme se setkali s tím, že jsme ve výrazu měli spoustu částí, které by jistě šly zkrátit. Například je zbytečné zobrazovat výraz (0 * a), protože nula krát cokoliv je stejně nula. Jak to tedy provedeme? Základní zjednodušení můžeme udělat tak, že pokud je daný výraz ve výsledku nulový, prostě vrátíme novou nulovou Konstantu. Ve specifických případech poté můžeme metodu zjednodušení přepsat tak, aby zjednodušovala poněkud sofistikovaněji. Začněme ale s tím nulovým výraz. Budeme potřebovat metodu, která zjistí, zda je daný výraz nulový. Otázka zní: má smysl definovat tuto metodu pro každý Matematický Výraz? Jistě můžeme rozhodnout, zda třeba Součet nebo Rozdíl je ve výsledku nulový. Stejně tak se můžeme rozhodnout u Konstanty. Jedinou potíž dělá proměnná. Tam ta metoda moc smysl nemá, protože Proměnná nemůže být nikdy nulová, leda až po dosazení. Nicméně stále jsme schopni rozhodnout, kdy je Výraz nulový a kdy ne – v případě Proměnné vrátíme vždy False, každá Proměnná je nenulová. Jak metodu zavedeme? Přidáme ji do třídy Matematický Výraz takto:

   1: abstract class MatematickyVyraz
   2: {
   3:     public abstract MatematickyVyraz Derivace();
   4:     public abstract MatematickyVyraz Substituce(string NazevPromenne, MatematickyVyraz Hodnota);
   5:     public abstract MatematickyVyraz Kopie();
   6:     public abstract bool NulovyVyraz();
   7: }

Zajímavá otázka je, zda má být metoda abstraktní. Můžeme ji totiž definovat pouze jako virtuální metodu s tím, že defaultně bude vracet False. Ušetřili bychom si trochu psaní ve třídách, u kterých nejsme schopni zjistit, zda je výraz nulový (Proměnná) nebo ve výrazech, které nikdy nebudou záporné – kterákoliv funkce s oborem hodnot, ve kterém se nenachází nula (1 / x). Pro jednoduchost ponechme metodu abstraktní a v každé třídě si tuto metodu napíšeme zvlášť. Pojďme tedy implementovat metodu NulovyVyraz() v našich třídách. Začneme konstantou. Zde je výraz nulový, když je nulová Hodnota Konstanty:

   1: public override bool NulovyVyraz()
   2: {
   3:     return Hodnota == 0;
   4: }

Dále Proměnná. Jak už jsme řekli, proměnná nebude nulová nikdy:

   1: public override bool NulovyVyraz()
   2: {
   3:     return false;
   4: }

Teď Binární Výrazy. Začneme součtem. Kdy je součet nulový? Když platí rovnice (-A = B). To prozatím nejsme schopni vyjádřit, protože naše kalkulačka neumí počítat výsledné hodnoty. Takže se spokojíme s implementací, že Součet je nulový, když jsou nulové oba dva Výrazy A i B.

   1: public override bool NulovyVyraz()
   2: {
   3:     return A.NulovyVyraz() && B.NulovyVyraz();
   4: }

U Rozdílu to nadefinujeme stejně:

   1: public override bool NulovyVyraz()
   2: {
   3:     return A.NulovyVyraz() && B.NulovyVyraz();
   4: }

U Součinu to bude podobné, akorát tam bude jiný logický operátor. Stačí, když alespoň jeden výraz bude nulový a již je celý výraz nulový:

   1: public override bool NulovyVyraz()
   2: {
   3:     return A.NulovyVyraz() || B.NulovyVyraz();
   4: }

U Podílu je pak jediná možnost na nulovost: čitatel je rovný nule.

   1: public override bool NulovyVyraz()
   2: {
   3:     return A.NulovyVyraz();
   4: }

To bychom měli. Teď už jen zbývá definovat metodu pro zjednodušení, která zjistí, zda je daný výraz nulový a pokud ano, vrátí nulovou Konstantu. Kde danou metodu definujeme? Zjednodušovat budeme chtít všechny Matematické Výrazy, přestože u některých bude zjednodušení triviální (Konstanta a Proměnná). Metodu tedy definujeme v hlavní třídě Matematické Výrazy. Implementace:

   1: abstract class MatematickyVyraz
   2: {
   3:     public virtual MatematickyVyraz Zjednodus()
   4:     {
   5:         if(NulovyVyraz())
   6:             return new Konstanta();
   7:  
   8:         return Kopie();
   9:     }
  10:  
  11:     public abstract MatematickyVyraz Derivace();
  12:     public abstract MatematickyVyraz Substituce(string NazevPromenne, MatematickyVyraz Hodnota);
  13:     public abstract MatematickyVyraz Kopie();
  14:     public abstract bool NulovyVyraz();
  15: }

Tuto metodu zdědí všechny třídy, takže už teď můžeme vyzkoušet, jak naše zjednodušování funguje:

   1: static void Main(string[] args)
   2: {
   3:     Konstanta nula = new Konstanta();
   4:     Konstanta deset = new Konstanta(10);
   5:  
   6:     Promenna a = new Promenna("a");
   7:  
   8:     Soucin nulovySoucin = new Soucin(a, nula);
   9:     Soucet obycejnySoucet = new Soucet(a, deset);
  10:     Soucet nulovySoucet = new Soucet(nula, nula);
  11:     Soucet dvojitaNula = new Soucet(nulovySoucin, nulovySoucin);
  12:     Soucet hokusPokus = new Soucet(nulovySoucin, deset);
  13:  
  14:     Console.WriteLine("Před zjednodušením: {0}",
  15:         nulovySoucin.ToString());
  16:  
  17:     Console.WriteLine("Po zjednodušení: {0}", 
  18:         nulovySoucin.Zjednodus().ToString());
  19:  
  20:     Console.WriteLine("-------");
  21:  
  22:     Console.WriteLine("Před zjednodušením: {0}",
  23:         obycejnySoucet.ToString());
  24:  
  25:     Console.WriteLine("Po zjednodušení: {0}",
  26:         obycejnySoucet.Zjednodus().ToString());
  27:  
  28:     Console.WriteLine("-------");
  29:  
  30:     Console.WriteLine("Před zjednodušením: {0}",
  31:         nulovySoucet.ToString());
  32:  
  33:     Console.WriteLine("Po zjednodušení: {0}",
  34:         nulovySoucet.Zjednodus().ToString());
  35:  
  36:     Console.WriteLine("-------");
  37:  
  38:     Console.WriteLine("Před zjednodušením: {0}",
  39:         dvojitaNula.ToString());
  40:  
  41:     Console.WriteLine("Po zjednodušení: {0}",
  42:         dvojitaNula.Zjednodus().ToString());
  43:  
  44:     Console.WriteLine("-------");
  45:  
  46:     Console.WriteLine("Před zjednodušením: {0}",
  47:         hokusPokus.ToString());
  48:  
  49:     Console.WriteLine("Po zjednodušení: {0}",
  50:         hokusPokus.Zjednodus().ToString());
  51:  
  52:     Console.Read();
  53:  
  54:     /*
  55:     Výstup z programu:
  56:     
  57:     Před zjednodušením: (a * 0)
  58:     Po zjednodušení: 0
  59:     -------
  60:     Před zjednodušením: (a + 10)
  61:     Po zjednodušení: (a + 10)
  62:     -------
  63:     Před zjednodušením: (0 + 0)
  64:     Po zjednodušení: 0
  65:     -------
  66:     Před zjednodušením: ((a * 0) + (a * 0))
  67:     Po zjednodušení: 0
  68:     -------
  69:     Před zjednodušením: ((a * 0) + 10)
  70:     Po zjednodušení: ((a * 0) + 10)
  71:     */
  72: }

Vidíme, že vše hezky funguje, až na poslední příklad. Tam máme zcela zřejmý nulový výraz (a * 0), přesto zjednodušen nebyl. Chyba je v tom, že metodou Zjednoduš() neprocházíme celý strom výrazů. V Binárních výrazem je nevoláme na sloty A a B. Takže jdeme přepisovat. Zároveň můžeme metodu Zjednoduš() u sčítání implementovat tak, aby v případě, kdy je jeden z výrazů nulový, vrátila druhý výraz:

   1: public override MatematickyVyraz Zjednodus()
   2: {
   3:     MatematickyVyraz v1 = A.Zjednodus();
   4:     MatematickyVyraz v2 = B.Zjednodus();
   5:  
   6:     if(v1.NulovyVyraz())
   7:         return v2;
   8:  
   9:     if(v2.NulovyVyraz())
  10:         return v1;
  11:  
  12:     return new Soucet(v1, v2);
  13: }

Všimněte si, že nejdřív jako první zjednodušíme A a B a až poté zjišťujeme, jestli je tento výraz nulový. Kdybychom toto neudělali, nemuseli bychom dostat maximálně možný zjednodušený výraz.

Podobnou úpravu uděláme u Rozdílu. Jen pozor na znaménka u Rozdílu – v případě, že je A nulové, nemůžeme vrátit B, protože by se ztratilo znaménko. Museli bychom vrátit –B, což vlastně neumíme udělat jinak než Rozdílem (případě ještě složitěji Součinem):

   1: public override MatematickyVyraz Zjednodus()
   2: {
   3:     MatematickyVyraz v1 = A.Zjednodus();
   4:     MatematickyVyraz v2 = B.Zjednodus();
   5:  
   6:     if(v2.NulovyVyraz())
   7:         return v1;
   8:  
   9:     return new Rozdil(v1, v2);
  10: }

Implementace u součinu:

   1: public override MatematickyVyraz Zjednodus()
   2: {
   3:     MatematickyVyraz v1 = A.Zjednodus();
   4:     MatematickyVyraz v2 = B.Zjednodus();
   5:  
   6:     if(v1.NulovyVyraz() || v2.NulovyVyraz())
   7:         return new Konstanta();
   8:  
   9:     return Kopie();
  10: }

A u podílu:

   1: public override MatematickyVyraz Zjednodus()
   2: {
   3:     MatematickyVyraz v1 = A.Zjednodus();
   4:     MatematickyVyraz v2 = B.Zjednodus();
   5:  
   6:     if(v1.NulovyVyraz())
   7:         return new Konstanta();
   8:  
   9:     if(v2.NulovyVyraz())
  10:         throw new Exception("Nemůžeme dělit nulou!");
  11:  
  12:     return new Podil(v1, v2);
  13: }

Zde bychom měli ošetřovat, zda není zjednodušený výraz nulový, abychom po zjednodušení nedostali nesmysl. Předchozí hokusPokus příklad se již zjednoduší správně:

   1: static void Main(string[] args)
   2: {
   3:     Konstanta nula = new Konstanta();
   4:     Konstanta deset = new Konstanta(10);
   5:  
   6:     Promenna a = new Promenna("a");
   7:  
   8:     Soucin nulovySoucin = new Soucin(a, nula);
   9:     Soucet hokusPokus = new Soucet(nulovySoucin, deset);
  10:  
  11:     Console.WriteLine("Před zjednodušením: {0}",
  12:         hokusPokus.ToString());
  13:  
  14:     Console.WriteLine("Po zjednodušení: {0}",
  15:         hokusPokus.Zjednodus().ToString());
  16:  
  17:     Console.Read();
  18:  
  19:     /*
  20:     Výstup z programu:
  21:     
  22:     Před zjednodušením: ((a * 0) + 10)
  23:     Po zjednodušení: 10
  24:     */
  25: }