bild
Skolan för
datavetenskap
och kommunikation
KTH / CSC / Kurser / DD1339 / inda12 / Vårens uppgifter / Uppgift 3

Uppgift 3 våren 2013

Uppgiften ska lämnas till din övningsledare på övningen den 1/2.

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.

Läs om reguljära uttryck i texten Java Regex Tutorial av Lars Vogel. Avsnitt 1-4 har du stor nytta av när du löser veckans uppgift.

Skriftlig uppgift

Lämna in en lösning till uppgift 10.71 (uppl 4: 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() 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.

Evaluering av aritmetiska postfixuttryck

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
0 + 1                          0 1 +
(2 + -3) * 4                   2 -3 + 4 *
(5 - 6) * (7 + 8)              5 6 - 7 8 + *
((9 + 10) * 11) - 12) / 13     9 10 + 11 * 12 - 13 /
14 * (15 - (16 + 17))          14 15 16 17 + - *

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 stacken du implenterade i föregående uppgift. Utgå från kodskelettet Postfix.java. De två hjälpmetoderna isOperator och isInteger ska du implementera med hjälp av reguljära uttryck. Kodskelettet innehåller testkod och din implementation måste klara samtliga testfall.

Copyright © Sidansvarig: Stefan Nilsson <snilsson@nada.kth.se>
Uppdaterad 2012-12-14