BUK 2002 - 4. Zadanie domowe

Napisz program na maszynę stosową, sortujący algorytmem insertionsort.

Wejście

Na stosie zapisana są dane a_0,a_1,a_2,…,a_n, a na samym wierzchołku znajduje się licza n — rozmiar danych.

Wyjście

Stos wyjściowy powinien mieć tę samą postać przy czym dane powinny być już posortowane, (na spodzie stosu — najmniejsza wartość, na wierzchołku — największa), na samej górze dalej powinna znajdować się wartość n — rozmiar danych.

Przykład

Dla danych:

5 6 8 1 4

poprawną odpowiedzią jest:

1 5 6 8 4

---

Język maszyny stosowej

• PUSH x --- wrzuć na wierzchołek stosu wartość x,
• POP --- usuń ze stosu wartość znajdującą się na czubku stosu (TOP()),
• POP x --- usuń x-tą wartość na stosie (licząc od wierzchołka),
• DUP x --- wczytaj x-tą wartość na stosie (licząc od wierzchołka) i wrzuć ją na stosie (stara kopia dalej zostaje na stosie)
• DUP --- analogicznie jak DUP x, lecz najpierw zdejmowana jest ze stosu wartość x, a następnie wykonywane jest polecenie DUP x,
• STORE x --- zdejmij ze stosu wartość i zapisz ją na x-tej pozycji na stosie (licząc od wierzchołka)
• STORE --- analogicznie jak STORE x, zdejmij ze stosu x, a następnie wykonaj STORE x,
• ADD --- zsumuj dwie wartość znajdujące się na wierzchołku stosu i wrzuć wynik na stos (x:=POP();y:=POP();PUSH(x+y))
• SUB --- odejmij dwie wartość znajdujące się na wierzchołku stosu i wrzuć wynik na stos (x:=POP();y:=POP();PUSH(y-x))
• ADD x --- dodaj x do wartości znajdującej się na wierzchołku stosu i wrzuć wynik na stos (y:=POP();PUSH(x+y))
• GOTO e --- skok do etykiety e w programie
• IF e --- zdejmij ze stosu wartość, jeśli jest większa od zera to wykonaj skok do etykiety e (x:=POP(); if (x>0) GOTO e)
• HALT --- zatrzymaj wykonanie programu
• PRINT --- zdejmij ze stosu wartość i ją wypisz

Przykład

program obliczający wartość bezwzględna z liczby na stosie:

          DUP 1
          IF dodatnia
ujemna:   PUSH 0
          DUP 2
          SUB
          STORE 1          
dodatnia: PRINT
// program kończy się z pustym stosem

Termin i punktacja

Ostateczny termin na nadsyłanie rozwiązań upływa o godzienie 23:59 2002.06.09. Za zadanie można otrzymać maksymalnie 10 punktów.