Rpn Kalkulator

Kalkulator-øving Reverse Polish Notation-basert kalkulator

1

Reverse Polish Notation (RPN) • RPN er en måte å gi inn operander og operatorer til en kalkulator, med noen fordeler – en trenger ikke parenteser – den er fleksibel i bruk – den er enkel å implementere

• Grunnidé – operander gis inn først og lagres på en såkalt stack (norsk: stabel) – når en operator gis inn, tas operandene (bort) fra toppen av stacken, beregningen utføres og resultatet legges (tilbake) på toppen av stacken 2

Input Stack (toppen til høyre) 1.0 {1.0} 2.0

{1.0, 2.0}

+

{3.0}

Eksempler 1 + (2 * 3)

3

(1 + 2) * 3

1.0 {1.0}

1.0 {1.0}

2.0 {1.0, 2.0}

2.0 {1.0, 2.0}

3.0 {1.0, 2.0, 3.0}

+

*

{1.0, 6.0}

3.0 {3.0, 3.0}

+

{7.0}

*

{3.0}

{9.0}

Operasjoner • Matematiske operatorer – Unære operatorer eller funksjoner, som kvadratrot, sinus og cosinus, tar bort én operand og legger én verdi tilbake på toppen – Binære operatorer, som +, -, *, /, tar bort to operander og legger én verdi tilbake på toppen – Konstanter, som pi og e, fungerer som funksjoner uten argumenter, dvs. de legges bare på toppen

• Spesielle operasjoner – dup: dupliserer det øverste elementet – pop: fjerner det øverste elementet – swap: bytter om de to øverste elementene 4

1.0

{1.0}

2.0

{1.0, 2.0}

dup

{1.0, 2.0, 2.0}

pop

{1.0, 2.0}

swap

{2.0, 1.0}

Øvingskonstruksjon • Koden deles i to klasser: – ArgumentStack: administrerer stacken med verdier • en global variabel som inneholder double-verdiene • noen globale metoder/funksjoner, som håndterer stacken: push, peek, og pop • print-metoden skriver ut stackinnholdet

– Calc: håndterer brukerinput, implementerer operasjoner og kaller ArgumentStack-metoder underveis • hjelpemetoder: performOperation, handleInput og splitAndHandleInput • hovedprogram: main-metoden leser brukerinput, utfører operasjonene og print’er ut stack-innholdet

5

ArgumentStack • ArgumentStack: håndterer stacken med verdier – en global variabel inneholder double-verdiene • static double[] arguments

– en rekke globale metoder/funksjoner, som endrer stacken • push – legger double-argumentet på toppen av stacken • peek – returnerer øverste verdi på stacken, uten å endre den • pop – fjerner én verdi fra stacken og returnerer denne

– hjelpemetode for å skrive ut: print(prefix, separator, suffix)

• Spørsmål: – Hvordan implementerer vi stack-operasjoner, når tabeller kan ikke kan endre lengde? – Tenk notatark med en variabel som peker på en tabellen: Hva skjer når verdier push’es og pop’es?

6

ArgumentStack-metoder • push(double v) – legger v på toppen av stacken • peek(double d) – returnerer den øverste verdien eller d, dersom stacken er tom • pop(double d) – fjerner verdien på toppen av stacken og returnerer den. Dersom stacken er tom returneres d. • print(prefix, separator, suffix) – skriver først ut prefix, deretter alle stackverdiene fra bunn til topp adskilt med separator, og så suffix til slutt. All utskrift skjer til System.out. 7

Calc-metoder •

•

•

•

8

performOperation(char op) - utfører operasjonen for op. Lovlige opverdier er ’+’, ’-’, ’*’, ’/’, ’,’ (dup), ’.’ (pop) og ’~’ (swap). Metoden må kalle nødvendige metoder i ArgumentStack-klassen. handleInput(String input) – Dersom første tegn i input er et siffer, så tolkes input som en verdi som skal push’es på stacken. Alternativt er det en operasjon som skal utføres. splitAndHandleInput(String input) – input er en sekvens med verdier og operasjoner adskilt med mellomrom, som håndteres fra venstre mot høyre. hovedprogrammet skal lese linjer fra System.in og avslutte når en tom linje leses. Hver linje håndteres med splitAndHandleInput og stacken skrives så ut på passende format. Som en ekstraoppgave kan dere også håndtere args-elementene vha. splitAndHandleInput.

Støtte for Turtle Graphics • Turtle Graphics-kommandoer kan ses på som operasjoner som fjerner operander, uten å legge noe resultat tilbake. • Følgende operasjoner skal støttes – – – – – –

‘f’ (forward): fjerner en operand n og flytter skilpadda n steg fremover ‘t’ (turn): fjerner en operand n og dreier skilpadda n grader ‘u’ (up): løfter blyanten ‘d’ (up): senker blyanten ‘h’ (home): nullstiller posisjon og retning ‘c’ (color): fjerner 4 operander r(ød), g(rønn), b(lå) og a(lpha/transparens) og setter fargen til en farge sammensatt av disse verdiene – ‘w’ (width): fjerner en operand w og setter bredden til denne verdien

• Eksempel: – 20 f 90 t 20 f 90 t 20 f 90 t 20 f – tegner en firkant og resulterer i en tom stack 9

Hendige metoder 1 •

System.arraycopy(src, srcstart, dest, deststart, len) – kopierer len elementer fra src til dest. Uthentingen av elementer starter på indeks srcstart (i src) og de legges fra deststart (i dest) og utover. –

•

Integer.valueOf (s)/ Double.valueOf (s) – gjør om s til en int/double – – –

•

Character.toLowerCase(’H’) => ’h’ Character.toUpperCase(’h’) => ’H’ Character.toLowerCase(’8’) => ’8’

String.toLowerCase()/toUpperCase() – gjør om til små/store bokstaver – –

10

Character.isDigit(’8’) => true Character.isDigit(’H’) => false

Character.toLowerCase(c)/toUpperCase(c) – gjør om til liten/stor bokstav – – –

•

Integer.valueOf(”1”) => 1 Double.valueOf(”1.0”) => 1.0 Double.valueOf(”2”) => 2.0

Character.isDigit(c) – returnerer true hvis c er et siffer (0-9), eller false om c ikke er et siffer – –

•

int[] enToTre = {1, 2, 3}; int[] treFireFem = {3, 4, 5}; System.arraycopy(enToTre, 1, treFireFem, 0, 2); // nå er treFireFem lik {2, 3, 5}

”Hallvard”.toLowerCase(”Hallvard”) => ”hallvard” ”Hallvard”.toUpperCase(”Hallvard”) => ”Hallvard”

Hendige metoder 2 • String.length() – returnerer antall tegn i String’en – ”Hallvard”.length() => 8

• String.charAt(pos) – returnerer String’en sitt tegn nr. pos. – ”Hallvard”.charAt(7) => ’d’

• String.indexOf(c)/lastIndexOf(c) – returnerer posisjonen til første/siste forekomst av char’en c – ”Hallvard”.indexOf(’l’) => 2 – ”Hallvard”.lastIndexOf(’l’) => 3

• String.indexOf(s)/lastIndexOf(s) – returnerer posisjonen til første/siste forekomst av delString’en s. – ”Hallvard”.indexOf(”al”) => 1 – ”Hallvard”.lastIndexOf(”lv”) => 3 11

Hendige metoder 3 • String.substring(start) – returnerer del-String’en med tegnene fra og med start og til og med siste tegn – ”Hallvard”.substring(4) => ”vard”

• String.substring(start, slutt) – returnerer del-String’en med tegnene fra og med start og til (men ikke med) slutt – ”Hallvard”.substring(2, 4) => ”ll”

• String.trim() – returnerer en String med de samme tegnene som originalen, bortsett fra at alle mellomrom foran og bak er fjernet – ” Hallvard ”.trim() => ”Hallvard”

• String.split(sep) – tenk på String’en som bestående av del-String’er adskilt med sep. Metoden returnerer delString’ene i en String-tabell, altså uten sep’ene. – ”Hallvard:foreleser:TDT4100”.split(”:”) => {”Hallvard”, ”foreleser”, ”TDT4100”}

12

Scanner-objekter • • • • •

13

java.util.Scanner Scanner = new Scanner(System.in) – gir deg et objekt som hjelper deg å lese input fra brukeren Scanner.hasNextLine() – gir true, dersom det er mer input tilgjengelig Scanner.nextLine() – gir deg neste input-linje Typisk løkke for innlesing av tekstlinjer: // lag en Scanner som leser fra konsollet java.util.Scanner sc = new java.util.Scanner(System.in); while (sc.hasNextLine ()) { // les neste linje og fjern blanke tegn først og sist String s = sc.nextLine().trim(); // avslutt dersom linja er tom if (s.length() == 0) { break; } }