INF2220 ukeoppgaver uke 4 (24/9-28/9) ===================================== OPPGAVE 1: ---------- Tegn det r?d-svarte treet som blir resultatet av f?lgende innsettingsekvens: 3, 1, 4, 6, 9, 2, 5, 7 OPPGAVE 2: ---------- P? forelesningen 11/9 s? vi p? en implementasjon av iteratorklasser for infiks og prefiks traversering. Skriv en tilsvarende klasse for postfiks traversering. OPPGAVE 3 --------- Vi skal skrive et program som sjekker visse aspekter ved Java-programmer, nemlig: - at {}-par kommer riktig - at vanlige parentes-par kommer riktig - at det ikke kommer semikolon eller {} inne i parenteser Vi skal ikke bry oss med detaljene i lesingen av programmet, men kan f.eks. anta at vi har en metode String nesteSymb() som leverer neste interessante symbol i programmet, og hvor "EOF" angir programslutt. Man kan bruke en (String) stakk for ? sjekke dette. Beskriv et sett av stakk-operasjoner som er tilstrekkelig for denne sjekkingen, og skriv hovedprogrammet ut fra dette. OPPGAVE 4 --------- Regnestykket 1.23 + ( (4.56 * 7.89) / (3.3 + 4.44) ) kan skrives p? postfiks form uten bruk av parenteser slik: 1.23 4.56 7.89 * 3.33 4.44 + / + N?r uttrykk p? postfiks form skal beregnes er det naturlig ? bruke en stakk av tall. M?let er da at svaret st?r alene igjen p? stakken n?r beregningen er ferdig. a) Forklar f?rst med ord hva slags stakk-operasjoner som m? gj?res n?r man leser inn et postfiks uttrykk sekvensielt, og f?r inn henholdsvis et tall eller en av de fire operasjonene. Tenk deg ogs? en operasjon som henter ut svaret til slutt, slik at det blir i alt seks operasjoner. b) Anta at man har en standard-pakke for stakker av reelle tall, og bruk denne til ? implementere de seks operasjonene. c) Lag en direkte implementasjon av de seks operasjonene som bruker en array. Legg ogs? inn i denne modulen mekanismer som tester om uttrykket er et korrekt uttrykk. NYTTIG EKSTRAOPPGAVE ------------------- Implementer zig- og zig-zag-rotasjon for bin?re s?ketr?r. Hvilke parametre vil du overf?re til metoden?