INDA - Övning 3 våren 2005


Uppgiften ska lämnas till din övningsledare på övningen i vecka 5. 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 9 i programmeringsboken.


Skriftlig uppgift
Lämna in lösningar till uppgift 9.12-9.17 i programmeringsboken.

En stack är en abstrakt datatyp (på Javaspråk: en "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.
Implementera denna abstrakta datatyp i Java. Du kan med fördel använda den enkellänkade listan från övning 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.
Följande händer alltså när uttrycket "1 2 + 3 *" beräknas.
1: push(1)
2: push(2)
+: push(pop() + pop())
3: push(3)
*: push(pop() * pop())
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.3 i programmeringsboken) och stacken du implenterade i föregående uppgift. Testa din metod noggrannt.


Stefan Nilsson
2005-01-21