|
INDA - Uppgift 3 våren 2007
Uppgiften ska lämnas till din övningsledare på övningen den 8/2.
Glöm inte försättsbladet (pdf) och att
alla papper ska häftas samman eller lämnas in i en plastficka.
För godkänt måste du ha gjort samtliga deluppgifter.
Det är tillåtet att göra enstaka fel och misstag men det
är viktigt att du försöker lösa samtliga uppgifter. Om du kör fast med
någon uppgift så finns det som vanligt hjälp att få på labbarna.
Hemuppgift
Studera kapitel 10 i programmeringsboken och se till att du förstår
hur abstrakta klasser och gränssnitt (interface) fungerar i Java.
Studera också avsnitt 2.1 i algoritmboken.
Skriftlig uppgift
Lämna in en lösning till uppgift 10.57 i programmeringsboken.
En stack är en abstrakt datatyp (på Javaspråk: "collection")
som stödjer följande metoder:
- push(o) Sätter in elementet o överst i stacken.
- pop() Tar bort och returnerar det översta elementet i
stacken, dvs det senast insatta elementet som fortfarande
finns kvar i stacken. Ett fel inträffar om stacken är tom.
- top() Returnerar det översta elementet i stacken utan att ta bort det.
Ett fel inträffar om stacken är tom.
- size() Returnerar antalet element i stacken.
- isEmpty() Returnerar en boolean som indikerar om stacken är tom.
Beskriv denna abstrakta datatyp i Java med hjälp av ett
gränssnitt (interface) med namnet Stack. Glöm inte dokumentationen -
den är extra viktig i ett gränssnitt där det inte finns någon programkod.
Skriv sedan en klass som implementerar detta gränssnitt. Du kan
med fördel använda den enkellänkade listan från uppgift 2.
Du bestämmer själv hur felhantering ska ske. Se till att samtliga
metoder har konstant tidskomplexitet i värstafall.
En stack är en mycket användbar abstrakt datatyp som bland
annat används för att implementera metodanrop i programspråk.
Veckans uppgift är dock inte att implementera ett helt programspråk.
Du ska skriva ett program som kan beräkna aritmetiska uttryck i
postfixnotation. Det är ett enkelt sätt att skriva aritmetiska uttryck
som inte kräver några parenteser och inga prioritetsregler. Här
kommer några exempel på aritmetiska uttryck skrivna i vanlig
infixnotation respektive postfixnotation.
Infix Postfix
1 + 2 1 2 +
(1 + 2) * 3 1 2 + 3 *
(1 - 2) * (3 + 4) 1 2 - 3 4 + *
((1 + 2) * 3) - 4) / 5 1 2 + 3 * 4 - 5 /
2 * (3 - (4 + 5)) 2 3 4 5 + - *
Du ser att operatorn alltid står direkt efter sina operander.
Postfixuttryck är enkla att beräkna med hjälp av en stack.
Algoritmen kan kort beskrivas så här:
- Gå igenom postfixuttrycket från vänster till höger.
- Så snart du ser en operand, pusha den på stacken.
- Så snart du ser en operator, poppa dess båda operander från
stacken och pusha sedan resultatet av beräkningen på stacken.
Skriv en metod i Java som tar ett postfixuttryck representerat
som en sträng av heltalsoperander och aritmetiska operatorer
(+, -, *, /) som indata och returnerar uttryckets
värde som ett heltal. Använd omslagsklassen Integer
(avsnitt 8.9 i programmeringsboken) och stacken du
implenterade i föregående uppgift. Testa din metod noggrannt.
Testkoden ska också lämnas in.
Stefan Nilsson
2007-01-15
|