Algoritmer och datastrukturer TF3 Sy
samt
Algoritmer och datastrukturer med objektorienterad programmering
Inlämningsuppgift nummer 2
Matte ?
Skriv ett program som kan hantera uttryck uppbyggda av följande delar:
- reella tal
- variabler, som har namn
- de binära operatorerna +, - och *, samt den
unära operatorn -
- sin x och cos x
Programmet ska kunna hantera uttryckt på följande sätt:
- uttrycket ska kunna skrivas ut, gärna frikostigt parentetiserat. Det
blir säkert enklare att skriva (3 + (5 * 8)) än 3 + 5 * 8.
- uttryck som inte innehåller variabler ska kunna beräknas. Programmet
behöver inte kunna kontrollera om ett uttryck innehåller variabler
eller inte. Det behöver inte heller reagera ordnat på ett försök
att utvärdera uttryck med variabler.
- uttrycket ska kunna deriveras. Det deriverade uttrycket behöver dock
inte kunna förenklas
Inmatningen av uttrycket kan få vara mycket "ful", du behöver inte
ordna en inmatning som gör en meningsfylld omformning från det
inmatade uttrycket till en internrepresentation.
Det är till och med acceptabelt med ett huvudprogram som inte matar in
värden, utan bygger ett antal uttryck från data som finns i programmet.
Om denna lösning används ska programmet dock ha många relevanta
testexempel.
Anvisningar
Avbilda uttrycken som binära träd. Härled uttryck (bestående av objekt
ur olika klasser) från klassen
T_n. Det står dig fritt att göra små modifieringar
i klassen.
Din lösning ska på ett relevant sätt använda virtuella funktioner.
Ledning
Följande huvudprogram kan fungera som ide hur ett huvudprogram kan se
ut. Ditt program ska provas med fler exempel, än vad som görs här.
<![CDATA[
main() {
T_n* n = new Plus(new Number(5), new Number(7));
cout << n -> calc();
T_n* m = new Plus(new Var('x'), n);
m -> derive('x') -> print();
cout << endl;
m -> print();
cout << endl;
T_n* k = new Plus(new Mul(new Var('x'),
new Sin(new Var('x'))),
m);
T_n* l = k -> derive('x');
l -> print();
cout << endl;
}
]]>
Använd klassen T_n som
basklass.
Skapa nya klasser för operatorer, funktioner, variabler etc!
Inför virtuella funktioner för att derivera, beräkna och
skriva ut. Tänk på att namnen på de virtuella funktionerna
måste vara deklarerade i basklassen (läs Lippman!).
Skriv rekursiva funktioner, uppgiften blir oerhört mycket knepigare
annars.
Smidigast blir förmodligen att använda pekare till noder i ganska
stor omfattning.
En lämplig arbetsgång kan vara som följer:
- Tänk noggrant igenom klasshierarkier etc
- Skapa en ny klass, t ex Number(argument). Förse
klassen med en
virtuell funktion void print().
- Testa
- Skapa Operator(argument) eller Plus(argument)
beroende på vilken design du väljer, och förse den på samma
sätt med en virtuell funktion void print().
- Testa
- Lägg till ytterligare klasser, en i taget och testa efter varje klass
och metod du lagt till. Använd kommentartecknet flitigt i
huvudprogrammet för att kommentera bort de delar av programmen som för
tillfället inte ingår i din testsekvens, men som kan vara bra att ha
kvar, för att kunna testa igen, efter eventuella ändringar.
- Lägg till utvärdering, metodiskt i klass efter klass. Testa flitigt.
- Lägg till derivering på samma sätt. Ledning: Derivering är,
redan från gymnasiet rekursivt definierad. Skriv upp
deriveringsreglerna
på ett papper och "översätt" dem sedan till C++.
Redovisning
Redovisningen består av
- Ifylld försättssida
- lämpligt kommenterad programlistning
- en kortfattad beskrivning av valda algoritmer och datastrukturer
- ett körexempel, möjligtvis avskrivet
- uppgift om var den exekverbara filen finns tillgänglig för läsning. Se till
att ge läsrättigheter åt gruppen övriga.
Uppgiftslösningen ska i sin helhet spegla en god programmeringssed för
C++ och tillämpa klassbegreppet på ett meningsfyllt sätt.
Uppgiften får lösas individuellt eller i grupper om två. Om två
personer arbetar tillsammans, ska båda aktivt delta i hela
utvecklingsarbetet. En ren arbetsdelning, exempelvis programmering mot
dokumentation är inte tillåtet.
För handledning på denna uppgift hänvisas till Datortekniks
jourhavandec handledare eller Fredriks
handledningstider
Uppgifterna lämnas in enligt anvisningarna i kursplanen, senast den 2 mars.
Fredrik Larsson
<fredrikl@DoCS.UU.SE>
Anders Berglund
<Anders.Berglund@DoCS.UU.SE>
Last modified: Tue Feb 17 21:38:55 MET 1998