Algoritmi in podatkovne strukture 1

V programskem jeziku java napišite programabilni kalkulator, ki omogoča napredno računanje (programiranje) s celimi (int) števili in nizi. Kalkulator omogoča:

• računanje aritmetičnih izrazov v obratnem poljskem zapisu (angl. reverse polish notation)
• preprosto konkatenacijsko programiranje (s pomočjo sklada)
• izvedbo preprostih programskih konstruktov (pogojev, zank, funkcij).

Kalkulator naj izraze bere s standardnega vhoda. Vsaka vrstica predstavlja en izraz, sestavljen iz več delov (nizov) - vsak predstavlja  bodisi veljaven ukaz, celo število ali niz znakov. Med posameznimi dela izraza je vedno (vsaj) en presledek. Predpostavite lahko, da so pri testiranju vsi vhodi sintaktično in semantično pravilni.  

Rešitev implementirajte s pomočjo 42 skladov: glavnega (indeks 0) in pomožnih (z indeksi od 1 do 41). Velika večina ukazov deluje nad glavnim skladom (z indeksom 0). Pri ukazih, ki se lahko izvajajo nad poljubnim skladom, je indeks sklada posebej določen s številom na vrhu glavnega sklada. 

Kalkulator naj podpira naslednje ukaze oz. operacije (nad glavnim skladom):

• echo - v vrstici izpiše vrh sklada 0 (sklad pusti nespremenjen); če je sklad prazen, izpiše prazno vrstico
• pop - odstrani vrh sklada 0
• dup - podvoji vrh sklada 0 (x -> x x)
• dup2 - podvoji par na vrhu sklada 0 (x y -> x y x y)
• swap - zamenja vrhnja dva elementa sklada 0 (x y -> y x)

Naslednje operacije zamenjajo vrh glavnega  sklada z ustreznim rezultatom (x -> y):

• char - vrh sklada 0 zamenja z znakom, ki ima ASCII/Unicode kodo vrha sklada
• even - vrh sklada 0 zamenja z 1, če je vrh sod, sicer z 0
• odd - vrh sklada 0 zamenja z 1, če je vrh lih, sicer z 0
• ! - vrh sklada 0 zamenja s faktorielo vrha
• len - vrh sklada 0 zamenja z dolžino elementa na vrhu

Naslednje operacije zamenjajo vrhnja dva elementa glavnega sklada z ustreznim rezultatom (x y -> r):

• <> - primerja zgornja dva elementa (x y) sklada 0 in na sklad porine 1 (če x <> y) ali 0 (če x == y)
• < - primerja zgornja dva elementa sklada 0 in na sklad porine 1 (če x < y) ali 0 (sicer)
• <= - primerja zgornja dva elementa sklada 0 in na sklad porine 1 (če x <= y) ali 0 (sicer)
• == - primerja zgornja dva elementa sklada 0 in na sklad porine 1 (če x == y) ali 0 (sicer)
• > - primerja zgornja dva elementa sklada 0 in na sklad porine 1 (če x > y) ali 0 (sicer)
• >= - primerja zgornja dva elementa sklada 0 in na sklad porine 1 (če x >= y) ali 0 (sicer)
• + - na sklad 0 porine vsoto vrhnjih dveh elementov sklada
• - - na sklad 0 porine razliko vrhnjih dveh elementov sklada
• * - na sklad 0 porine zmnožek vrhnjih dveh elementov sklada
• / - na sklad 0 porine kvocient (celoštevilsko deljenje) vrhnjih dveh elementov sklada
• % - na sklad 0 porine ostanek po deljenju elementa pod vrhom z elementom na vrh
• . - stakne (združi, zlepi) vrhnja dva elementa sklada 0 v en element (x y -> xy)
• rnd - na sklad 0 porine naključno število, ki ima vrednost >= x in <= y 

Naslednje operacije omogočajo izvedbo pogojnega stavka (izpolnjenost pogoja hranimo v interni spremeljivki):

Če ukaz ni na seznamu zgoraj naštetih, potem gre za element (število ali niz), ki se porine na vrh glavnega sklada 0 (push).

Primeri izvajanja

V vseh primerih so vrstice, ki se začnejo z >, vnešene v program, ostale pa so izpis programa. Program zaženemo z

java Naloga1

Nekaj primerov izvajanja operacij:

> 0 -1 3 5 -7 11 -13 17 dup2 echo pop echo swap 0 print
17
-13
17 -13 -13 11 -7 5 3 -1 0

> 151 141 + echo -100 150 - echo + echo
292
-250
42

> 3 5 11 17 0 print + + 10 * 0 print * 11 / echo
17 11 5 3
330 3
90

> 6 ! echo 42 == echo even 0 print
720
0
1

> 65 90 rnd echo char echo
66
B

> 0 1 2 3 4 3 4 4 1 fun dup 0 reverse swap 2 2 move 0 print 1 print 2 print
4 3 2 1 0
swap reverse 0 dup
3 4

> 0 1 2 3 3 1 fun 0 reverse dup 0 print 1 run 0 print 2 1 loop 0 print
3 2 1 0
0 0 1 2 3
0 0 0 1 2 3 3

> 7 3 1 2 5 1 fun == then ?dup2 else ?+ 1 run 0 print
10

> 9 1 fun dup 0 reverse swap % dup then ?1 ?run 24 10 0 print 1 run pop echo
10 24
2

> 3 1 fun 0 100 rnd 3 2 fun 5 1 loop 7 3 fun dup2 <= then ?pop else ?swap ?pop 3 4 fun 4 3 loop 1 print 2 print 3 print 4 print 2 run 0 print 4 run 0 print
rnd 100 0
loop 1 5
?pop ?swap else ?pop then <= dup2
loop 3 4
34 96 12 48 25
12

Drugi napotki in namigi

Pri izvedbi lahko uporabite le javansko knjižnico java.util.Scanner. Vse ostale knjižnice niso dovoljene oz. potrebne - izrecno niso dovoljene knjižnice, ki vsebujejo javanske zbirke (npr. ArrayList) iz Collection Framework-a

Za predstavitev skladov najprej zapišite vmesnik (abstraktni podatkovni tip) Stack z ustreznimi operacijami, nato pa ga implementirajte s pomočjo javanskega polja. Velikost sklada lahko omejite na 64. Za izvedbo več skladov napišite še vnesnik Sequence.

Upoštevajte, da je celoten izraz (program) napisan v eni vrstici, torej so pred obdelavo vsake vrstice vhoda vsi skladi prazni ter izpolnjenost pogoja nastavljena na  FALSE. 

Kot aritmetične operacije lahko uporabljate operacije nad javanskimi primitivnimi tipi (int), za določanje naključnega števila pa metodo Math.random().

Oddaja naloge

Vse podrobnosti za avtomatsko ocenjevanje in oddajo so (bodo) predstavljene v navodilih za oddajo domačih nalog.

Veliko uspeha pri delu!