addendum

Datastructuren aanvulling op opdracht 2
2014
Over expressies en expressiebomen
Deadline
De deadline is verplaatst naar maandag 27 oktober 11:00 ('s ochtends).
Extra uitleg
Dit document beschrijft een aantal zaken, die in de opdracht niet voor iedereen duidelijk zijn. En daarbij tips om het
beschreven probleem aan te pakken. Deze aanpak is niet verplicht, maar zijn bedoeld als idee voor diegenen die er zelf
niet uitkomen.
Wiskundige formules v.s. expressies bestaande uit operatoren en operanden
Bij wiskundige formules zijn niet alle operatoren expliciet in de formule aanwezig, maar blijken ze
uit de volgorde van de operanden of uit het gebruik van superscript. Zo betekent 2a hetzelfde als
2 * a en x3 het zelfde als x tot de macht 3 en zo betekent (fg)' de afgeleide van (f * g ). Bij
het opstellen van expressies voor een expressieboom is het handig om de operatoren expliciet te
maken. Dus (2a + 6)2 wordt b.v. ((2 * a) + 6) ^ 2 als we ^ als symbool gebruiken voor
machtsverheffen.
Poolse notatie
Om een expressie in poolse notatie te kunnen parsen zodat je er een expressieboom van kan
maken, is het handig om operatoren en operanden telkens te scheiden door spaties. (2a + 6)2
wordt dan ^ + * 2 a 6 2.
Unaire operatoren
Wanneer je unaire operatoren wil gebruiken, is het goed om je te realiseren dat de inorderwandeling van de boom de infix notatie oplevert. Dat is de notatie zoals wij het meest gewend zijn.
Een gewone inorder-wandeling plaatst geen haakjes die de rekenvolgorde afdwingen. Hiervoor kan
je je expressieboom een eigen inorder-wandeling geven (overriding).
Sommige unaire operatoren schrijven wij nl vóór de operand zoals –x, ln a en sin(x). Andere
unaire operatoren schrijven we echter achter de operand zoals 10! (10 faculteit). In de poolse
notatie schrijf je altijd eerst de operator en dan de operand. Dus – x, ln a, sin x en ! 10. In je
expressiebomen gebruik je één van de twee kinderen voor de operand. Doe dit zo dat je inorder
wandeling de juiste notatie oplevert. Bij unaire operaties, die wij normaal voor de operand zetten
komt de operand dan in het linker kind en bij unaire operatoren die wij achter de operand plaatsen
komt de operand in het rechter kind. 10log(sin(x) + ln(7!)) wordt in poolse notatie
log 10 + sin x ln ! 7
Diferentiëren
De differentiatie regels zoals gegeven in de opdracht (rule 1 t/m 4) staan beschreven als wiskundige formules. Wanneer
je deze wil toepasen is het handig om deze eerst uit te schrijven als expressie en er een expressie boom voor te tekenen.
Dan blijkt dat je i.p.v. met (axn)'=naxn-1 kan werken met (xn)'=nxn-1 omdat vermenigvuldigen met a al door toepassing
van de eerste regel kan worden opgelost.
Ter geruststelling
Het is niet de bedoeling, dat je programma alle wiskundige formules perfect kan differentiëren. Wel alle polynomen en
logaritmen en enkele goniometrische functies (sin, cos).
De uitdaging zoals beschreven in de opdracht geldt voor studenten die een goed willen halen.
Vereenvoudigen (simplify) hoeft niet tot in de perfectie. Maak het niet te ingewikkeld. Maar doe wel alles wat je direct
kan zien aan een operand en zijn twee kinderen. Denk bijvoorbeeld aan:


Operanden zijn beide bladeren:
 3+6=9
 4 * 10 = 40
 x–x=0
 x/x=1
Operand = 0 of 1
 0 * <subtree> = 0
 1 * <subtree> = <subtree>
 <subtree> ^ 0 = 1
 <subtree> ^ 1 = <subtree>
Recursief toepassen van deze regels vereenvoudigt je boom.
Evaluate vult alleen waarden in voor x. Hierdoor verenvoudigt je expressieboom sterk en blijft er een expressie over
zonder x en als er geen andere symbolen/variabelen in de expressie zaten komt er een waarde uit. Evaluate vervangt
dus in je expresieboom alle x-en door de opgegeven waarde en roept daarna simplify aan.

Download Report