# Naloga2 – Algoritmi nad zbirkami V tej nalogi najprej dodamo zbirke s kazalci, nato preproste odločitvene in zančne ukaze, na koncu pa nad zbirkami, ki jih že imamo, uresničimo nekaj klasičnih algoritmov. ## Zbirke s kazalci Doslej so bile vse zbirke izvedene s poljem. Dodajte še tri izvedbe s kazalci (povezanim seznamom): - sklad: razred `izvedbe.LinkedStack`, ki uresničuje vmesnik `Stack`, - vrsta (FIFO): razred `izvedbe.LinkedQueue`, ki uresničuje vmesnik `Queue`, - dvostrana vrsta: razred `izvedbe.LinkedDeque`, ki uresničuje vmesnik `Deque` (izvedite jo z **dvojno** povezanim seznamom). Skladkulator bo tako uporabljal vseh šest izvedb zbirk: tri s poljem (`ArrayStack`, `ArrayQueue`, `ArrayDeque`) in tri s kazalci (`LinkedStack`, `LinkedQueue`, `LinkedDeque`). ## Ustvarjanje zbirk Dodajte še ukaze za **ustvarjanje zbirk** s kazalci. Delujejo enako kot `as`, `aq` in `ad`: vzamejo ime z glavnega sklada, ustvarijo prazno zbirko ustreznega tipa, jo vstavijo v slovar in ime porinejo nazaj na sklad: - *p* `ls` → *p* : ustvari sklad s kazalci (`LinkedStack`) z imenom *p* - *p* `lq` → *p* : ustvari vrsto s kazalci (`LinkedQueue`) z imenom *p* - *p* `ld` → *p* : ustvari dvostrano vrsto s kazalci (`LinkedDeque`) z imenom *p* > Če zbirka z imenom *p* v slovarju že obstaja, jo nadomesti nova prazna zbirka (morda drugega tipa). Vsi ukazi nad zbirkami iz Naloga1 delujejo enako, ne glede na izvedbo: ``` seznam ld { a b c } seznam count echo nl /* »3« */ seznam dumpc /* »a b c« */ ``` ## Pogojna stavka Podprli boste dva pogojna stavka. Prvi je `iftrue`, ki prejme pogoj in le en ukaz: - *c* *b* `iftrue` : če je *c* različen od 0, izvede ukaz *b*, sicer ne naredi nič Drugi pa je `if`, ki glede na resničnost podanega pogoja izvede eno izmed vej: - *c* *b* *a* `if` : če je *c* različen od 0, izvede ukaz *b*, sicer ukaz *a* Ukaz *b* (oz. *a*) je lahko vgrajen ukaz, ime funkcije ali pa kar niz, ki se potisne na sklad. Izvedemo ga tako, kot da bi ga prebrali z vhoda (torej enako kot en simbol iz programa). Oba stavka podpirata izvedbo le enega ukaza, zato je včasih treba definirati pomožno funkcijo. Oglejmo si nekaj primerov: ``` 'Hej 1 'echo iftrue nl /* »Hej« */ 'Hej 0 'echo iftrue nl pop /* (samo prazna vrstica), echo se ni izvedel; pop odstrani Hej */ iffalse fun { swap not swap iftrue } 'Hej 1 'echo iffalse nl pop /* (samo prazna vrstica), Hej odstrani pop */ 'Hej 0 'echo iffalse nl /* »Hej« */ neg fun { 0 swap - } abs fun { dup 0 <= 'neg iftrue } -42 abs echo nl /* »42« */ 1 'Hokus 'pokus if /* -> Hokus */ 5 6 == 'Hokus 'pokus if /* -> Hokus pokus */ ``` ## Zanka Naslednja je preprosta zanka s fiksnim številom ponovitev: - *n* *b* `loop` : *n*-krat izvede ukaz *b* Primeri: ``` /* Vgrajeni ukazi kot telo zanke */ 'a 'b 'c 'd 3 'strcat loop echo nl /* »abcd«, trikrat strcat zlepi štiri nize */ 7 5 'dup loop dump /* »7 7 7 7 7 7« */ /* Funkcija kot telo zanke */ ex fun { 'x echo } 3 'ex loop nl /* »xxx« */ /* Funkcija, ki spreminja vrednost na skladu */ podvoji fun { 2 * } 1 10 'podvoji loop echo nl /* »1024« */ ``` ## Rekurzija Funkcija lahko v svojem telesu kliče samo sebe po imenu – rekurzija deluje, saj se ime poišče šele ob dejanskem klicu, ne ob definiciji. Skupaj z `iftrue` tako dobimo rekurzivne funkcije, ki se končajo. Primer – odštevanje do 0: ``` odstevaj fun { dup echo spc 1 - dup 'odstevaj iftrue } 5 odstevaj nl /* »5 4 3 2 1«, na skladu ostane 0 */ ``` ## Nizi kot zbirke Nize lahko pretvarjamo v zbirke znakov in nazaj z ukazoma: - *s* *p* `unpack` : niz *s* razbije na posamezne znake in jih enega za drugim zapiše v zbirko *p* - *p* `pack` → *s* : izprazni zbirko *p*, element za elementom (`pop` oz. `dequeue`, glede na tip zbirke), in jih zloži v en niz *s*, ki ga porine na glavni sklad Primeri: ``` sklad as { a b c } sklad pack echo nl /* »cba«, sklad obrne vrstni red */ vrsta aq { a b c } vrsta pack echo nl /* »abc«, vrsta ohrani vrstni red */ 'hello sklad as unpack sklad dumpc /* »h e l l o« */ 'hello sklad as unpack sklad pack echo nl /* »olleh«, sklad obrne vrstni red */ 'hello vrsta aq unpack vrsta pack echo nl /* »hello«, vrsta ohrani vrstni red */ ``` ## Filtriranje Naslednji ukaz elemente ene zbirke prenese v drugo in pri tem izpusti vse, ki so enaki podanemu: - *x* *p* *q* `filter` : elemente zbirke *p* jemlje po vrsti (`pop` oz. `dequeue`, glede na tip zbirke) in jih dodaja na konec zbirke *q* (`push` oz. `enqueue`), razen tistih, ki so enaki *x* – ti se odstranijo in izgubijo Po filtriranju je zbirka *p* prazna, v zbirki *q* pa ostanejo tudi njeni morebitni prejšnji elementi. Predpostavimo, da sta zbirki *p* in *q* različni. Če je *p* vrsta, se vrstni red elementov ohrani, če je *p* sklad, pa se jemlje z vrha, zato se v *q* dodajo v obratnem vrstnem redu. Primeri: ``` vhod aq { a x b x c } izhod aq { } 'x vhod izhod filter izhod dumpc /* »a b c« */ vhod count echo nl /* »0«, izvorna vrsta je prazna */ sklad as { 1 2 3 4 2 } obrat aq { } '2 sklad obrat filter obrat dumpc /* »4 3 1«, sklad se jemlje z vrha */ 'H_e_l_l_o dv1 ad unpack dv2 ad { } _ dv1 dv2 filter dv2 pack echo nl /* »Hello«, podčrtaji so izločeni */ ``` ## Palindromi Zaporedje je palindrom, če se bere enako od začetka proti koncu kot od konca proti začetku. V palindromu se morajo vsi pari elementov z začetka in konca (prvi-zadnji, drugi-predzadnji, ...) ujemati. Naslednji ukaz izračuna število neujemajočih se parov v dani dvostrani vrsti (ustvarjeni z `ad` ali `ld`): - *p* `palindrom` → *r* : vrne število neujemajočih se parov v dvostrani vrsti *p* Pri izvedbi tega algoritma lahko na dvostrani vrsti uporabljate le operaciji `dequeue()` in `dequeueBack()` (ter morda še `count()`). Vrsta se pri tem izprazni. Dostop po indeksu (`get()`, `set()`) ni dovoljen. Bolj podrobno pa o algoritmu razmislite sami. Primeri: ``` 'abcba dv ad unpack dv palindrom echo nl /* »0«, "abcba" je palindrom */ 'abcd dv ad unpack dv palindrom echo nl /* »2«, oba para (a,d) in (b,c) */ 'abbc dv ad unpack dv palindrom echo nl /* »1«, samo par (a,c) */ ``` ## Uravnoteženi oklepajski izrazi Zaporedje oklepajev (`(`, `)`, `[`, `]`, `{`, `}`) je uravnoteženo, če se vsak zaklepaj ujema z najbolj nedavnim še neujetim predklepajem in na koncu ne ostane noben neujet predklepaj. Naslednji ukaz prešteje napačna ujemanja oklepajev v podani zbirki: - *p* `balanced` → *r* : prešteje napačna ujemanja oklepajev v zaporedju *p* Oklepaje iz zbirke *p* algoritem jemlje zaporedoma, glede na tip zbirke (`pop()` oz. `dequeue()`), zato se *p* pri tem izprazni. Pri izvedbi uporabite pomožni sklad, ki ga ustvarite sami, in nad njim le operaciji `push()` in `pop()`. Dostop po indeksu (`get`, `set`) ni dovoljen. Razmislite, kdaj oklepaj potisnete na sklad in kdaj sprožite preverjanje ujemanja. Na koncu ne pozabite prišteti še morebitnih neujetih predklepajev. Bolj podrobno pa o algoritmu razmislite sami. Primeri: ``` '([]) izraz aq unpack izraz balanced echo nl /* »0«, "([])" je uravnoteženo */ '([)] izraz aq unpack izraz balanced echo nl /* »2«, ')' in ']' se ne ujemata s pravo vrsto oklepaja */ '(]([) izraz aq unpack izraz balanced echo nl /* »3«, ']' in ')' sta napačna, '(' na koncu ostane neujet */ '{[()]} izraz aq unpack izraz balanced echo nl /* »0«, vse tri vrste oklepajev so pravilno ugnezdene */ '{(}) izraz aq unpack izraz balanced echo nl /* »2«, '}' in ')' se ne ujemata s pravo vrsto oklepaja */ ```