Uppgift 3 våren 2010

Uppgiften ska lämnas till din övningsledare på övningen den 12/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.

Skriftlig uppgift

Lämna in en lösning till uppgift 10.62 i programmeringsboken.

Stack

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. Testa alla metoder noggrannt. Testkoden ska också lämnas in.

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. Glöm inte testkoden.