Lab obiektowy i współbieżny zadanie 1

Pierwsze zadanie z fascynującego przedmiotu “Laboratorium Programowania Obiektowego i współbieżnego brzmi tak:”

Napisz w Javie hierarchię klas opisujących pracowników pewnej firmy komputerowej. Wyraź w tej hierarchii następujące fakty:

    *

      wszyscy pracownicy są ludźmi,
    *

      każdy kierownik projektu, projektant, analityk, tester, programista, a nawet sam prezes jest pracownikiem,
    *

      każdy kierownik projektu oraz prezes jest kierownikiem.


Tak zaprojektuj klasy by:

    *

      każdy człowiek znał swoje imię i nazwisko,
    *

      każdy pracownik znał swoje stanowisko (tekst) i swego szefa (oczywiście prezes nie ma szefa, szefem kierownika projektu jest prezes, szefami pozostałych pracowników są kierownicy projektów),
    *

      każdy pracownik, prócz prezesa, brał udział w dokładnie jednym projekcie, i oczywiście znał ten projekt,
    *

      każdy kierownik projektu znał członków swojego projektu,
    *

      każdy projektant znał swoją dziedzinę,
    *

      prezes był tylko jeden.


Stwórz też klasy opisujące:

    *

      projekt (zna swoją nazwę),
    *

      dziedzinę (wyznaczającą zakres kompetencji projektanta), dziedzina zna swój słowny opis.

Każdy z ludzi musi umieć podać swój opis tekstowy (komunikat toString). Opis ma zawierać wszystkie informacje, które zna dany człowiek (np. nazwę projektu, czy pełny opis szefa). Napisz fragment programu w Javie, który utworzy kilka (ok. 10) obiektów reprezentujących ludzi zatrudnionych w przykładowej firmie na różnych stanowiskach, umieści ich w kolekcji, a następnie wypisze opis każdego z nich. Zadbaj o to, by tworzenie nowych obiektów było jak najprostsze. Całość zaprojektuj w postaci pakietu i zapisz jako jeden plik jar (tu mogą się przydać informacje z przedmiotu HTML i Java).


Wskazówki:

    *

      przy implementacji prezesa posłuż się statyczną metodą produkującą, w celu zrealizowania wzorca Singleton,
    *

      rozwiązanie ma obrazować statyczny stan firmy, nie interesują nas zmiany (dynamiczne aspekty stanu firmy, np. to że ktoś awansuje),
    *

      zadanie jest proste.



A oto rozwiązanie:
Zadanie 1

Lab HTMLa i Javy, zadanie 2

Drugie zadanie z nowego przedmiotu, Laboratorium HTML i Java brzmiało następująco:

  Napisz klasę implementującą zbiór liczb całkowitych. Przy tworzeniu obiektów tej klasy, użytkownik podaje z jakiego zakresu liczb będą elementy tego zbioru (dla uproszczenia zakładamy, że to przedział o dolnej granicy 0) oraz ile wynosi maksymalna liczba elementów w zbiorze. Zbiór powinien mieć typowe operacje:

    * dodaj element,
    * usuń element,
    * podaj rozmiar,
    * sprawdź czy zadana liczba należy do zbioru,
    * podaj napis będący tekstową reprezentacją zbioru (toString).

W swojej implementacji zbioru:

    * użyj tablic,
    * sygnalizuj zgłoszeniem wyjątku przekroczenie maksymalnej liczności zbioru,
    * użyj statycznej metody produkującej, by na podstawie parametrów dostarczyć właściwą implementację zbioru (wektor charakterystyczny albo posortowana tablica).

A oto rozwiązanie:
Lab HTML i Java zadanie 2

Lab HTMLa i Javy, zadanie 1

Pierwsze zadanie z nowego przedmiotu, Laboratorium HTML i Java brzmiało następująco:

Stwórz zestaw powiązanych stron (co najmniej 3, nie muszą być duże) dotyczących Twojego hobby. Strony te powinny spełniać następujące warunki: 
    * strony mają być stworzone ręcznie (tzn. nie powinny być wynikiem zapisania dokumentu Write'a czy Worda w formacie (X)HTML),
    * strony mają używać wspólnego arkusza stylów,
    * strony powinny być zapisane za pomocą kodowania utf-8 (żeby to można było zauważyć, strony powinny być po polsku),
    * wszystkie strony muszą być zapisane w tym samym standardzie (X)HTMLa,
    * wszelkie formatowania powinny być wyrażone za pomocą arkuszy stylów,
    * należy zdefiniować (i użyć) co najmniej jedną, własną klasę stylów, choćby do wyświetlenia tekstu z boku, jak to opisano w materiałach pomocniczych poniżej,
    * strony powinny zawierać co najmniej następujące elementy html:
          o a,
          o ul i ol,
          o dl (lista definicji, elementy zaznacza się znacznikami dt i dl),
          o table (tablica nie musi być duża, wystarczy nawet 2*2, byleby użyć zarówno th jak i td),
          o img,
          o h1.

Arkusz(e) stylów powinien zawierać co najmniej:

    * definicje własnej klasy (własnych klas),
    * selektor powodujący, że elemeny (li) z listy uporządkowanej (ol) będą wypisywane inną czcionką (np. innego rozmiaru czy koloru), niż elementy z listy nieuporządkowanej (ul),
    * formatowanie ekranowe i do druku: na wydruku wszystkie teksty mają być czarne (a na ekranie co najmniej część nie), ponadto na wydruku nie powinny się pojawić żadne rysunki/zdjęcia.
    * wszystkie strony i arkusze muszą walidować się narzędziem z witryny w3.org.

Nie wiedziałem, jak sobie poradzę ze zrobieniem STRONY INTERNETOWEJ ale musiłem stawić czoło temu zadaniu.

A oto rozwiązanie:
Lab HTML i JAVA 1

Laboratorium C++

Zadanie z laboratorium programowania C++ na Informatyce UW.

Program zaliczeniowy ? wersja finalna ? 2008-10-23.
Program zaliczeniowy polega na napisaniu aplikacji w C++. Celem aplikacji jest wykonywanie prostych 
programów na danych.
Programem nazywamy listę kolejnych operacji na danych.
Każdy program jest postaci:
operacja 
operacja 
....
operacja 
Każda operacja jest pewnym przekształceniem plików z danymi.
Są dostępne następujące operacje:
? Operacja filtrowania
? Składania: FILTER     .
?  =, !=, >, =, <=.
? Schemat pliku wynikowego jest taki sam jak źródłowego.
? Operacja dołączenia
? Składnia: MERGE   
? Operacja polega na zsumowaniu kolumn plików 1 i 2.
? Operacja powiedzie się jeśli kolumny plików 1 i 2 mają inne nazwy oraz ilość wierszy w pliku 1 i 
w pliku 2 jest taka sama.
? Wynikowy plik ma wszystkie kolumny pliku 1 i wszystkie kolumny pliku 2.
? Operacja łączenia
? Składnia: JOIN   
? Operacja polega na wypisaniu do pliku docelowego najpierw zawartości pliku1 a za nim pliku2.
? Operacja jest wykonalna tylko i wyłącznie, gdy ilość kolumn pliku1 i pliku2 jest taka sama i typy 
kolejnych kolumn są takie same.
? Wynikowy plik ma schemat taki sam jak plik1.
? Operacja wyliczenia
? Składnia: AGREGATE     
?  oznacza operację z listy: maksimum [MAX], minimum [MIN], suma [SUM], średnia 
[AVG] (zaokrąglenie do int'a), ilość [COUNT].
? Operacja powiedzie się jeśli typ danych jest zgodny z operacją.
? Wynikowy plik ma strukturę złożoną z jednej kolumny o podanej nazwie typu int oraz zawiera 
jeden wiersz z wynikiem operacji.
? Operacja dodania danych.
? Składnia: INSERT    ... 
? Operacja dodaje wiersz danych na końcu pliku danych.
? Operacja się powiedzie jeśli ilość danych zgadza się z listą kolumn oraz typu danych się 
zgadzają.
? Operacja ładowania danych.
? Składnia: LOAD   
? Operacja odczytuje linia po linii dane z pliku wejściowego i dopisuje je na końcu wskazanego 
pliku.
? Dane w pliku z danymi są zapisane linia po linii.
? Każda linia zawiera jeden rekord danych.? Każda linia zawiera pewną ilość pól postaci   ... 
? Każda wartość jest zapisana w formacie wartości przyjmowanym we wszystkich 
komendach.
? Operacja się powiedzie jeśli ilość danych zgadza się z listą kolumn oraz typu danych się 
zgadzają.
? Operacja stworzenia pustego pliku.
? Składnia: CREATE    ... 
? Operacja tworzy pusty plik o podanej strukturze.
? Dodatkowa operacja wypisania pliku.
? Składnia: PRINT 
? Operacja nie posiada żadnego wyjścia.
? Operacja powinna wypisać na standardowe wyjście zawartość danego pliku (oczywiście w 
postaci zinterpretowanej).
? Dane powinny być wypisane wierszami. Pierwszy wiersz powinien być w postaci:   ...  
? Kolejne wiersze powinny zawierać kolejne wartości pól (w odpowiedniej kolejności) zapisanie w 
formacie , czyli np. 'M &38; M' oznacza wartość ?M & M?.
Legenda:
?  - pole postaci 'łańcuch znaków bez znaku ' , & oraz znaku nowej linii. Znaki ', & oraz 
nowej linii są zapisywane jako &;'
? Wszelkie nazwy plików, kolumn, etc. są ciągami znaków [a-z] i [A-Z] oraz [0-9] oraz znaku _ o 
długości maksymalnie 50 znaków.
?  oznacza typ danych. Są dwa typy, string ? oznacza łańcuch znaków dowolnej długości oraz 
int oznacza liczę 32 bitową ze znakiem.
Schemat działania aplikacji składa się z następujących kroków:
1. Wczytanie programu.
2. W pętli dla każdej komendy.
3. Wykonaj komendę.
Wykonanie każdej komendy polega na:
1. Wczytaniu plików źródłowych do pamięci.
2. Wykonanie komendy w pamięci na danych w pamięci.
3. Zapis danych do plików docelowych.
Aplikacja powinna zapisywać wszelkie dane w lokalnym katalogu. Każdy błąd w programie jest 
krytyczny i powinien przerywać działanie aplikacji. Program powinien być wczytywany ze 
standardowego wejścia. Wszelkie błędy odczytu/zapisu na dysk są błędami krytycznymi. Struktura 
danych w plikach dowolna, wg własnych pomysłów. Optymalizacja implementacji komend nie jest 
priorytetem. Można założyć, że w każdej chwili działania programu całość danych w plikach mieści się 
w pamięci. W plikach nie może być wartości NULL.
Przykład programu:
CREATE tabela1 dzial string zarobki int
INSERT tabela1 tabela1 'Zarząd' '10000'
INSERT tabela1 tabela1 'Zarząd' '15000'
INSERT tabela1 tabela1 'Zarząd' '12000'
INSERT tabela1 tabela1 'IT' '4000'
INSERT tabela1 tabela1 'Administracja' '2000'
INSERT tabela1 tabela1 'IT' '4000'INSERT tabela1 tabela1 'Zarząd' '19000'
INSERT tabela1 tabela1 'IT' '5000'
FILTER tabela2 tabela1 dzial = 'Zarząd'
AGREGATE tabela3 tabela2 zarobki SUM zarobki
FILTER tabela2 tabela1 dzial = 'IT'
AGREGATE tabela4 tabela2 zarobki SUM zarobki
JOIN tabela3 tabela3 tabela4
PRINT tabela3
Po wykonaniu programu w tabeli 3 powinny być dwa wiersze. Pierwszy powinien zawierać sumę 
zarobków zarządu zaś drugi sumę zarobków działu IT.
Po wypisaniu na standardowym wyjściu powinno być:
zarobki int
'56000'
'13000'


Oficjalne ? wiążące FAQ do zadania.
1. Jakie znaki mogą się pojawić w nazwach plików (plików wejściowych, plikach wyjściowych i 
plikach do ładowania danych) i nazwach kolumn (kolumny w plikach)?
Odp: W nazwach mogą się pojawiać tylko angielskie literki małe (a, b, c, ..., z), angielskie literki 
duże (A, B, C, ..., Z), cyfry (0, 1, ..., 9) oraz znak podkreślenia ( _ ). Nie może być ani spacji ani 
polskich znaków. Maksymalna długość to 50 znaków (liczona jako ilość znaków w nazwie). W 
związku z potencjalnymi problemami z systemem plików, na którym uruchamiany jest program 
zakłada się, że program może w zakresie rozróżniania wielkości liter w nazwach plików polegać 
na systemie plików. Czyli jest dopuszczalne, że pliki 'Ala.db', 'ALA.db' i 'ala.DB' odnoszą się w 
istocie do tego samego pliku i podanie jakiejkolwiek z tych nazw powoduje odczytanie tego 
samego pliku. Natomiast nie jest dopuszczalne, aby polecenie zapisania pliku 'Ala.db' w istocie 
zapisywało plik 'ALA.DB', choć jeśli taki plik istnieje to może zostać nadpisany.
2. Jakie znaki mogą się znaleźć w wartościach danych?
Odp: Każda wartość jest zapisana w postaci napisu ograniczonego znakami apostrofa (' - znak 
o kodzie 39). We wnętrzu napisu nie występują znaki apostrofa ( ' ) oraz nowej linii (znaki o 
kodach 13 i 10). Ponadto każdy znak może być reprezentowany w postaci &; przy 
czym  jest z zakresu od 1 do 255. Co więcej znak & musi być reprezentowany w ten 
sposób. Np. wartość M'c ma kota &John's ma psa może zostać zapisana jako: 
'M&39;c ma kota &38;&13;&10;John&39;s ma psa' albo jako '&77;&39;&99;&32;ma&32;kota 
&38;&13;&10;John&39;s ma&32;psa'. Natomiast nie poprawne są napisy: 'M&390;c ma kota 
&38;&13;&10;John's ma psa' (niepoprawne wartość 390 oraz niepoprawny znak ' w środku 
napisu), 'M&39;c ma kota &&13;&10;John&39;s ma psa' (niepoprawny znak &) oraz 'M&39;c 
ma kota &38;John&39;s ma psa' (nowa linia w środku napisu).
3. Czy program powinien obsługiwać BOM w plikach i czy powinien obsługiwać pliki zapisane w 
UTF-8, UTF-16, itd.?
Odp: Nie, zakłada się, że program wczytywany ze standardowego wejścia jest zapisany w 
formacie ASCII, nie zawiera BOM. Pliki danych w komendzie LOAD nie posiadają BOM są 
zapisane w formacie ASCII. Nie specyfikujemy, w jakim kodowaniu są znaki w aplikacji (np. 
ISO-8559-1, ISO-8559-2, WINDOWS-1250), ale autor aplikacji powinien być w stanie 
odpowiedzieć jak kwestia kodowania wpływa na działanie aplikacji. Pliki danych są w pełni 
zdefiniowane przez aplikację, więc format ich zapisu jest dowolny.
4. Jak aplikacja powinna się zachować w przypadku problemów w czasie wykonania programu?
Odp: Aplikacja powinna obsługiwać normalne błędy, które mogą się pojawić w czasie działania 
aplikacji, czyli np. błędne formaty komend, błędne formaty plików, brak plików i brak praw 
dostępu do plików. W przypadku natrafienia na problem w czasie wykonania użytkownik 
powinien zostać poinformowany o charakterze problemu (czyli opis problemu w taki sposób, 
aby użytkownik zrozumiał i był w stanie coś zaradzić) oraz o miejscu wystąpienia problemu (np. 
jeśli problem pojawił się przy wykonywaniu komendy, to należy poinformować użytkownika, 
jakiej komendy dotyczy problem). Po wyświetleniu informacji o błędzie aplikacja powinna 
zakończyć działanie.
5. Co to znaczy, że komendy w programie powinny być transakcyjne?
Odp: Oznacza to, że wykonanie każdej komendy może się powieść lub nie. W przypadku, gdy 
wykonanie komendy nie powiodło się aplikacja powinna przywrócić stan sprzed rozpoczęcia 
wykonania komendy. W szczególności oznacza to usunięcie wszelkich plików tymczasowych. 
Nie dopuszcza się częściowego wykonania komendy polegającego np. na częściowym 
załadowaniu danych w komendzie LOAD albo częściowej agregacji danych w komendzie 
AGREGATE.
6. Czy lista   w poleceniu CREATE może być pusta czy tez nie? Innymi słowy 
czy możemy stworzyć plik bez żadnych kolumn?
Odp: Nie. W poleceniu CREATE lista kolumn musi zawierać co najmniej jeden element.7. Czy w operacje w poleceniu AGREGATE (max, min) w przypadku gdy plik/tabelka są puste 
mogą zwracać 0? Czy bardziej należy rozumieć to jako błąd (nie ma wierszy więc taka operacja 
liczenia max wartości z jakiejś kolumny jest w ogóle niemożliwa)? 
Odp: Polecenie powinno powodować błąd w przypadku, gdy operacja nie ma sensu. Operacje 
suma i średnia (SUM i AVG) mają sens tylko dla kolumn typu liczbowego. Operacje MIN, MAX 
i COUNT mogą być wykonane dla kolumny dowolnego typu. W przypadku MIN i MAX dla 
tekstów należy użyć tej samej relacji porządkowania tekstów co w poleceniu FILTER. Ponadto 
operacje MIN, MAX oraz AVG mają sens tylko dla niepustego zbioru. Operacje COUNT oraz 
SUM mają sens zarówno dla zbioru pustego jak i niepustego. W przypadku zbioru pustego 
zarówno COUNT jak i SUM zwraca 0.
8. Czy wartość '' jest dozwolona i co reprezentuje?
Odp: Taka wartość jest poprawna i reprezentuje napis długości 0 znaków (pusty napis).
9. Czy w operacji PRINT wartości powinny być wyświetlane w postaci zinterpretowanej i co to 
oznacza?
Odp: Tak, PRINT powinien wyświetlać wartości w postaci zinterpretowanej. Oznacza to, że 
sekwencje znaków, które kodują inny znak, np. &38;, powinny być napisane jako znak, który 
kodują a nie sekwencja kodująca. Np. napis 'M &38; M' powinien być przez PRINT wypisany 
jako 'M & M.
10. Czy operacja FILTER działa na tekstach?
Odp: Tak.
11. Czy jest w jakikolwiek sposób określone w jaki sposób aplikacja powinna wewnętrznie 
przechowywać wartości?
Odp: Nie. Aplikacja wewnętrznie może przechowywać wartości jakkolwiek. Oczywiście 
wewnętrzna reprezentacja może ułatwić lub utrudnić implementację wymaganych operacji na 
danych. Decyzja całkowicie należy do programisty.
12. Czy można założyć, ze w poleceniu FILTER operacja jest otoczona białymi znakami? Innymi 
słowy czy np. dzial='12343' (bez spacji oddzielających) przechodzi czy możemy wywalić błąd?
Odp: Aplikacja powinna przyjmować co najmniej programy, które posiadają pojedynczą spację 
pomiędzy elementami komendy. Czyli np. FILTER a b test = '15'. Dodatkowym atutem 
aplikacji będzie akceptowanie dowolnej ilości znaków białych pomiędzy elementami komendy. 
Zaś akceptowanie w miejscach, gdzie jest to możliwe, komend bez spacji jest cechą aplikacji 
bardzo dobrych. To samo dotyczy wszystkich komend a nie tylko komendy FILTER.
13. W zadaniu w opisie polecenia AGREGATE ostatnia linijka mówi: ?Wynikowy plik ma strukturę 
złożoną z jednej kolumny o podanej nazwie TYPU INT". Czy należy rozumieć, że plik 
stworzony przez AGREGATE może mieć w wyniku zarówno int jak i string?
Odp: Tak, w treści zadania jest błąd. Odpowiedź na pytanie 7 jest wiążąca i jej skutkiem jest to, 
że w wyniku operacji AGREGATE z funkcją MIN lub MAX na kolumnie typu string w pliku, 
wynikowym powstaje kolumna typu string.
14. Jakie mogą być typy wynikowe kolumny w operacji AGREGATE?
Odp: Dla funkcji COUNT, SUM i AVG wynikowa kolumna ma typ int. Dla funkcji MIN i 
MAX typu kolumny wynikowej jest taki sam jak typ kolumny, na której jest wykonywana 
funkcja. Oczywiście powyższe ustalenia mają sens tylko wtedy, gdy operacja ma sens, czyli tylko 
w sytuacja, które opisuje odpowiedź na pytanie 7.
15. Kiedy jest termin oddania zadania zaliczeniowego?
Odp: Ostateczny termin oddania mija 15 grudnia (2008-12-15). Programy oddanie po tym 
terminie nie będą rozpatrywane. Zaleca się, aby oddać program przed ostatnimi zajęciami, aby 
była szansa rozmowy na temat programu na ostatnich zajęciach.
16. Czy możemy milcząco założyć, że wewnątrz pliku mogą się pojawiać tylko takie znaki jak 
wymieniono tj. spacje, A-Za-z_0-9 oraz pomocnicze znaki & ; oraz apostrofy ' ' okalające 
wartość. Czy musimy to sprawdzać?
Odp: Zdecydowanie nie. W pliku mogą się pojawić wszystkie znaki o kodach ASCII od 0 do 
255. Trzeba rozróżnić dwie kwestie, specyfikację poprawności wejścia i założenie, że wejście jest 
zgodne ze specyfikacją. W naszym zadaniu jest wyspecyfikowane jakie wejście jest poprawne, ale nie ma założenia, że dane na wejściu spełniają tą specyfikację. Oczywiście jeśli dane na wejściu 
są niepoprawne to użytkownik powinien dostać odpowiedni komunikat.
17. Tak naprawdę nie widzę różnicy między operacją JOIN a LOAD. Z tego co widzę to operacja 
LOAD robi to samo co JOIN. Czy różnica polega na tym ze LOAD łączy dwa pliki: plik1 i 
plik2 w wynikowy plik1. Natomiast JOIN łączy plik1 i plik2 w nowy plik wynikowy plik3. Czy 
poprawnie to rozumiem?
Odp: Źle rozumiesz. Chodzi o to, że specyfikacja w żaden sposób nie opisuje formatu 
wewnętrznego plików, na których operuje program (chodzi o pliki źródłowe/wynikowe we 
wszystkich komendach). Więc JOIN w istocie robi to samo co LOAD, ale w komendzie LOAD 
plik, z którego dane są ładowane ma określony format (być może inny niż pliki z danymi, być 
może taki sam, to zależy od programisty).
18. Czy w operacji FILTER i AGREGATE może się zdarzyć sytuacja, że plikiem wynikowym 
będzie plik, z którego biorę dane do przetworzenia, czyli na przykład: AGREGATE plik1 plik1 
zarobki SUM zarobki, czy zawsze to będzie nowy plik?
Odp: Nie ma żadnych założeń, czy jest to inny czy ten sam plik, więc może być inny i może być 
ten sam. Więcej informacji, patrz odpowiedź na pytanie 5.
19. Operacja JOIN i MERGE może mieć więcej niż dwie tabele do połączenia/zsumowania, na 
przykład: JOIN     ... ?
Odp: Nie, specyfikacja mówi, że operacja łączy dokładnie dwie tabele.
20. Czy w wartościach pól mogą pojawić się polskie literki?
Odp: Tak. Trzeba widzieć różnice pomiędzy wartościami a nazwami. Wartości występują 
wszędzie tam, gdzie dodajemy dane np. do kolumny, przy filtrowaniu, itp. Np. w INSERT 
tabela1 tabela1 'Zarząd' '1000' tabela1 to nazwa tabeli zaś 'Zarząd' to wartość. W wartościach 
mogą występować polskie literki jak i inne dziwne znaki np. %, $, /, [, ], itd. itd. zaś w nazwach 
(kolumn, plików) mogą występować tylko i wyłącznie normalne znaki tak jak to mówi 
specyfikacja, czyli [a-z] i [A-Z] oraz [0-9] oraz znak _.

A oto rozwiązanie:

include 
include 
include 
include 
include 
define round(x) (x<0?ceil((x)-0.5):floor((x)+0.5))

const int ERR_FILE=1;
const int ERR_LAST_TYPE_MISSING=2;
const int ERR_BAD_TYPE=3;
const int ERR_NUM_ROWS=4;
const int ERR_NAME=5;
const int ERR_TYPE=6;
const int ERR_NUM_COL=7;
const int ERR_AGGR=8;
const int ERR_AMP=9;
const int ERR_ASCII=10;
const int ERR_APO=11;
const int ERR_NAME_LEN=12;
const int ERR_NAME_CHAR=13;
const int ERR_COMM=14;

using namespace std;

	int str2int(string wartosc)
	{
		int liczba=0;
		for(int i=0;i='0')&&(wartosc[i]<='9'))
			{
				liczba=liczba*10+(wartosc[i]-'0');
			}
		}
		return liczba;
	}

	void my_itoa(int value, string& buf, int base){
		
		int i = 30;
		
		buf = "";
		
		for(; value && i ; --i, value /= base) buf = "0123456789abcdef"[value % base] + buf;
		
	}


	string AsciiEncode(string wartosc_string)
	{
		string zwroc="";
		//zamieniamy ' & ; n
		for(int i=0;i")
		{
			if(typ=="int")
			{
				if(wartosc_int>liczba)
				{
					wynik=1;
				}
			}
			else
			{
				if(wartosc_string>wartosc)
				{
					wynik=1;
				}
			}
		}
		else if(operacja==">=")
		{
			if(typ=="int")
			{
				if(wartosc_int>=liczba)
				{
					wynik=1;
				}
			}
			else
			{
				if(wartosc_string>=wartosc)
				{
					wynik=1;
				}
			}
		}
		else if(operacja=="<=")
		{
			if(typ=="int")
			{
				if(wartosc_int<=liczba)
				{
					wynik=1;
				}
			}
			else
			{
				if(wartosc_string<=wartosc)
				{
					wynik=1;
				}
			}
		}
		else if(operacja=="=")
		{
			if(typ=="int")
			{
				if(wartosc_int==liczba)
				{
					wynik=1;
				}
			}
			else
			{
				if(wartosc_string==wartosc)
				{
					wynik=1;
				}
			}
		}
		else if(operacja=="!=")
		{
			if(typ=="int")
			{
				if(wartosc_int!=liczba)
				{
					wynik=1;
				}
			}
			else
			{
				if(wartosc_string!=wartosc)
				{
					wynik=1;
				}
			}
		}
		else if(operacja=="<")
		{
			if(typ=="int")
			{
				if(wartosc_int<liczba)
				{
					wynik=1;
				}
			}
			else
			{
				if(wartosc_string<wartosc)
				{
					wynik=1;
				}
			}
		}
		else
		{
			wynik=-1; //nieznany operator.
		}

		return wynik;
	}

	string Wypisz_typ()
	{
		return nazwa+" "+typ;
	}

	string Wypisz(int zamien)
	{
		string zwroc="";
		
		if(zamien)
		{
			zwroc=AsciiEncode(wartosc_string);
		}
		else
		{
			zwroc=wartosc_string;
		}

		
		return "'"+zwroc+"'";
	}


}; // Koniec klasy Pole.




//Klasy reprezentujace wiersze tabel

class Wiersz
{
	public:
	vector  pola;
	Wiersz(vector  dane) : pola(dane){}
	Wiersz() {}
	string Wypisz(int zamien)
	{
		string wypisz="";
		int ile=pola.size();
		for(int i=0;i0)
		{
			wypisz+=pola.at(ile-1).Wypisz(zamien);
		}


		return wypisz;
	}
}; // Koniec klasy Wiersz.




//Klasa reprezentujaca tabele z danymi.
class Tabela
{

public:
	vector  wiersze;
	vector  typy;

	void Czysc()
	{
		wiersze.clear();
		typy.clear();
	}

	Pole Agreguj(string funkcja,string kolumna)
	{
		int kol=Kolumna(kolumna);
		Pole wynik;
		int suma=0;
		int min=0;
		int max=0;
		string min_str="";
		string max_str="";

		if(kol==-1)
		{
			
			wynik.typ="blad";
		}
		else
		{
			min=wiersze.at(0).pola.at(kol).wartosc_int;
			max=min;
			min_str=wiersze.at(0).pola.at(kol).wartosc_string;
			max_str=min_str;
			

			for(int i=0;i<wiersze.size();i++)
			{
				suma+=wiersze.at(i).pola.at(kol).wartosc_int;

				//min
				if(wiersze.at(i).pola.at(kol).wartosc_int<min)
				{
					min=wiersze.at(i).pola.at(kol).wartosc_int;
				}

				if(wiersze.at(i).pola.at(kol).wartosc_stringmax)
				{
					max=wiersze.at(i).pola.at(kol).wartosc_int;
				}

				if(wiersze.at(i).pola.at(kol).wartosc_string>max_str)
				{
					max_str=wiersze.at(i).pola.at(kol).wartosc_string;
				}
			}


			if(funkcja=="COUNT")
			{
				wynik.wartosc_int=wiersze.size();
				my_itoa(wiersze.size(),wynik.wartosc_string,10);
				wynik.typ="int";
			}
			else if(funkcja=="MAX")
			{
				wynik.typ=typy.at(kol).typ;
				if(wynik.typ=="int")
				{
					wynik.wartosc_int=max;
					my_itoa(max,wynik.wartosc_string,10);
				}
				else
				{
					wynik.wartosc_string=max;
				}
				
			}
			else if(funkcja=="MIN")
			{
				wynik.typ=typy.at(kol).typ;
				if(wynik.typ=="int")
				{
					wynik.wartosc_int=min;
					my_itoa(max,wynik.wartosc_string,10);
				}
				else
				{
					wynik.wartosc_string=min;
				}
				
			}
			else if((funkcja=="AVG")&&(typy.at(kol).typ=="int"))
			{
				wynik.typ="int";
				wynik.wartosc_int=round(suma/wiersze.size());
				my_itoa(wynik.wartosc_int,wynik.wartosc_string,10);
			}
			else if((funkcja=="SUM")&&(typy.at(kol).typ=="int"))
			{
				wynik.typ="int";
				wynik.wartosc_int=suma;
				my_itoa(wynik.wartosc_int,wynik.wartosc_string,10);
			}
			else
			{
				wynik.typ="blad";//blad.
			}

			
		}

		return wynik;
	}

	int Kolumna(string nazwa)
	//zwraca numer kolumny.
	{
		int znalezione=-1; //blad.
		for(int i=0;i<typy.size();i++)
		{
			if(typy.at(i).nazwa==nazwa)
			{
				znalezione=i;
				break;
			}
		}
		return znalezione;
	}

	int Filtruj(string kolumna, string operacja, string wartosc)
	{
		int blad=0;
		int kol=Kolumna(kolumna);

		if(kol!=-1)
		{
			for(int i=0;i<wiersze.size();i++)
			{
				
				int odp=wiersze.at(i).pola.at(kol).Porownaj(operacja,wartosc);
				if(odp==-1)
				{
					blad=61; //zly operator.
					break;
				}
				else if(odp==0)
				{
					wiersze.erase(wiersze.begin()+i,wiersze.begin()+i+1);
					i=i-1;
				}
			}
		}
		else
		{
			blad=51; //nie ma takiej kolumny.
		}

		return blad;
	}

	int Serializuj(string nazwa)
	{
		int blad=0;
		fstream plik;
		plik.open((nazwa+"_data.txt").c_str(),ios::out);
		if(plik.good())
		{

			plik<<"CREATE "<<nazwa<<" ";
			//zapisujemy.
			//Najpierw typy.
			for(int i=0;i<typy.size();i++)
			{
				plik<<"'"<<typy.at(i).nazwa<<"' "<<typy.at(i).typ<<" ";
			}
			plik<<"n";

			//Teraz dane.
			for(int i=0;i<wiersze.size();i++)
			{
				plik<<"INSERT "<<nazwa<<" "<<nazwa<<" "<<wiersze.at(i).Wypisz(1)<<"n";
			}

			plik.close();
		}
		else
		{
			blad=41;//nie ma dostepu do pliku.
		}

		return blad;
	}

	int Dodaj(vector  pola)
	{
		Wiersz w;
		w.pola=pola;
		wiersze.push_back(w);
		return 0;
	}

	int Utworz(vector  typ,int poczatek)
	{
		int blad=0;

		for(int i=poczatek;i<typ.size();i+=2)
		{
			typy.push_back(Pole(typ.at(i),typ.at(i+1),"1"));
		}
		
		return blad;
	}

	int Wstaw(vector dane,int poczatek)///////////////////////
	{
		int blad=0;

		vector tmp; 
		if(dane.size()-poczatek==typy.size())
		{
			for(int i=poczatek;i<dane.size();i++)
			{
				Pole tymczas=Pole(typy.at(i-poczatek).nazwa,typy.at(i-poczatek).typ,dane.at(i));
				tmp.push_back(tymczas);
				
			}
			
			if(blad==0)
			{
				Dodaj(tmp);
			}
		}
		else
		{
			blad=11; //Niepoprawna ilosc danych
		}
		return blad;
	}

	void Wypisz()
	{
		//Wypisujemy typy
		for(int i=0;i<typy.size();i++)
		{
			cout<<typy.at(i).Wypisz_typ()<<" ";
		}
		cout<<"n";

		//Teraz wiersze
		int ile=wiersze.size();
		for(int i=0;i<ile;i++)
		{
			cout<<wiersze.at(i).Wypisz(0)<<"n";
		}
	}

}; // Koniec klasy tabela.




class Parser
{
private:
	vector  klucze;
	string komenda;
public:
	int blad;		//Kod bledu.
	Tabela tabelka1;
	Tabela tabelka2;

	Parser() : blad(0){}

	void Czysc()
	{
		tabelka1.Czysc();
		tabelka2.Czysc();
		klucze.clear();
		komenda="";
	}

	int Wczytuj(string nazwa)
	{
		fstream plik;
		plik.open((nazwa+"_data.txt").c_str(),ios::in);
		if(plik.good())
		{
			string dane;
			while(getline(plik,dane))
			{
				Wykonaj(dane);
			}
			
			plik.close();
		}
		else
		{
			blad=ERR_FILE;
			cout<<"Problem z plikiem wejsciowym n-----n"<<komenda;
			throw(ERR_FILE);
		}
		
		return blad;
	}

	Tabela Deserializuj(string nazwa)
	{
		Parser pars;
		blad=pars.Wczytuj(nazwa);
		return pars.tabelka1;
	}

	int Insert()
	{
		Nazwa(1);
		Nazwa(2);
		tabelka1=Deserializuj(klucze.at(2));
		blad=tabelka1.Wstaw(klucze,3);

		if(blad==0)
		{
			blad=tabelka1.Serializuj(klucze.at(1));
		}

		return blad;
	}

	int Create()
	{
		for(int i=2;iklucze.size()-1)
			{
				cout<<"Brak typu ostatnigon-------n"<<komenda;
				blad=ERR_LAST_TYPE_MISSING;
				throw(blad);
			}
			else if((klucze.at(i+1)!="string")&&(klucze.at(i+1)!="int"))
			{
				cout<<"Nieprawidlowy typn-------n"<<komenda;
				blad=ERR_BAD_TYPE; //Nieprawidlowy typ.
				throw(blad);
			}
		}

		if(blad==0)
		{
			blad=tabelka1.Utworz(klucze,2);
		}

		if(blad==0)
		{
			blad=tabelka1.Serializuj(klucze.at(1));
		}


		return blad;
	}

	int Filter()
	{
		//Filtruje.
		//Czytamy tabele do przefiltrowania
		tabelka1=Deserializuj(klucze.at(2));
		//Usuwamy niepasujace wiersze
		blad=tabelka1.Filtruj(klucze.at(3),klucze.at(4),klucze.at(5));
		//Zapisujemy:
		blad=tabelka1.Serializuj(klucze.at(1));
		return blad;
	}

	int Load()
	{
		//Laduje dane.
		Parser parserek;
		string wiersz;
		//Otwieramy plik:
		fstream plik;
		tabelka1=Deserializuj(klucze.at(2));
		if (blad==0)
		{
			plik.open(klucze.at(3).c_str(),ios::in);
			if(plik.good())
			{
				
				//Zwalimy robote na juz napisana funkcje:
				while((blad==0)&&(getline(plik,wiersz)))
				{
					blad=parserek.Przetworz(wiersz);

					if(blad==0)
					{
						blad=tabelka1.Wstaw(parserek.klucze,0);
					}
				}

				if(blad==0)
				{
					blad=tabelka1.Serializuj(klucze.at(1));
				}
			}
			else
			{
				cout<<"Problem z plikiem wejsciowym n-----n"<<komenda;
				blad=ERR_FILE;
				throw(blad);
			}
		}
		else
		{
			cout<<"Problem z plikiem wejsciowym n-----n"<<komenda;
			blad=ERR_FILE;
			throw(blad);
		}

		return blad;
	}

	int Merge()
	{
		tabelka1=Deserializuj(klucze.at(2));
		if(blad==0)
		{
			
			tabelka2=Deserializuj(klucze.at(3));
			if(blad!=0)
			{
			}
			else if(tabelka1.wiersze.size()==tabelka2.wiersze.size())
			{
				for(int i=0;i<tabelka1.typy.size();i++)
				{
					if(tabelka1.typy.at(i).nazwa==tabelka2.typy.at(i).nazwa)
					{
						blad=72;//taka sama nazwa.
						break;
					}
				}

				if(blad==0)
				{
					//Dopisujemy typy
					tabelka1.typy.insert(tabelka1.typy.end(),tabelka2.typy.begin(),tabelka2.typy.end());
					//Dopisujemy kolumny.
					for(int i=0;i<tabelka2.wiersze.size();i++)
					{
						tabelka1.wiersze.at(i).pola.insert(tabelka1.wiersze.at(i).pola.end(),tabelka2.wiersze.at(i).pola.begin(),tabelka2.wiersze.at(i).pola.end());
					}
					//zapisujemy:
					tabelka1.Serializuj(klucze.at(1));
				}
			}
			else
			{
				cout<<"Zła liczba wierszy n-----n"<<komenda;
				blad=ERR_NUM_ROWS;
				throw(blad);
			}
		}
		return blad;
	}

	int Join()
	{
		tabelka1=Deserializuj(klucze.at(2));
		if(blad==0)
		{
			
			tabelka2=Deserializuj(klucze.at(3));
			if(blad!=0)
			{
			}
			else if(tabelka1.typy.size()==tabelka2.typy.size())
			{
			
				for(int i=0;i<tabelka1.typy.size();i++)
				{
				
					if(tabelka1.typy.at(i).nazwa!=tabelka2.typy.at(i).nazwa)
					{
						cout<<"Zła nazwa n-----n"<<komenda;
						blad=ERR_NAME;
						throw(blad);
					}
					else if(tabelka1.typy.at(i).typ!=tabelka2.typy.at(i).typ)
					{
						cout<<"Zły typ n-----n"<<komenda;
						blad=ERR_TYPE;
						throw(blad);
					}
				}

				if(blad==0)
				{
					//Dopisujemy wiersze.
					for(int i=0;i<tabelka2.wiersze.size();i++)
					{
						tabelka1.wiersze.push_back(tabelka2.wiersze.at(i));
					}
					//zapisujemy:
					tabelka1.Serializuj(klucze.at(1));
				}
			}
			else
			{
				cout<<"Zła liczba kolumn n-----n"<<komenda;
				blad=ERR_NUM_COL;
				throw(blad);
			}
		}

		return blad;
	}

	int Agregate()
	{
		tabelka1=Deserializuj(klucze.at(2));
		Pole wynik=tabelka1.Agreguj(klucze.at(4),klucze.at(5));
		
		if(wynik.typ=="blad")
		{
			cout<<"Problem agregacji n-----n"<<komenda;
			blad=ERR_AGGR;
			throw(blad);
		}
		else
		{
			wynik.nazwa=klucze.at(3);
			//Tworzymy tabelke z wynikiem.
			vector tmp;
			tmp.push_back(wynik);
			tabelka2.typy=tmp;
			tabelka2.Dodaj(tmp);
			tabelka2.Serializuj(klucze.at(1));
		}

		return blad;
	}

	int Print()
	{
		tabelka1=Deserializuj(klucze.at(1));
		tabelka1.Wypisz();
		return blad;
	}


	int Przetworz(string polecenie)
	//Przetwarza polecenia na wektor z tokenami.
	{
		komenda=polecenie;
		polecenie.insert(polecenie.end(), 1, ' ');//spacja na koniec.
		int ile=polecenie.length();
		string teraz="";
		string tmp;
		int otwarty=0; // otwarty apostrof.
		int kod=0;

		klucze.clear();

		//Przetwarzamy polecenie litera po literze.
		for(int i=0;i<ile;i++)
		{
			if(polecenie[i]=='&')
			{
				kod=0;
				//zamieniamy na ascii.
				i++;
				while((polecenie[i]!=';')&&(i<ile))
				{
					kod=kod*10+(polecenie[i]-'0');
					i++;
				}

				if(i==ile)
				{
					cout<<"Niedokończone & n-----n"<<komenda;
					blad=ERR_AMP;
					throw(blad);
				}
				else if((kod255))
				{
					cout<<"Zły kod ASCII n-----n"<0)
				{
					klucze.push_back(teraz);
					teraz="";
				}
			}
			else
			{
				teraz.insert(teraz.end(), 1, polecenie[i]);
			}

		}

		if(otwarty==1)
		{
			cout<<"Niedokończony apostrof n-----n"<50)
			{
				cout<<"Za długa nazwa n-----n"<<komenda;
				blad=ERR_NAME_LEN;
				throw(blad);
			}
			else
			{
				for(int i=0;i='a')&&(tmp[i]='A')&&(tmp[i]='0')&&(tmp[i]<='9'))))
					{
						cout<<"Zły znak w nazwie n-----n"<<komenda;
						blad=ERR_NAME_CHAR;
						throw(blad);
					}
				}
			}
		}
		return blad;
	}


	int Zrob()
	{

			if(klucze.at(0)=="INSERT")
			{
				blad=Insert();
			}
			else if(klucze.at(0)=="CREATE")
			{
				blad=Create();
			}
			else if(klucze.at(0)=="FILTER")
			{
				blad=Filter();
			}
			else if(klucze.at(0)=="AGREGATE")
			{
				blad=Agregate();
			}
			else if(klucze.at(0)=="JOIN")
			{
				blad=Join();
			}
			else if(klucze.at(0)=="PRINT")
			{
				blad=Print();
			}
			else if(klucze.at(0)=="MERGE")
			{
				blad=Merge();
			}
			else if(klucze.at(0)=="LOAD")
			{
				blad=Load();
			}
			else
			{
				cout<<"Nieznana komenda n-----n"<<komenda;
				blad=ERR_COMM;
				throw(blad);
			}
		return blad;
	}


	int Wykonaj(string polecenie)
	{
		Przetworz(polecenie);
		
		if(blad==0)
		{
			Zrob();
		}

		return blad;
	}


};  // Koniec klasy Parser.





int main()
{
	Parser pars;
	string wiersz;

	int blad=0;
	while((blad==0)&&(getline(cin,wiersz)))
	{	
		pars.Wykonaj(wiersz);
		blad=pars.blad;
		pars.Czysc();
	}

	return 0;
}



Kod źródłowy

Mała baza danych

Program zaliczeniowy ? wersja finalna ? 2008-10-23.
Program zaliczeniowy polega na napisaniu aplikacji w C++. Celem aplikacji jest wykonywanie prostych
programów na danych.
Programem nazywamy listę kolejnych operacji na danych.
Każdy program jest postaci:
operacja 
operacja 
....
operacja 
Każda operacja jest pewnym przekształceniem plików z danymi.
Są dostępne następujące operacje:
? Operacja filtrowania
? Składania: FILTER     .
?  =, !=, >, <, >=, <=.
? Schemat pliku wynikowego jest taki sam jak źródłowego.
? Operacja dołączenia
? Składnia: MERGE   
? Operacja polega na zsumowaniu kolumn plików 1 i 2.
? Operacja powiedzie się jeśli kolumny plików 1 i 2 mają inne nazwy oraz ilość wierszy w pliku 1 i
w pliku 2 jest taka sama.
? Wynikowy plik ma wszystkie kolumny pliku 1 i wszystkie kolumny pliku 2.
? Operacja łączenia
? Składnia: JOIN   
? Operacja polega na wypisaniu do pliku docelowego najpierw zawartości pliku1 a za nim pliku2.
? Operacja jest wykonalna tylko i wyłącznie, gdy ilość kolumn pliku1 i pliku2 jest taka sama i typy
kolejnych kolumn są takie same.
? Wynikowy plik ma schemat taki sam jak plik1.
? Operacja wyliczenia
? Składnia: AGREGATE     
?  oznacza operację z listy: maksimum [MAX], minimum [MIN], suma [SUM], średnia
[AVG] (zaokrąglenie do int'a), ilość [COUNT].
? Operacja powiedzie się jeśli typ danych jest zgodny z operacją.
? Wynikowy plik ma strukturę złożoną z jednej kolumny o podanej nazwie typu int oraz zawiera
jeden wiersz z wynikiem operacji.
? Operacja dodania danych.
? Składnia: INSERT    ... 
? Operacja dodaje wiersz danych na końcu pliku danych.
? Operacja się powiedzie jeśli ilość danych zgadza się z listą kolumn oraz typu danych się
zgadzają.
? Operacja ładowania danych.
? Składnia: LOAD   
? Operacja odczytuje linia po linii dane z pliku wejściowego i dopisuje je na końcu wskazanego
pliku.
? Dane w pliku z danymi są zapisane linia po linii.
? Każda linia zawiera jeden rekord danych.? Każda linia zawiera pewną ilość pól postaci   ... 
? Każda wartość jest zapisana w formacie wartości przyjmowanym we wszystkich
komendach.
? Operacja się powiedzie jeśli ilość danych zgadza się z listą kolumn oraz typu danych się
zgadzają.
? Operacja stworzenia pustego pliku.
? Składnia: CREATE    ... 
? Operacja tworzy pusty plik o podanej strukturze.
? Dodatkowa operacja wypisania pliku.
? Składnia: PRINT 
? Operacja nie posiada żadnego wyjścia.
? Operacja powinna wypisać na standardowe wyjście zawartość danego pliku (oczywiście w
postaci zinterpretowanej).
? Dane powinny być wypisane wierszami. Pierwszy wiersz powinien być w postaci:   ...  
? Kolejne wiersze powinny zawierać kolejne wartości pól (w odpowiedniej kolejności) zapisanie w
formacie , czyli np. 'M &38; M' oznacza wartość ?M & M?.
Legenda:
?  - pole postaci 'łańcuch znaków bez znaku ' , & oraz znaku nowej linii. Znaki ', & oraz
nowej linii są zapisywane jako &;'
? Wszelkie nazwy plików, kolumn, etc. są ciągami znaków [a-z] i [A-Z] oraz [0-9] oraz znaku _ o
długości maksymalnie 50 znaków.
?  oznacza typ danych. Są dwa typy, string ? oznacza łańcuch znaków dowolnej długości oraz
int oznacza liczę 32 bitową ze znakiem.
Schemat działania aplikacji składa się z następujących kroków:
1. Wczytanie programu.
2. W pętli dla każdej komendy.
3. Wykonaj komendę.
Wykonanie każdej komendy polega na:
1. Wczytaniu plików źródłowych do pamięci.
2. Wykonanie komendy w pamięci na danych w pamięci.
3. Zapis danych do plików docelowych.
Aplikacja powinna zapisywać wszelkie dane w lokalnym katalogu. Każdy błąd w programie jest
krytyczny i powinien przerywać działanie aplikacji. Program powinien być wczytywany ze
standardowego wejścia. Wszelkie błędy odczytu/zapisu na dysk są błędami krytycznymi. Struktura
danych w plikach dowolna, wg własnych pomysłów. Optymalizacja implementacji komend nie jest
priorytetem. Można założyć, że w każdej chwili działania programu całość danych w plikach mieści się
w pamięci. W plikach nie może być wartości NULL.
Przykład programu:
CREATE tabela1 dzial string zarobki int
INSERT tabela1 tabela1 'Zarząd' '10000'
INSERT tabela1 tabela1 'Zarząd' '15000'
INSERT tabela1 tabela1 'Zarząd' '12000'
INSERT tabela1 tabela1 'IT' '4000'
INSERT tabela1 tabela1 'Administracja' '2000'
INSERT tabela1 tabela1 'IT' '4000'INSERT tabela1 tabela1 'Zarząd' '19000'
INSERT tabela1 tabela1 'IT' '5000'
FILTER tabela2 tabela1 dzial = 'Zarząd'
AGREGATE tabela3 tabela2 zarobki SUM zarobki
FILTER tabela2 tabela1 dzial = 'IT'
AGREGATE tabela4 tabela2 zarobki SUM zarobki
JOIN tabela3 tabela3 tabela4
PRINT tabela3
Po wykonaniu programu w tabeli 3 powinny być dwa wiersze. Pierwszy powinien zawierać sumę
zarobków zarządu zaś drugi sumę zarobków działu IT.
Po wypisaniu na standardowym wyjściu powinno być:
zarobki int
'56000'
'13000'

A oto rozwiązanie:

#include 
#include 
#include 
#include 
#include 
#define round(x) (x<0?ceil((x)-0.5):floor((x)+0.5))

const int ERR_FILE=1;
const int ERR_LAST_TYPE_MISSING=2;
const int ERR_BAD_TYPE=3;
const int ERR_NUM_ROWS=4;
const int ERR_NAME=5;
const int ERR_TYPE=6;
const int ERR_NUM_COL=7;
const int ERR_AGGR=8;
const int ERR_AMP=9;
const int ERR_ASCII=10;
const int ERR_APO=11;
const int ERR_NAME_LEN=12;
const int ERR_NAME_CHAR=13;
const int ERR_COMM=14;

using namespace std;

	int str2int(string wartosc)
	{
		int liczba=0;
		for(int i=0;i='0')&&(wartosc[i]<='9'))
			{
				liczba=liczba*10+(wartosc[i]-'0');
			}
		}
		return liczba;
	}

	void my_itoa(int value, string& buf, int base){
		
		int i = 30;
		
		buf = "";
		
		for(; value && i ; --i, value /= base) buf = "0123456789abcdef"[value % base] + buf;
		
	}


	string AsciiEncode(string wartosc_string)
	{
		string zwroc="";
		//zamieniamy ' & ; n
		for(int i=0;i")
		{
			if(typ=="int")
			{
				if(wartosc_int>liczba)
				{
					wynik=1;
				}
			}
			else
			{
				if(wartosc_string>wartosc)
				{
					wynik=1;
				}
			}
		}
		else if(operacja==">=")
		{
			if(typ=="int")
			{
				if(wartosc_int>=liczba)
				{
					wynik=1;
				}
			}
			else
			{
				if(wartosc_string>=wartosc)
				{
					wynik=1;
				}
			}
		}
		else if(operacja=="<=")
		{
			if(typ=="int")
			{
				if(wartosc_int<=liczba)
				{
					wynik=1;
				}
			}
			else
			{
				if(wartosc_string<=wartosc)
				{
					wynik=1;
				}
			}
		}
		else if(operacja=="=")
		{
			if(typ=="int")
			{
				if(wartosc_int==liczba)
				{
					wynik=1;
				}
			}
			else
			{
				if(wartosc_string==wartosc)
				{
					wynik=1;
				}
			}
		}
		else if(operacja=="!=")
		{
			if(typ=="int")
			{
				if(wartosc_int!=liczba)
				{
					wynik=1;
				}
			}
			else
			{
				if(wartosc_string!=wartosc)
				{
					wynik=1;
				}
			}
		}
		else if(operacja=="<")
		{
			if(typ=="int")
			{
				if(wartosc_int<liczba)
				{
					wynik=1;
				}
			}
			else
			{
				if(wartosc_string<wartosc)
				{
					wynik=1;
				}
			}
		}
		else
		{
			wynik=-1; //nieznany operator.
		}

		return wynik;
	}

	string Wypisz_typ()
	{
		return nazwa+" "+typ;
	}

	string Wypisz(int zamien)
	{
		string zwroc="";
		
		if(zamien)
		{
			zwroc=AsciiEncode(wartosc_string);
		}
		else
		{
			zwroc=wartosc_string;
		}

		
		return "'"+zwroc+"'";
	}


}; // Koniec klasy Pole.




//Klasy reprezentujace wiersze tabel

class Wiersz
{
	public:
	vector  pola;
	Wiersz(vector  dane) : pola(dane){}
	Wiersz() {}
	string Wypisz(int zamien)
	{
		string wypisz="";
		int ile=pola.size();
		for(int i=0;i0)
		{
			wypisz+=pola.at(ile-1).Wypisz(zamien);
		}


		return wypisz;
	}
}; // Koniec klasy Wiersz.




//Klasa reprezentujaca tabele z danymi.
class Tabela
{

public:
	vector  wiersze;
	vector  typy;

	void Czysc()
	{
		wiersze.clear();
		typy.clear();
	}

	Pole Agreguj(string funkcja,string kolumna)
	{
		int kol=Kolumna(kolumna);
		Pole wynik;
		int suma=0;
		int min=0;
		int max=0;
		string min_str="";
		string max_str="";

		if(kol==-1)
		{
			
			wynik.typ="blad";
		}
		else
		{
			min=wiersze.at(0).pola.at(kol).wartosc_int;
			max=min;
			min_str=wiersze.at(0).pola.at(kol).wartosc_string;
			max_str=min_str;
			

			for(int i=0;i<wiersze.size();i++)
			{
				suma+=wiersze.at(i).pola.at(kol).wartosc_int;

				//min
				if(wiersze.at(i).pola.at(kol).wartosc_int<min)
				{
					min=wiersze.at(i).pola.at(kol).wartosc_int;
				}

				if(wiersze.at(i).pola.at(kol).wartosc_stringmax)
				{
					max=wiersze.at(i).pola.at(kol).wartosc_int;
				}

				if(wiersze.at(i).pola.at(kol).wartosc_string>max_str)
				{
					max_str=wiersze.at(i).pola.at(kol).wartosc_string;
				}
			}


			if(funkcja=="COUNT")
			{
				wynik.wartosc_int=wiersze.size();
				my_itoa(wiersze.size(),wynik.wartosc_string,10);
				wynik.typ="int";
			}
			else if(funkcja=="MAX")
			{
				wynik.typ=typy.at(kol).typ;
				if(wynik.typ=="int")
				{
					wynik.wartosc_int=max;
					my_itoa(max,wynik.wartosc_string,10);
				}
				else
				{
					wynik.wartosc_string=max;
				}
				
			}
			else if(funkcja=="MIN")
			{
				wynik.typ=typy.at(kol).typ;
				if(wynik.typ=="int")
				{
					wynik.wartosc_int=min;
					my_itoa(max,wynik.wartosc_string,10);
				}
				else
				{
					wynik.wartosc_string=min;
				}
				
			}
			else if((funkcja=="AVG")&&(typy.at(kol).typ=="int"))
			{
				wynik.typ="int";
				wynik.wartosc_int=round(suma/wiersze.size());
				my_itoa(wynik.wartosc_int,wynik.wartosc_string,10);
			}
			else if((funkcja=="SUM")&&(typy.at(kol).typ=="int"))
			{
				wynik.typ="int";
				wynik.wartosc_int=suma;
				my_itoa(wynik.wartosc_int,wynik.wartosc_string,10);
			}
			else
			{
				wynik.typ="blad";//blad.
			}

			
		}

		return wynik;
	}

	int Kolumna(string nazwa)
	//zwraca numer kolumny.
	{
		int znalezione=-1; //blad.
		for(int i=0;i<typy.size();i++)
		{
			if(typy.at(i).nazwa==nazwa)
			{
				znalezione=i;
				break;
			}
		}
		return znalezione;
	}

	int Filtruj(string kolumna, string operacja, string wartosc)
	{
		int blad=0;
		int kol=Kolumna(kolumna);

		if(kol!=-1)
		{
			for(int i=0;i<wiersze.size();i++)
			{
				
				int odp=wiersze.at(i).pola.at(kol).Porownaj(operacja,wartosc);
				if(odp==-1)
				{
					blad=61; //zly operator.
					break;
				}
				else if(odp==0)
				{
					wiersze.erase(wiersze.begin()+i,wiersze.begin()+i+1);
					i=i-1;
				}
			}
		}
		else
		{
			blad=51; //nie ma takiej kolumny.
		}

		return blad;
	}

	int Serializuj(string nazwa)
	{
		int blad=0;
		fstream plik;
		plik.open((nazwa+"_data.txt").c_str(),ios::out);
		if(plik.good())
		{

			plik<<"CREATE "<<nazwa<<" ";
			//zapisujemy.
			//Najpierw typy.
			for(int i=0;i<typy.size();i++)
			{
				plik<<"'"<<typy.at(i).nazwa<<"' "<<typy.at(i).typ<<" ";
			}
			plik<<"n";

			//Teraz dane.
			for(int i=0;i<wiersze.size();i++)
			{
				plik<<"INSERT "<<nazwa<<" "<<nazwa<<" "<<wiersze.at(i).Wypisz(1)<<"n";
			}

			plik.close();
		}
		else
		{
			blad=41;//nie ma dostepu do pliku.
		}

		return blad;
	}

	int Dodaj(vector  pola)
	{
		Wiersz w;
		w.pola=pola;
		wiersze.push_back(w);
		return 0;
	}

	int Utworz(vector  typ,int poczatek)
	{
		int blad=0;

		for(int i=poczatek;i<typ.size();i+=2)
		{
			typy.push_back(Pole(typ.at(i),typ.at(i+1),"1"));
		}
		
		return blad;
	}

	int Wstaw(vector dane,int poczatek)///////////////////////
	{
		int blad=0;

		vector tmp; 
		if(dane.size()-poczatek==typy.size())
		{
			for(int i=poczatek;i<dane.size();i++)
			{
				Pole tymczas=Pole(typy.at(i-poczatek).nazwa,typy.at(i-poczatek).typ,dane.at(i));
				tmp.push_back(tymczas);
				
			}
			
			if(blad==0)
			{
				Dodaj(tmp);
			}
		}
		else
		{
			blad=11; //Niepoprawna ilosc danych
		}
		return blad;
	}

	void Wypisz()
	{
		//Wypisujemy typy
		for(int i=0;i<typy.size();i++)
		{
			cout<<typy.at(i).Wypisz_typ()<<" ";
		}
		cout<<"n";

		//Teraz wiersze
		int ile=wiersze.size();
		for(int i=0;i<ile;i++)
		{
			cout<<wiersze.at(i).Wypisz(0)<<"n";
		}
	}

}; // Koniec klasy tabela.




class Parser
{
private:
	vector  klucze;
	string komenda;
public:
	int blad;		//Kod bledu.
	Tabela tabelka1;
	Tabela tabelka2;

	Parser() : blad(0){}

	void Czysc()
	{
		tabelka1.Czysc();
		tabelka2.Czysc();
		klucze.clear();
		komenda="";
	}

	int Wczytuj(string nazwa)
	{
		fstream plik;
		plik.open((nazwa+"_data.txt").c_str(),ios::in);
		if(plik.good())
		{
			string dane;
			while(getline(plik,dane))
			{
				Wykonaj(dane);
			}
			
			plik.close();
		}
		else
		{
			blad=ERR_FILE;
			cout<<"Problem z plikiem wejsciowym n-----n"<<komenda;
			throw(ERR_FILE);
		}
		
		return blad;
	}

	Tabela Deserializuj(string nazwa)
	{
		Parser pars;
		blad=pars.Wczytuj(nazwa);
		return pars.tabelka1;
	}

	int Insert()
	{
		Nazwa(1);
		Nazwa(2);
		tabelka1=Deserializuj(klucze.at(2));
		blad=tabelka1.Wstaw(klucze,3);

		if(blad==0)
		{
			blad=tabelka1.Serializuj(klucze.at(1));
		}

		return blad;
	}

	int Create()
	{
		for(int i=2;iklucze.size()-1)
			{
				cout<<"Brak typu ostatnigon-------n"<<komenda;
				blad=ERR_LAST_TYPE_MISSING;
				throw(blad);
			}
			else if((klucze.at(i+1)!="string")&&(klucze.at(i+1)!="int"))
			{
				cout<<"Nieprawidlowy typn-------n"<<komenda;
				blad=ERR_BAD_TYPE; //Nieprawidlowy typ.
				throw(blad);
			}
		}

		if(blad==0)
		{
			blad=tabelka1.Utworz(klucze,2);
		}

		if(blad==0)
		{
			blad=tabelka1.Serializuj(klucze.at(1));
		}


		return blad;
	}

	int Filter()
	{
		//Filtruje.
		//Czytamy tabele do przefiltrowania
		tabelka1=Deserializuj(klucze.at(2));
		//Usuwamy niepasujace wiersze
		blad=tabelka1.Filtruj(klucze.at(3),klucze.at(4),klucze.at(5));
		//Zapisujemy:
		blad=tabelka1.Serializuj(klucze.at(1));
		return blad;
	}

	int Load()
	{
		//Laduje dane.
		Parser parserek;
		string wiersz;
		//Otwieramy plik:
		fstream plik;
		tabelka1=Deserializuj(klucze.at(2));
		if (blad==0)
		{
			plik.open(klucze.at(3).c_str(),ios::in);
			if(plik.good())
			{
				
				//Zwalimy robote na juz napisana funkcje:
				while((blad==0)&&(getline(plik,wiersz)))
				{
					blad=parserek.Przetworz(wiersz);

					if(blad==0)
					{
						blad=tabelka1.Wstaw(parserek.klucze,0);
					}
				}

				if(blad==0)
				{
					blad=tabelka1.Serializuj(klucze.at(1));
				}
			}
			else
			{
				cout<<"Problem z plikiem wejsciowym n-----n"<<komenda;
				blad=ERR_FILE;
				throw(blad);
			}
		}
		else
		{
			cout<<"Problem z plikiem wejsciowym n-----n"<<komenda;
			blad=ERR_FILE;
			throw(blad);
		}

		return blad;
	}

	int Merge()
	{
		tabelka1=Deserializuj(klucze.at(2));
		if(blad==0)
		{
			
			tabelka2=Deserializuj(klucze.at(3));
			if(blad!=0)
			{
			}
			else if(tabelka1.wiersze.size()==tabelka2.wiersze.size())
			{
				for(int i=0;i<tabelka1.typy.size();i++)
				{
					if(tabelka1.typy.at(i).nazwa==tabelka2.typy.at(i).nazwa)
					{
						blad=72;//taka sama nazwa.
						break;
					}
				}

				if(blad==0)
				{
					//Dopisujemy typy
					tabelka1.typy.insert(tabelka1.typy.end(),tabelka2.typy.begin(),tabelka2.typy.end());
					//Dopisujemy kolumny.
					for(int i=0;i<tabelka2.wiersze.size();i++)
					{
						tabelka1.wiersze.at(i).pola.insert(tabelka1.wiersze.at(i).pola.end(),tabelka2.wiersze.at(i).pola.begin(),tabelka2.wiersze.at(i).pola.end());
					}
					//zapisujemy:
					tabelka1.Serializuj(klucze.at(1));
				}
			}
			else
			{
				cout<<"Zła liczba wierszy n-----n"<<komenda;
				blad=ERR_NUM_ROWS;
				throw(blad);
			}
		}
		return blad;
	}

	int Join()
	{
		tabelka1=Deserializuj(klucze.at(2));
		if(blad==0)
		{
			
			tabelka2=Deserializuj(klucze.at(3));
			if(blad!=0)
			{
			}
			else if(tabelka1.typy.size()==tabelka2.typy.size())
			{
			
				for(int i=0;i<tabelka1.typy.size();i++)
				{
				
					if(tabelka1.typy.at(i).nazwa!=tabelka2.typy.at(i).nazwa)
					{
						cout<<"Zła nazwa n-----n"<<komenda;
						blad=ERR_NAME;
						throw(blad);
					}
					else if(tabelka1.typy.at(i).typ!=tabelka2.typy.at(i).typ)
					{
						cout<<"Zły typ n-----n"<<komenda;
						blad=ERR_TYPE;
						throw(blad);
					}
				}

				if(blad==0)
				{
					//Dopisujemy wiersze.
					for(int i=0;i<tabelka2.wiersze.size();i++)
					{
						tabelka1.wiersze.push_back(tabelka2.wiersze.at(i));
					}
					//zapisujemy:
					tabelka1.Serializuj(klucze.at(1));
				}
			}
			else
			{
				cout<<"Zła liczba kolumn n-----n"<<komenda;
				blad=ERR_NUM_COL;
				throw(blad);
			}
		}

		return blad;
	}

	int Agregate()
	{
		tabelka1=Deserializuj(klucze.at(2));
		Pole wynik=tabelka1.Agreguj(klucze.at(4),klucze.at(5));
		
		if(wynik.typ=="blad")
		{
			cout<<"Problem agregacji n-----n"<<komenda;
			blad=ERR_AGGR;
			throw(blad);
		}
		else
		{
			wynik.nazwa=klucze.at(3);
			//Tworzymy tabelke z wynikiem.
			vector tmp;
			tmp.push_back(wynik);
			tabelka2.typy=tmp;
			tabelka2.Dodaj(tmp);
			tabelka2.Serializuj(klucze.at(1));
		}

		return blad;
	}

	int Print()
	{
		tabelka1=Deserializuj(klucze.at(1));
		tabelka1.Wypisz();
		return blad;
	}


	int Przetworz(string polecenie)
	//Przetwarza polecenia na wektor z tokenami.
	{
		komenda=polecenie;
		polecenie.insert(polecenie.end(), 1, ' ');//spacja na koniec.
		int ile=polecenie.length();
		string teraz="";
		string tmp;
		int otwarty=0; // otwarty apostrof.
		int kod=0;

		klucze.clear();

		//Przetwarzamy polecenie litera po literze.
		for(int i=0;i<ile;i++)
		{
			if(polecenie[i]=='&')
			{
				kod=0;
				//zamieniamy na ascii.
				i++;
				while((polecenie[i]!=';')&&(i<ile))
				{
					kod=kod*10+(polecenie[i]-'0');
					i++;
				}

				if(i==ile)
				{
					cout<<"Niedokończone & n-----n"<<komenda;
					blad=ERR_AMP;
					throw(blad);
				}
				else if((kod255))
				{
					cout<<"Zły kod ASCII n-----n"<0)
				{
					klucze.push_back(teraz);
					teraz="";
				}
			}
			else
			{
				teraz.insert(teraz.end(), 1, polecenie[i]);
			}

		}

		if(otwarty==1)
		{
			cout<<"Niedokończony apostrof n-----n"<50)
			{
				cout<<"Za długa nazwa n-----n"<<komenda;
				blad=ERR_NAME_LEN;
				throw(blad);
			}
			else
			{
				for(int i=0;i='a')&&(tmp[i]='A')&&(tmp[i]='0')&&(tmp[i]<='9'))))
					{
						cout<<"Zły znak w nazwie n-----n"<<komenda;
						blad=ERR_NAME_CHAR;
						throw(blad);
					}
				}
			}
		}
		return blad;
	}


	int Zrob()
	{

			if(klucze.at(0)=="INSERT")
			{
				blad=Insert();
			}
			else if(klucze.at(0)=="CREATE")
			{
				blad=Create();
			}
			else if(klucze.at(0)=="FILTER")
			{
				blad=Filter();
			}
			else if(klucze.at(0)=="AGREGATE")
			{
				blad=Agregate();
			}
			else if(klucze.at(0)=="JOIN")
			{
				blad=Join();
			}
			else if(klucze.at(0)=="PRINT")
			{
				blad=Print();
			}
			else if(klucze.at(0)=="MERGE")
			{
				blad=Merge();
			}
			else if(klucze.at(0)=="LOAD")
			{
				blad=Load();
			}
			else
			{
				cout<<"Nieznana komenda n-----n"<<komenda;
				blad=ERR_COMM;
				throw(blad);
			}
		return blad;
	}


	int Wykonaj(string polecenie)
	{
		Przetworz(polecenie);
		
		if(blad==0)
		{
			Zrob();
		}

		return blad;
	}


};  // Koniec klasy Parser.





int main()
{
	Parser pars;
	string wiersz;

	int blad=0;
	while((blad==0)&&(getline(cin,wiersz)))
	{	
		pars.Wykonaj(wiersz);
		blad=pars.blad;
		pars.Czysc();
	}

	return 0;
}



Lab obiektowy Zad 3

Zadanie numer 3 laboratorium programowania obiektowego:

Laboratorium programowania obiektowego
Zadanie zaliczeniowe 3
Homer Simpson pracuje w elektrowni atomowej. W zajmowanym przez niego pokoju zacięły się drzwi. Jest godzina 16. Homer musi wyjść z pracy za 10 minut, jeśli chce zdążyć do domu na transmisję meczu.
Pokój ma rozmiary 20 na 20 (metrów) - składa się z 400 pól rozmiaru 1 na 1. Dla uproszczenia zakładamy, że wszystko, co się w nim znajduje, w tym także Homer, zajmuje powierzchnię 1 metr na 1 metr. Położenie przedmiotów w pokoju określać będziemy, podając jako współrzędne parę liczb 1..20. Ściany okalające pomieszczenie mają współrzędne (1,?), (20,?), (?,1), (?,20) gdzie ? reprezentuje dowolną liczbę z przedziału 1..20. Wyjątkiem od powyższej reguły jest pole o współrzędnych (1,10), na którym znajdują się (zatrzaśnięte) drzwi.
Na każdym polu może się znajdować tylko jeden przedmiot. 
We wszystkich przypadkach, w których będziemy mówili o odległości dwu punktów, będziemy mieli na myśli odległość liczoną w tzw. metryce miejskiej, w której odległość punktów (a,b) i (c,d) jest równa abs(a-c)+abs(b-d). 
Oprócz ścian zewnętrznych, drzwi i Homera w polu gry znajdują się ściany wewnętrzne, skrzynie, puszki piwa, pączki oraz trzy rodzaje materiałów rozszczepialnych: Mars, Jowisz i Saturn.
Homer na zawartość pomieszczenia może wpływać na dwa sposoby - przesuwając znajdujące się w nim przedmioty oraz wysadzając je. Przesuwać może dowolne przedmioty z wyjątkiem ścian, drzwi, puszek piwa i pączków.  Każdy przedmiot, po przesunięciu, przenosi się na sąsiednie pole, o ile jest puste.
Oprócz możliwości przesuwania przedmiotów w pomieszczeniu, Homer może powodować eksplozje. Każdy wybuch, do jakiego dojdzie, ma określoną siłę, wyrażoną liczbą całkowitą większą od zera. Przedmioty albo są całkowicie odporne na wybuchy, albo mają wytrzymałość wyrażoną liczbą całkowitą, również większą od zera. Wybuch o sile N niszczy wszystko w odległości N od wybuchającego przedmiotu (lub przedmiotów), czego wytrzymałość jest mniejsza bądź równa N. Pączki, jako jedyne, po znalezieniu się w polu wybuchu same wybuchają (z właściwą sobie siłą), a więc mogą powodować wybuchy łańcuchowo.
Wytrzymałość na wybuchy przedmiotów (w tym także wytrzymałość Homera oraz materiałów rozszczepialnych) jest równa 1 za wyjątkiem ścian zewnętrznych, które są niezniszczalne oraz ścian wewnętrznych i drzwi, dla których jest równa 2. 
Każdy z materiałów rozszczepialnych ma pewne cechy szczególne: 

*	Mars, gdy znajdzie się w polu wybuchu o sile większej bądź równej 1, ulega zniszczeniu, ale nie wybucha. 
*	Po zetknięciu dwu lub więcej porcji Jowiszu (tj. umieszczeniu ich na polach odległych o 1) i tym samym przekroczeniu masy krytycznej, po 5 sekundach wybuchają one z siłą 2. 
*	Przekroczenie masy krytycznej Saturnu i wybuch po 5 sekundach z siłą 2 następuje po zetknięciu ze sobą 3 lub więcej jego porcji. 
*	Jeżeli porcja Saturnu znajdzie się w polu wybuchu o sile większej bądź równej 1, przekształca się w porcję Jowiszu, która w wyniku tego wybuchu nie zostanie zniszczona. Może ona wejść w reakcję z sąsiadującymi pierwiastami lub zostać później wykorzystana przez Homera. 
*	Po zetknięciu jednej porcji Jowiszu i jednej porcji Saturnu obie się dematerializują (znikają).

Homer może również powodować wybuchy przy użyciu eksplodujących pączków. Ma ich przy sobie 5 sztuk, jest ich też trochę rozrzuconych po pomieszczeniu. By podnieść pączek, wystarczy wejść na pole, na którym się znajduje. 
Pączek, który jest w rękach Homera, może zostać odbezpieczony i porzucony przez niego. Jeśli tak się stanie, wybuchnie z siłą 1 w 20 sekund po porzuceniu. 
Pączek odbezpieczony i porzucony przez Homera może zostać przez niego podniesiony i zabezpieczony przez ponowne wejście na pole, na którym się znajduje.
Czas gry wynosi 10 wirtualnych minut. Homer na przejście z jednego pola na drugie potrzebuje 1 sekundy. Wyjątkiem są pola zawierające puszkę piwa - Homer spędza na nich 30 sekund pijąc piwo. Ponieważ jest to czas wirtualny, gracz nie musi czekać pół minuty, a jedynie odpowiedni licznik zostaje zwiększony. Po wypiciu, Homer może kontynuować pracę, a puszka piwa znika. Przepchnięcie czegokolwiek na sąsiednie pole zajmuje Homerowi 5 sekund. Jesli Homer nie porusza się, czas nie płynie.
Wybuch następuje w chwili, gdy zajdą okoliczności wywołujące go i trwa 0 sekund, podobnie reakcje pierwiastków rozszczepialnych.
Gdyby w jakiejś chwili były okoliczności pozwalające na zajście kilku zdarzeń, wówczas najwyższy priorytet ma połączenie się kilku porcji pierwiastka i eksplozja na skutek osiągnięcia masy krytycznej. Jeżeli może zajść jedno z kilku zjawisk o tym samym priorytecie, wybór między nimi jest dowolny.
Celem gry jest zniszczenie drzwi i opuszczenie przez nie pomieszczenia w czasie nie dłuższym, niż 10 minut. Początkowy stan pokoju można przyjąć dowolny.
Użytkownik steruje Homerem, wpisując polecenia w postaci tekstowej, np. ?g? oznaczające ?przejdź w górę? itp. Jeżeli na polu w kierunku, w którym chcemy przesunąć Homera, znajduje się przedmiot przesuwalny, oprócz przemieszczenia naszego bohatera nastąpi przesunięcie przedmiotu o jedno pole, oczywiście pod warunkiem, że miejsce na które przedmiot przesuwamy jest puste. Wejście na pole, na którym znajduje się pączek, powoduje zabranie go. 
Napisz w języku Java grę opartą na powyższym scenariuszu. Program powinien być zapisany obiektowo, w szczególności powinien umożliwiać łatwe dodawanie nowych rodzajów przedmiotów a także modyfikowanie parametrów istniejących.
Program może wczytywać polecenia gracza ze standardowego wejścia i wypisywać stan planszy na standardowe wyjście.

A oto rozwiązanie:

Lab obbiektowy 3

Programowanie obiektowe zadanie 2

Zadanie zaliczeniowe z laboratorium programowania obiektowego

Laboratorium programowania obiektowego
Zadanie zaliczeniowe 2
termin oddawania rozwiazan: 9 czerwca 2008

Bezszachy sa wariantem gry w szachy. Gra prowadzona jest przez dwoch graczy,
nazywanych dalej bialym i czarnym, na szachownicy 8 na 8, za pomoca bierek
szachowych. Poczatkowe ustawienie figur na szachownicy jest takie samo, jak
w zwyklych szachach. Pionkow w bezszachach nie uzywa sie.

Gracze wykonuja na przemian po jednym ruchu, zaczynajac od gracza bialego.

Figury bezszachowe poruszaja sie po szachownicy tak samo, jak szachowe.
Jedynym wyjatkiem jest brak mozliwosci roszady.

W bezszachach, w odroznieniu od szachow, nie istnieja pojecia szachu i mata.
Zabicie krola nie powoduje zakonczenia gry.

Gra konczy sie zwyciestwem jednego z graczy, gdy uda mu sie zabic wszystkie
bierki przeciwnika. Gra konczy sie remisem, gdy gracz nie moze wykonac
zadnego legalnego ruchu, choc pozostaly mu bierki. Remis oglaszamy rowniez,
gdy gracze wykonaja 1000 ruchow (po 500 ruchow kazdego gracza).

Napisz w C++ program, ktory przeprowadzi partie bezszachow miedzy para
graczy:

* losowym, ktory za kazdym razem losowo wybiera jeden z dozwolonych w danej
chwili ruchow. Wybor kazdego z legalnych ruchow powinien byc rownie
prawdopodobny. Jesli np. gracz ma dwie bierki i jedna z nich moze wykonac
10 legalnych ruchow, a druga 5, to prawdopodobienstwo ruchu pierwsza bierka
powinno byc dwa razy wieksze, niz druga.

* leniwym, ktory sposrod bierek, ktorymi moze sie ruszyc wybiera ta, ktora
znajduje sie najblizej jego krawedzi szachownicy (wiersz pierwszy dla bialego,
osmy dla czarnego). Jesli wybrana bierka gracz moze wykonac bicie, robi to,
jesli nie, wykonuje nia losowy ruch.

Program powinien ruszac sie za obu graczy i, po kazdym ruchu, wypisywac
na wyjscie stan szachownicy. Na zakonczenie partii nalezy wypisac informacje
o wyniku - kto wygral, czy byl remis.

Informacje dla osob, ktore nie znaja zasad gry w szachy:

Poslugujemy sie piecioma rodzajami figur:

* wieza - moze sie przesuwac po wierszu lub kolumnie szachownicy
* goniec - moze sie przesuwac po przekatnych szachownicy
* hetman - moze wykonywac ruchy takie, jak wieza lub goniec
* krol - moze wykonac ruch na jedno z sasiednich pol, takze po przekatnej
* skoczek - moze wykonac ruch, zmieniajac numer wiersza o 2 a kolumny o 1,
  lub na odwrot. Jest jedyna bierka, ktora moze "przeskoczyc" nad innymi.

Jesli na polu, na ktore przestawiamy bierke, jest bierka przeciwnika, zabijamy
ja, czyli zdejmujemy z szachownicy.

Poczatkowo na szachownicy w pierwszym wierszu sa figury gracza bialego,
kolejno: wieza, skoczek, goniec, hetman, krol, goniec, skoczek, wieza.
W ostatnim wierszu znajduja sie figury gracza czarnego, w tej samej
kolejnosci.

Uwaga 1: zadanie trzeba rozwiazac obiektowo. Nalezy unikac powtarzania kodu
lub pisania wielokrotnie podobnych fragmentow.

Uwaga 2: hierarchia klas powinna umozliwiac latwe rozszerzenie o nowe
rodzaje bierek i graczy.

Pytania do tresci zadania prosze kierowac na adres:

zaroda@mimuw.edu.pl

A oto rozwiązanie:

#include 
#include 
#include 
#include 
#include 



using namespace std;

class Pionek;
class Gracz;


//struktura przechowujaca mozliwy ruch.
typedef struct Ruch{
	Pionek* pionek;
	int x; //Wiersz docelowy
	int y; //Kolumna docelowa
	int bicie; //Czy bicie.
} Ruch;

//dlugosc boku planszy
#define ROZMIAR_PLANSZY 8




//Nadklasa dla Gracza.
class Gracz {
	protected:
		char nawias_start;	//Poczatek nawiasu zaznaczajacego gracza
		char nawias_stop;	// Koniec tegoz.
	
	public:
		vector Pionki;	//Pionki gracza pozostajace na planszy
		string nazwa_gracza;	//Nazwa gracza.
		void Usun(Pionek*);		//Usuwa pionek z listy pionkow.
		void inicjuj(string nazwa_gracza,char nawias_start,char nawias_stop);
		virtual int Ruch(Pionek* plansza[ROZMIAR_PLANSZY][ROZMIAR_PLANSZY]);	//Rusza graczem
		string Wypisz(string pionek);									// Wypisuje pionek gracza
		int WykonajRuch(struct Ruch rusz,Pionek* plansza[ROZMIAR_PLANSZY][ROZMIAR_PLANSZY]);	// Fizycznie wykonuje ruch
};


//nadklasa dla pionka
class Pionek
{
	public:
		int x; //wiersz planszy
		int y;//kolumna planszy
		int WyprobujRuch(vector* ruchy,Pionek* plansza[ROZMIAR_PLANSZY][ROZMIAR_PLANSZY],int x,int y);
		Gracz* gracz;
		virtual vector MozliweRuchy(Pionek* plansza[ROZMIAR_PLANSZY][ROZMIAR_PLANSZY]);	//Mozliwe ruchy pionka
		void Zbij();	//Usuwa pionek
		void inicjuj(int i,int j,Gracz* gracz);
		string nazwa;
		virtual string Wypisz();
};

// klasa główna - gra
class Gra 
{

	private:
		int numer_ruchu;
		int ograniczenie;		//Ograniczenie na ilosc ruchow.
		Pionek* plansza[ROZMIAR_PLANSZY][ROZMIAR_PLANSZY];
		Gracz* gracz1;
		Gracz* gracz2;
	public:
		Gra(Gracz* gracz1,Gracz* gracz2,int ograniczenie)
		{
			this->gracz1=gracz1;
			this->gracz2=gracz2;
			this->ograniczenie=ograniczenie;

			for(int i=0;i<ROZMIAR_PLANSZY;i++)
			{
				for(int j=0;j<ROZMIAR_PLANSZY;j++)
				{
					plansza[i][j]=NULL;
				}
			}
			
			// umieszczanie pionkow na planszy.
			
			for(unsigned int i=0;i Pionki.size(); i++)
			{
				plansza[gracz1->Pionki.at(i)->x][gracz1->Pionki.at(i)->y]=gracz1->Pionki.at(i);
			}

			for(unsigned int i=0;i Pionki.size(); i++)
			{
				plansza[gracz2->Pionki.at(i)->x][gracz2->Pionki.at(i)->y]=gracz2->Pionki.at(i);
			}
			//pionki umieszczone.
			
		}
		int Ruch();
		void Wypisz(); //Wypisuje stan planszy
};



// Metody GRA

	int Gra::Ruch()
			{

				cout << "Ruch " << numer_ruchu << ": n";

				if((numer_ruchu Ruch(plansza) && gracz2->Ruch(plansza))
				{
					Wypisz();
					numer_ruchu++;

					if(gracz1->Pionki.size()==0)
					{
						//wygral gracz 2.
						cout << "Wygral gracz '" <nazwa_gracza <Pionki.size()==0)
					{
						//wygral gracz 1.
						cout << "Wygral gracz '" <nazwa_gracza << "' Gratulacje! n";
						return 0;
					}
					else
					{
						//Gramy dalej
						return 1;
					}
				}
				else
				{
					cout << "REMIS!! n";
					return 0;
				}
			}

			
	void Gra::Wypisz() //Wypisuje stan planszy
			{
				int i,j,k;
				
				cout << "nn";
				
				//gorna sciana planszy
				cout << "#";
				for(k=0;k<ROZMIAR_PLANSZY;k++)
				{
					cout <<"##"<< k+1 <<"###";
				}
				
				
				//kolejne wiersze planszy
				for (i=0;i<ROZMIAR_PLANSZY;i++)
				{
					cout << "n#";
					for(k=0;k<ROZMIAR_PLANSZY;k++)
					{
						cout <<"     #";
					}
					cout << "n"<< (char)('A'+i);
					
					for(j=0;j<ROZMIAR_PLANSZY;j++)
					{
						cout<<' ';
						
						if(plansza[i][j]!=NULL)
						{
							//jest tu jakis pionek.
							cout <Wypisz();
						}
						else
						{
							cout << "   ";
						}

						cout << " #";
					}
					
					cout << "n#";
					for(k=0;k<ROZMIAR_PLANSZY;k++)
					{
						cout <<"     #";
					}

					cout << 'n';
					
					for(k=0;k<ROZMIAR_PLANSZY;k++)
					{
						cout <<"######";
					}
					cout << "#";
				}
				
				cout <nazwa_gracza=nazwa_gracza;
			this->nawias_start=nawias_start;
			this->nawias_stop=nawias_stop;
		}

	int Gracz::WykonajRuch(struct Ruch rusz,Pionek* plansza[ROZMIAR_PLANSZY][ROZMIAR_PLANSZY])
			{	//przesuwa pionek, na razie bez bicia.
				
				string bicie="";

				if(plansza[rusz.x][rusz.y]!=NULL)
				{
					//Cos tu jest. Zakladam ze bicie.
					plansza[rusz.x][rusz.y]->Zbij();
					bicie=" (bicie)";
				}

				cout << "Gracz '"<nazwa_gracza <<"': "<nazwa <<"  z [" <x) <y+1 <<"] na [" << (char)('A'+rusz.x) << rusz.y+1 <<"]"<< bicie <x][rusz.pionek->y]=NULL;
				rusz.pionek->x=rusz.x;
				rusz.pionek->y=rusz.y;

				return 1;
			}

	void Gracz::Usun(Pionek* pionek)
			{	//Usuwa pionek z listy.
				unsigned int i=0;

				while((i Pionki.size())&&(this->Pionki.at(i)!=pionek))
				{
					i++;
				}

				if(i Pionki.size())
				{
					//znaleziono
					//usuwamy.
					this->Pionki.erase(this->Pionki.begin()+i,this->Pionki.begin()+i+1);
				}
			}


	string Gracz::Wypisz(string pionek)
			{
				string wynik="";
				wynik=nawias_start+pionek+nawias_stop;
				return wynik;
			}


//Koniec metod GRACZ
//METODY PIONEK
	vector Pionek::MozliweRuchy(Pionek* plansza[ROZMIAR_PLANSZY][ROZMIAR_PLANSZY])
	{
		vector zwroc;
		//Bez tego linker g++ się sypie.
		return zwroc;
	}

	void Pionek::inicjuj(int i,int j,Gracz* gracz)
		{
			this->x=i;
			this->y=j;
			this->gracz=gracz;
			gracz->Pionki.push_back(this);
		}
	string Pionek::Wypisz()
		{
			return gracz->Wypisz("|");
		}

	void Pionek::Zbij()
		{
			//Jak nietrudno się domyślić zbija pionek.
			this->gracz->Usun(this);
		}


	int Pionek::WyprobujRuch(vector* ruchy,Pionek* plansza[ROZMIAR_PLANSZY][ROZMIAR_PLANSZY],int i,int j)
	{

		Ruch gdzie;
 		if((i>=ROZMIAR_PLANSZY)||(i=ROZMIAR_PLANSZY)||(jpush_back(gdzie);
			return 1;
	
		}
		else if(plansza[i][j]->gracz!=this->gracz)
		{
			//Obcy gracz
			gdzie.pionek=this;
			gdzie.x=i;
			gdzie.y=j;
			gdzie.bicie=1;
			ruchy->push_back(gdzie);
			return 0;
		}
		else
		{
			return 0;
		}

	}

//Koniec metod pionek.
// Wszystkie nadklasy zostaly zadeklarowane. Teraz zrobimy podklasy.
// Najpierw gracze.

	class Losowy: public Gracz
	{
		public:
		int Ruch(Pionek* plansza[ROZMIAR_PLANSZY][ROZMIAR_PLANSZY]);
		Losowy(string nazwa_gracza,char nawias_start,char nawias_stop)
		{
			inicjuj(nazwa_gracza,nawias_start,nawias_stop);
		}
	};

	int Losowy::Ruch(Pionek* plansza[ROZMIAR_PLANSZY][ROZMIAR_PLANSZY])
	{
		vector tmp;
		vector mozliwe_ruchy;

		for(unsigned int i=0;i Pionki.size(); i++)
		{		
			tmp=this->Pionki.at(i)->MozliweRuchy(plansza);
			mozliwe_ruchy.insert(mozliwe_ruchy.end(),tmp.begin(),tmp.end());
			tmp.clear();
		}

		

		if(mozliwe_ruchy.size()>0)
		{
			//jesli sa ruchy do wykonania.
			int losowa = rand()%(int)mozliwe_ruchy.size();
			return WykonajRuch(mozliwe_ruchy[losowa],plansza);
		}
		else
		{
			return 0;
		}
	}




	class Leniwy: public Gracz
	{
		public:
		int krawedz ; // Krawedz okreslana jako 'nalezaca'  do gracza.
		int Ruch(Pionek* plansza[ROZMIAR_PLANSZY][ROZMIAR_PLANSZY]);
		Leniwy(string nazwa_gracza,char nawias_start,char nawias_stop,int krawedz)
		{
			this->krawedz=krawedz;
			inicjuj(nazwa_gracza,nawias_start,nawias_stop);
		}
	};

	int Leniwy::Ruch(Pionek* plansza[ROZMIAR_PLANSZY][ROZMIAR_PLANSZY])
	{
		int najblizej = ROZMIAR_PLANSZY+1;		//Odleglosc do najblizszej bierki.
		Pionek* najblizszy = NULL;				//Najblizsza bierka
		vector tmp;
		vector mozliwe_ruchy;
		int odleglosc;

		for(unsigned int i=0;i Pionki.size(); i++)
		{		
			tmp=this->Pionki.at(i)->MozliweRuchy(plansza);
			odleglosc=this->krawedz-(Pionki.at(i)->x);

			if(odleglosc0)&&(odlegloscMozliweRuchy(plansza); //Jego mozliwe ruchy.
			unsigned int i=0;
			while((i<tmp.size())&&(tmp.at(i).bicie==0))
			{
				i++;
			}

			if(i<tmp.size()) //Znalezlismy ruch z biciem.
			{
				return WykonajRuch(tmp.at(i),plansza);
			}
			else	// Nie ma bicia, ale losowy ruch.
			{
				int losowa = rand()%(int)tmp.size();
				return WykonajRuch(tmp[losowa],plansza);
			}
		}
		else
		{
			return 0;
		}
	}



// Teraz pionki.



	class Wieza:public Pionek
	{
		public:
		vector MozliweRuchy(Pionek* plansza[ROZMIAR_PLANSZY][ROZMIAR_PLANSZY]);
		string Wypisz();
		Wieza (int i,int j,Gracz* gracz)
		{
			inicjuj(i,j,gracz);
			this->nazwa="Wieża";
		}
	};

	vector Wieza::MozliweRuchy(Pionek* plansza[ROZMIAR_PLANSZY][ROZMIAR_PLANSZY])
	{
		vector ruchy;
		int i;

		//Skaczemy po wierszach
		i=y+1;
		while(WyprobujRuch(&ruchy,plansza,x,i)==1)
		{
			i++;
		}
		i=y-1;
		while(WyprobujRuch(&ruchy,plansza,x,i)==1)
		{
			i=i-1;
		}
		//Skaczemy po kolumnach
		i=x+1;
		while(WyprobujRuch(&ruchy,plansza,i,y)==1)
		{
			i++;
		}
		i=x-1;
		while(WyprobujRuch(&ruchy,plansza,i,y)==1)
		{
			i=i-1;
		}

		return ruchy;
	}

	string Wieza::Wypisz()
	{
		return gracz->Wypisz("W");
	}

	class Skoczek:public Pionek
	{
		public:
		vector MozliweRuchy(Pionek* plansza[ROZMIAR_PLANSZY][ROZMIAR_PLANSZY]);
		string Wypisz();
		Skoczek (int i,int j,Gracz* gracz)
		{
			inicjuj(i,j,gracz);
			this->nazwa="Skoczek";
		}
	};

	vector Skoczek::MozliweRuchy(Pionek* plansza[ROZMIAR_PLANSZY][ROZMIAR_PLANSZY])
	{
		vector ruchy;

		WyprobujRuch(&ruchy,plansza,x+2,y-1);
		WyprobujRuch(&ruchy,plansza,x+2,y+1);
		WyprobujRuch(&ruchy,plansza,x-2,y-1);
		WyprobujRuch(&ruchy,plansza,x-2,y+1);
		WyprobujRuch(&ruchy,plansza,x+1,y+2);
		WyprobujRuch(&ruchy,plansza,x+1,y-2);
		WyprobujRuch(&ruchy,plansza,x-1,y+2);
		WyprobujRuch(&ruchy,plansza,x-1,y-2);

		return ruchy;
	}

	string Skoczek::Wypisz()
	{
		return gracz->Wypisz("S");
	}



	class Krol:public Pionek
	{
		public:
		vector MozliweRuchy(Pionek* plansza[ROZMIAR_PLANSZY][ROZMIAR_PLANSZY]);
		string Wypisz();
		Krol (int i,int j,Gracz* gracz)
		{
			inicjuj(i,j,gracz);
			this->nazwa="Król";
		}
	};

	vector Krol::MozliweRuchy(Pionek* plansza[ROZMIAR_PLANSZY][ROZMIAR_PLANSZY])
	{
		vector ruchy;

		WyprobujRuch(&ruchy,plansza,x-1,y-1);
		WyprobujRuch(&ruchy,plansza,x,y-1);
		WyprobujRuch(&ruchy,plansza,x+1,y-1);
		WyprobujRuch(&ruchy,plansza,x-1,y);
		WyprobujRuch(&ruchy,plansza,x+1,y);
		WyprobujRuch(&ruchy,plansza,x-1,y+1);
		WyprobujRuch(&ruchy,plansza,x,y+1);
		WyprobujRuch(&ruchy,plansza,x+1,y+1);

		return ruchy;
	}

	string Krol::Wypisz()
	{
		return gracz->Wypisz("K");
	}



	class Goniec:public Pionek
	{
		public:
		vector MozliweRuchy(Pionek* plansza[ROZMIAR_PLANSZY][ROZMIAR_PLANSZY]);
		string Wypisz();
		Goniec (int i,int j,Gracz* gracz)
		{
			inicjuj(i,j,gracz);
			this->nazwa="Goniec";
		}
	};

	vector Goniec::MozliweRuchy(Pionek* plansza[ROZMIAR_PLANSZY][ROZMIAR_PLANSZY])
	{
		vector ruchy;
		int i;

		//W prawy gorny rog
		i=1;
		while(WyprobujRuch(&ruchy,plansza,x+i,y+i)==1)
		{
			i++;
		}
		i=1;
		// W lewy dolny
		while(WyprobujRuch(&ruchy,plansza,x-i,y-i)==1)
		{
			i++;
		}
		//W prawy dolny
		i=1;
		while(WyprobujRuch(&ruchy,plansza,x+i,y-i)==1)
		{
			i++;
		}
		i=1;
		// W lewy gorny
		while(WyprobujRuch(&ruchy,plansza,x-i,y+i)==1)
		{
			i++;
		}

		return ruchy;
	}

	string Goniec::Wypisz()
	{
		return gracz->Wypisz("G");
	}



	class Hetman:public Pionek
	{
		public:
		vector MozliweRuchy(Pionek* plansza[ROZMIAR_PLANSZY][ROZMIAR_PLANSZY]);
		string Wypisz();
		Hetman (int i,int j,Gracz* gracz)
		{
			inicjuj(i,j,gracz);
			this->nazwa="Hetman";
		}
	};

	vector Hetman::MozliweRuchy(Pionek* plansza[ROZMIAR_PLANSZY][ROZMIAR_PLANSZY])
	{
		vector ruchy;
		int i;

		//W prawy gorny rog
		i=1;
		while(WyprobujRuch(&ruchy,plansza,x+i,y+i)==1)
		{
			i++;
		}
		i=1;
		//W lewy dolny
		while(WyprobujRuch(&ruchy,plansza,x-i,y-i)==1)
		{
			i++;
		}
		//W lewy dolny
		i=1;
		while(WyprobujRuch(&ruchy,plansza,x+i,y-i)==1)
		{
			i++;
		}
		i=1;
		// W lewy gorny
		while(WyprobujRuch(&ruchy,plansza,x-i,y+i)==1)
		{
			i++;
		}

		//Skaczemy po wierszach
		i=y+1;
		while(WyprobujRuch(&ruchy,plansza,x,i)==1)
		{
			i++;
		}
		i=y-1;
		while(WyprobujRuch(&ruchy,plansza,x,i)==1)
		{
			i=i-1;
		}
		//Skaczemy po kolumnach
		i=x+1;
		while(WyprobujRuch(&ruchy,plansza,i,y)==1)
		{
			i++;
		}
		i=x-1;
		while(WyprobujRuch(&ruchy,plansza,i,y)==1)
		{
			i=i-1;
		}

		return ruchy;
	}

	string Hetman::Wypisz()
	{
		return gracz->Wypisz("H");
	}
/****************************************************************
*********************** --- MAIN --- ****************************
****************************************************************/

int main(int argc, char **argv) {

	Gracz* gracz1;
	Gracz* gracz2;
	Gra* gierka;

	//Inicjalizujemy generator liczb pseudolosowych.
	srand(time(NULL));

	//Tworzymy graczy
	gracz1 = new Losowy("Biały",'[',']');
	gracz2 = new Leniwy("Czarny",'{','}',7);

	//Rozmieszczamy pionki gracza 1
	new Wieza(0,0,gracz1);
	new Skoczek(0,1,gracz1);
	new Goniec(0,2,gracz1);
	new Hetman(0,3,gracz1);
	new Krol(0,4,gracz1);
	new Goniec(0,5,gracz1);
	new Skoczek(0,6,gracz1);
	new Wieza(0,7,gracz1);

	//Rozmieszczamy pionki gracza 2
	new Wieza(7,0,gracz2);
	new Skoczek(7,1,gracz2);
	new Goniec(7,2,gracz2);
	new Hetman(7,4,gracz2);
	new Krol(7,3,gracz2);
	new Goniec(7,5,gracz2);
	new Skoczek(7,6,gracz2);
	new Wieza(7,7,gracz2);
	//Tworzymy
	gierka=new Gra(gracz1,gracz2,500);
	//No i siup!
	while(gierka->Ruch())
	{
	}

return 0;
}


Laboratorium programowania zad 18

Zadanie z laboratorium programowania na Informatyce UW.

Zadanie 18 (termin wysylania rozwiazan: 23 czerwca, godz. 23:59)

(Gramatyka)

Napisz program, ktory wczyta z wejscia gramatyke oraz tekst i sprobuje
skonstruowac i wypisac wyprowadzenie tego tekstu.

Bedziemy sie poslugiwali gramatykami, w ktorych dla kazdego symbolu
pomocniczego jest co najwyzej jedna produkcja pusta, a wszystkie
produkcje niepuste maja po prawej stronie po dwa symbole - pierwszy
to symbol koncowy a drugi pomocniczy. Ponadto, dla kazdego symbolu
pomocniczego prawe strony niepustych produkcji rozpoczynaja sie od
roznych symboli.

Wejscie:

Na wejsciu znajduja sie dwa wiersze, kazdy zakonczony kropka. W pierwszym
sa, rozdzielone przecinkami, grupy produkcji. Kazda grupa rozpoczyna sie
od symbolu pomocniczego, po nim jest strzalka zlozona ze znakow '-' i '>'
a dalej, rozdzielone znakami '|' prawe strony produkcji dla tego symbolu
pomocniczego. Symbol pomocniczy znajdujacy sie po lewej stronie pierwszej
produkcji jest symbolem poczatkowym gramatyki. Symbole pomocnicze i koncowe
sa jednoliterowe. W drugim wierszu jest tekst.

Wyjscie:

Program wypisuje na wyjscie produkcje zastosowane do wyprowadzenia tekstu.
Konczy wraz z koncem wyprowadzenia lub wtedy, gdy kolejnej produkcji wybrac
nie mozna.

Np. dla danych:

A->|xB,B->yA.
xyxy.

program powinien wypisac:

A->xB
B->yA
A->xB
B->yA
A->

a dla:

A->xA|yB,B->.
xxx.

program powinien wypisac:

A->xA
A->xA
A->xA

Wskazowka:

Gramatyke o postaci opisanej w tresci zadania mozna reprezentowac przy pomocy
dwuwymiarowej tablicy, ktorej wiersze odpowiadaja symbolom pomocniczym a
kolumny symbolom koncowym. Produkcje A->xB zapiszemy, umieszczajac w wierszu
'A' i kolumnie 'x' znak 'B'. Dodatkowo, dla kazdego symbolu pomocniczego A,
w tablicy jednowymiarowej mozemy zapisac wartosc logiczna mowiaca, czy dla A
jest produkcja pusta.

A oto rozwiązanie:

#include 
#include 
#include 

//Struktura dla produkcji
typedef struct produkcja_el{     
      char terminal;           
	  char nieterminal;
      struct produkcja_el * nastepny; 
};


//Struktura dla nieterminali.
struct nieterminal_el {
      char nieterminal;
	  struct produkcja_el * produkcje; 
      struct nieterminal_el* nastepny; 
};

struct nieterminal_el* start_nieterminal;


//dodaje produkcje do struktury.
void dodaj_produkcje(char prod_in,char prod_terminal,char prod_out)
{
	struct nieterminal_el* teraz_nieterminal;
	struct produkcja_el* tmp_produkcja;
	
	if(start_nieterminal==NULL)
	{
		//pierwszy nieterminal.
		
		teraz_nieterminal=malloc(sizeof(struct nieterminal_el));
		teraz_nieterminal->nastepny=NULL;
		teraz_nieterminal->nieterminal=prod_in;
		teraz_nieterminal->produkcje=NULL;
		start_nieterminal=teraz_nieterminal;
	}
	else
	{
		teraz_nieterminal=start_nieterminal;
	}
	
	//szukamy odpowiedniego nieterminala.
	
	while((teraz_nieterminal->nastepny!=NULL)&&(teraz_nieterminal->nieterminal!=prod_in))
	{
		teraz_nieterminal=teraz_nieterminal->nastepny;
	}
	
	if((teraz_nieterminal->nastepny==NULL)&&(teraz_nieterminal->nieterminal!=prod_in))
	{
		//nie znalezlismy, trzeba dodac.
		teraz_nieterminal->nastepny=malloc(sizeof(struct nieterminal_el));
		teraz_nieterminal=teraz_nieterminal->nastepny;
		teraz_nieterminal->nastepny=NULL;
		teraz_nieterminal->nieterminal=prod_in;
		teraz_nieterminal->produkcje=NULL;
		//dodany.
	}
	
	//Teraz jestesmy na odpowiednim nieterminalu,
	

	//i dodajemy produkcje.
	tmp_produkcja=teraz_nieterminal->produkcje;
	teraz_nieterminal->produkcje=malloc(sizeof(struct produkcja_el));
	teraz_nieterminal->produkcje->nastepny=tmp_produkcja;
	teraz_nieterminal->produkcje->terminal=prod_terminal;
	teraz_nieterminal->produkcje->nieterminal=prod_out;
	
	//powinna byc dodana.
}

//funkcja znajdujaca produkcje i wypisujaca.

char znajdz_produkcje(char prod_in,char znak)
{
	struct nieterminal_el* teraz_nieterminal;
	struct produkcja_el* teraz_produkcja;
	
	teraz_nieterminal=start_nieterminal;

	//szukamy odpowiedniego nieterminala.
	while((teraz_nieterminal->nastepny!=NULL)&&(teraz_nieterminal->nieterminal!=prod_in))
	{
		teraz_nieterminal=teraz_nieterminal->nastepny;
	}
	
	if(teraz_nieterminal->nieterminal==prod_in)
	{
		//jest.
		teraz_produkcja=teraz_nieterminal->produkcje;
		//szukamy odpowiedniej produkcji
			while((teraz_produkcja->nastepny!=NULL)&&(teraz_produkcja->terminal!=znak))
			{
				teraz_produkcja=teraz_produkcja->nastepny;
			}
			
		if(teraz_produkcja->terminal==znak)
		{
			//Jest odpowiednia produkcja!!
			//Wypisujemy.
			
			//zeby przypadkiem kropki nie wypisac.
		
			if(znak=='.')
			{
				printf("%c->n",prod_in);
			}
			else
			{
				printf("%c->%c%cn",prod_in,znak,teraz_produkcja->nieterminal);
			}
			
			return teraz_produkcja->nieterminal;
		}
	}
	else
	{
		return '.';
	}
	
	
}


int main (int argc, char *argv[])
{

	//Inicjujemy
	int wynik;
	char znak,prod_in,prod_out,nieterminal,prod_terminal;
	
	struct nieterminal_el* teraz_nieterminal;
	struct produkcja_el* teraz_produkcja;
	struct nieterminal_el* tmp_nieterminal;
	struct produkcja_el* tmp_produkcja;

	prod_in='.';
	prod_out='.';
	nieterminal='.';
	prod_terminal='.';
	start_nieterminal=NULL;
	
	wynik=scanf("%c",&znak);

	//Czytamy.
	while((znak!='r')&&(znak!='.')&&(znak!='n')&&(wynik!=EOF))
	{
		if((znak>='A')&&(znak')
				{
					wynik=scanf("%c",&znak);
					//printf("Wczytalem '%c'n",znak);
					
					while((znak!=',')&&(znak!='.')&&(wynik!=EOF))
					{
						if(znak=='|')
						{
							//printf("Dodaje produkcje %c->%c%cn",prod_in,prod_terminal,prod_out);
							dodaj_produkcje(prod_in,prod_terminal,prod_out);
							prod_terminal='.';	//kropka jako oznaczenie produkcji pustej,
							prod_out='.';
						}
						else if((znak>='a')&&(znak='A')&&(znak%c%cn",prod_in,prod_terminal,prod_out);
					prod_terminal='.';	//kropka jako oznaczenie produkcji pustej,
					prod_out='.';
					wynik=scanf("%c",&znak);
					
					//printf("Wczytalem '%c'n",znak);
		
				}
				else
				{
					//blad - brak >
					return 3;
				}
			
			}
			else
			{
				//blad brak  -
				return 2;
			}
		}
		else
		{
		//blad zly zakres znakow duzych
 		return 1;
		} 
		
	}
	//Powinno byc wczytane.
	
	//jesli byly jakies produkcje.

	if(start_nieterminal!=NULL)
	{
		
		//przechodzimy dalej.,

		while(((znak'z'))&&(wynik!=EOF))
		{
			wynik=scanf("%c",&znak);
		}


		
		prod_in='A';
		while((((znak>='a')&&(znaknieterminal);
			
			teraz_produkcja=teraz_nieterminal->produkcje;
			while(teraz_produkcja!=NULL)
			{
				//printf("%c->%c%cn",teraz_nieterminal->nieterminal,teraz_produkcja->terminal,teraz_produkcja->nieterminal);
				tmp_produkcja=teraz_produkcja;
				teraz_produkcja=teraz_produkcja->nastepny;
				free(tmp_produkcja);
			}
			tmp_nieterminal=teraz_nieterminal;
			teraz_nieterminal=teraz_nieterminal->nastepny;
			free(tmp_nieterminal);
		}
		
		return 0;
	}
	else
	{
		//nie bylo produkcji,
		return 5;
	}
}

Laboratorium programowania zad 17

Zadanie z laboratorium programowania na Informatyce UW.

Zadanie 17 (termin wysylania rozwiazan: 9 czerwca 2008, godz. 23:59)

(Procesor)

Zrealizuj symulator pewnego procesora. Ma on wczytac z wejscia jeden wiersz
zawierajacy program dla procesora, a nastepnie wykonac go, wczytujac
ewentualne dane z wejscia oraz wypisujac wyniki na wyjscie.

Procesor ma 10 rejestrow 10 bitowych przechowujacych wartosci calkowite w
kodzie U2 oraz dwa jednobitowe znaczniki mowiace o tym, czy wynik ostatniej
operacji byl ujemny oraz czy byl zerem. W chwili rozpoczecia rejestry sa
wyzerowane, znacznik "zero" ustawiony jest na true, a "minus" na false.

Program na nasz procesor jest reprezentowany przez ciag znakow (napis).
Kazda z 10 rozpoznawanych przez procesor instrukcji ma swoj jednoliterowy
kod, po ktorym podajemy od 0 do 2 jednoznakowych argumentow.

Ponizej znajduje sie lista instrukcji wraz z opisem znaczenia. W opisie tym
R oraz S oznaczaja numer rejestru ('0'..'9'), D oznacza liczbe skladajaca
sie z jednej cyfry dziesietnej a NN to dwucyfrowy zapis liczby calkowitej,
w ktorym pierwsza cyfra (dziesietna) jest bardziej znaczaca, a druga mniej.

rR  (read)          - wczytanie z wejscia liczby do rejestru R
wR  (write)         - wypisanie na wyjscie zawartosci wiersza R
aRS (add)           - R=R+S
cRS (copy)          - R=S
nR  (negate)        - R=-R
lRD (load)          - R=D
jNN (jump)          - goto NN
mNN (jump if minus) - if(minus) goto NN
zNN (jump if zero)  - if(zero) goto NN
d   (dump)          - wypisuje zawartosc rejestrow

Znaczniki "minus" i "zero", wykorzystywane w instrukcjach skoku warunkowego
'm' i 'z' sa aktualizowane po kazdej instrukcji, ktora przyjmuje jako
argument przynajmniej jeden rejestr (czyli po 'r' 'w' 'a' 'c' 'n' 'l') na
podstawie wartosci, ktora znalazla sie w tym rejestrze (gdy argumentem sa
dwa rejestry, znaczniki opisuja zawartosc pierwszego z nich).

Program podczas dzialania procesora jest przechowywany w pamieci. Komorki
pamieci sa adresowane kolejnymi liczbami naturalnymi zaczynajac od 1. Kazda
instrukcja zajmuje w pamieci od 1 do 3 komorek, np. instrukcja 'd' zajmuje
jedna komorke, 'r0' dwie a 'c01' trzy.

Wykonanie programu rozpoczyna sie od instrukcji znajdujacej sie pod adresem 1,
konczy sie, gdy kolejnej instrukcji, ktora mielibysmy wykonac, w programie nie
ma.

Oto przyklady programow:

r0r1r2w2w1w0

   wczytuje trzy liczby i wypisuje je w kolejnosci odwrotnej,

r0r1c20a21c31n3a30l41a40d

   wczytuje dwie liczby, oblicza ich sume, roznice i dodaje 1 do pierwszej
   liczby, na koniec pokazuje zawartosc rejestrow,

r0w0l11n1a01z99j03

   wczytuje liczbe n>0 i wypisuje n..1,

r0r1c20c31n3a23z36m28c02j05c12n1j05w0

   wczytuje dwie liczby i wypisuje ich najwiekszy wspolny dzielnik,

r0r1r2c31c40n4a34z44w2c32a34z37w0j57w1w0j99c32a34z99w0w2w1

   wczytuje trzy liczby i wypisuje je tak, by rowne ze soba nie sasiadowaly.
   Jesli to niemozliwe, nie wypisuje nic.

Postac danych:

Na wejsciu znajduje sie wiersz z programem (maksymalnie 100 znakow) oraz, w
kolejnych wierszach, liczby bedace danymi dla symulowanego programu (po jednej
w wierszu).

Postac wyniku:

Na wyjsciu powinien sie pojawic efekt wykonania instrukcji 'w' i 'd'.

Instrukcja 'w' wypisuje w zapisie dziesietnym (chodzi o zwykle uzycie funkcji
"printf" z pierwszym argumentem "%dn"), w pojedynczym wierszu, wartosc
argumentu. Instrukcja 'd' wypisuje zawartosc rejestrow. Dla kazdego z
dziesieciu rejestrow wypisujemy po jednym wierszu zawierajacym najpierw 10
cyfr binarnych wartosci przechowywanej w tym rejestrze (w kolejnosci od
najbardziej znaczacych), nastepnie jedna spacje oraz zapis dziesietny tej
wartosci.

A oto rozwiązanie:

#include 
#include 
#include 


int rejestry[10][10];
char program[100];
int minus;
int zero;


//Najpierw funkcje pomocnicze dla kodu binarnego.



int rozkoduj (int rejestr)
{
	//U2 na int
	int i,wynik,mnoznik;
	
	//dla ujemnego bitu:
	if (rejestry[rejestr][0]==1)
	{
		wynik=-512;
	}
	else
	{
		wynik=0;
	}
	
	mnoznik=256; 

		
	//9 razy:
	for (i=1;i<10;i++)
	{
		if(rejestry[rejestr][i]==1)
		{
			wynik=wynik+mnoznik;
		}
		
		mnoznik=mnoznik/2;
	}

	return wynik;
}



void zakoduj (int liczba,int rejestr)
{
	//koduje int na rejestr.


	int i,mnoznik;
	
	//na poczatku dla ujemnego bitu:
	
		if (liczba<0)
		{
			liczba=liczba+512;
			rejestry[rejestr][0]=1;
		}
		else
		{
			rejestry[rejestr][0]=0;
		}
		
	
	mnoznik=256; 
	
	
	//9 razy:
	
	for (i=1;i=mnoznik)
		{
			//ta liczba jest w rozkladzie.
			rejestry[rejestr][i]=1;
			liczba=liczba-mnoznik;
		}
		else
		{
			rejestry[rejestr][i]=0;
		}
		
		mnoznik=mnoznik/2;
	}

}


void ustaw_flagi(int rejestr)
{
	int zawartosc;
	zawartosc=0;
	zawartosc=rozkoduj(rejestr);

	if(zawartosc==0)
	{
		zero=1;
		minus=0;
	}
	else if(zawartosc>0)
	{
		zero=0;
		minus=0;
	}
	else
	{
		zero=0;
		minus=1;
	}
	
}

//Teraz funkcje realizujace instrukcje.


int read_p(int instrukcja)
{
	int rejestr,wynik;
	int liczba;
	//wczytuje znak do odpowiedniego rejestru
	rejestr=program[instrukcja+1]-'0'; // w programie sa char'y
	wynik=scanf("%d",&liczba);

	

	if(wynik>0)
	{
		//przepisujemy liczbe na rejestr;
		zakoduj(liczba,rejestr);
		ustaw_flagi(rejestr);
		return instrukcja+2;
		
	}
	else
	{
		return -1;
	}

}


int write_p(int instrukcja)
{
	int rejestr;
	int liczba;
	//wypisuje
	rejestr=program[instrukcja+1]-'0'; // w programie sa char'y
	liczba=rozkoduj(rejestr);
	ustaw_flagi(rejestr);

	printf("%dn",liczba);

	return instrukcja+2;
}

int load(int instrukcja)
{
	int rejestr;
	int liczba;
	//wczytuje znak do odpowiedniego rejestru
	rejestr=program[instrukcja+1]-'0'; // w programie sa char'y
	liczba=program[instrukcja+2]-'0';

	if((liczba>=0)&&(liczba<=9))
	{
		//przepisujemy liczbe na rejestr;
		zakoduj(liczba,rejestr);
		ustaw_flagi(rejestr);
		return instrukcja+3;
	}
	else
	{
		return -1;
		//Blad - podano nie liczbe
	}
}

int dump(int instrukcja)
{
	int i,j;
	//wyrzuca rejestry.

	for(i=0;i<10;i++)
	{
		for(j=0;j<10;j++)
		{
			printf("%d",rejestry[i][j]);
		}

		printf(" %dn",rozkoduj(i));
	}

	return instrukcja+1;
}

int jump(int instrukcja)
{
	int go,teraz,i;
	go=(program[instrukcja+1]-'0')*10 +(program[instrukcja+2]-'0');

	//szukamy go-tej instrukcji.

	go+=-1;//bo w opisie numerowane od 1
	teraz=0;
	i=0;

	while((teraz<100)&&(i<go))
	{
		if(program[teraz]=='d')
		{
			teraz+=1;
		}
		else if((program[teraz]=='r')||(program[teraz]=='w')||(program[teraz]=='n'))
		{
			teraz+=2;
		}
		else
		{
			teraz+=3;
		}

		i++;
	}

	if(i==go)
	{
		//znalezlismy
		return teraz;
	}
	else
	{
		return -1;
		//Nie ma tej instrukcji.
	}

}

int jump_minus(int instrukcja)
{
	if(minus)
	{
		return jump(instrukcja);
	}
	else
	{
		return instrukcja+3;
	}
}

int jump_zero(int instrukcja)
{
	if(zero)
	{
		return jump(instrukcja);
	}
	else
	{
		return instrukcja+3;
	}
}

// no i tylko funkcje matematyki binarnej.


int copy(int instrukcja)
{
	int i,rejestr1,rejestr2;

	rejestr1=program[instrukcja+1]-'0';
	rejestr2=program[instrukcja+2]-'0';

	

	for(i=0;i0;i+=-1)
	{
		rejestry[rejestr1][i]+=rejestry[rejestr2][i];
		rejestry[rejestr1][i]+=przeniesienie;
		przeniesienie=0;

		//przeniesienie;
		if(rejestry[rejestr1][i]>1)
		{
			przeniesienie=1;
			rejestry[rejestr1][i]+=-2;
		}
	}

	//bit znaku:
	rejestry[rejestr1][i]+=rejestry[rejestr2][i];
	rejestry[rejestr1][i]+=przeniesienie;

	if(rejestry[rejestr1][i]>1)
	{

		if(!przeniesienie)
		{
			//przepelnienie
			return -1;
		}
		else
		{
			rejestry[rejestr1][i]+=-2;
			ustaw_flagi(rejestr1);
			return instrukcja+3;
		}
	}
	else
	{
		ustaw_flagi(rejestr1);
		return instrukcja+3;
	}

}

int negate(int instrukcja)
{
	int i,rejestr,przeniesienie;
	rejestr=program[instrukcja+1]-'0';

	//inwersja bitow
	for(i=0;i1)
		{
			przeniesienie=1;
			rejestry[rejestr][i]+=-2;
		}
		i=i-1;
	}
	ustaw_flagi(rejestr);
	return instrukcja+2;
}




int main (int argc, char *argv[])
{
	int i,j,k,wynik;
	char znak;
	zero=0;
	minus=0;
	for(k=0;k<10;k++)
	{
		for(j=0;j<10;j++)
		{
			rejestry[k][j]=0;
		}
	}


	//zainicjowane.

	wynik=scanf("%c",&znak);
	k=0;
	while((wynik!=EOF)&&(k<100)&&(znak!='n')&&(znak!='r'))
	{
		program[k]=znak;
		wynik=scanf("%c",&znak);
		
		k++;
	}

	while(k<100)
	{
		program[k]=' ';
		k++;
	}




	k=0;
	//Wczytujemy
	if(wynik!=EOF)//jesli nie bylo programu
	{
		i=0;

		while(i<100)
		{
			
			if(i==-1)
			{
				//byl blad.
				break;
			}
			else
			{
				
				switch (program[i])
				{
					case 'r':
						i=read_p(i);
						break;
					case 'w':
						i=write_p(i);
						break;
					case 'a':
						i=add(i);
						break;
					case 'c':
						i=copy(i);
						break;
					case 'n':
						i=negate(i);
						break;
					case 'l':
						i=load(i);
						break;
					case 'd':
						i=dump(i);
						break;
					case 'j':
						i=jump(i);
						break;
					case 'm':
						i=jump_minus(i);
						break;
					case 'z':
						i=jump_zero(i);
						break;
					default:
						i=-1;
						break;
				}

			}
		}

	}
	else
	{
		//Szwindel. Nie bylo znakow.
		return 1;
	}

return 0;
}

Laboratorium programowania zad 16

Zadanie z laboratorium programowania na Informatyce UW.

Zadanie 16 (termin wysylania rozwiazan: 2 czerwca 2008, godz. 23:59)

(Graf)

Tekstowym zapisem grafu skierowanego, majacego n wierzcholkow
etykietowanych liczbami calkowitymi od 1 do n, bedzie ciag n wierszy
wskazujacych sasiadow kazdego z wierzcholkow. W i-tym wierszu znajda
sie, rozdzielone spacjami i uporzadkowane rosnco, numery wierzcholkow,
do ktorych prowadza krawedzie z wierzcholka i.

k-tym poziomem w grafie g wzgledem wierzcholka w nazwiemy zbior
wierzcholkow grafu g, ktorych odleglosc od w, mierzona liczba
wierzcholkow na najkrotszej sciezce, wynosi k.

Napisz program, ktory wczyta z wejscia tekstowy zapis grafu
skierowanego o niepustym zbiorze wierzcholkow i wypisze na wyjscie
kolejno, od pierwszego, wszystkie niepuste poziomy liczone wzgledem
wierzcholka 1. Dla kazdego poziomu program powinien wypisac,
uporzadkowane rosnaco i rozdzielone pojedynczymi odstepami, numery
wierzcholkow znajdujacych sie na tym poziomie.

Np. dla danych:

3 4
1 4 5
2

2
4 5

program powinien wypisac:

1
3 4
2
5

A oto rozwiązanie:

#include 
#include 
#include 


//Ten kod jest bardzo, bardzo brzydki. Opieram się na algorytmie przeszukiwania wszerz.

//Struktura dla kolejki przeszukiwania.
typedef struct kolejka_el{
	int wezel;
	struct kolejka_el * nastepny;
	int poziom;
};

//Struktura dla wezłów grafu
struct wezel_el{     
      int liczba;           
      struct wezel_el * nastepny; 
	  struct krawedz_el* krawedzie;
	  int odwiedzony;
	  struct krawedz_el* wypisanie;
};

//Struktura dla krawędzi grafu
struct krawedz_el {
      int cel;   
      struct krawedz_el* nastepny; 
};


int main (int argc, char *argv[])
{

	//Inicjujemy
	int numer_wezla,liczba,wynik,i;
	char znak;
	struct wezel_el *teraz_wezel=NULL;
	struct wezel_el *tmp_wezel=NULL;
	struct wezel_el *start_wezel=NULL;
	struct krawedz_el *teraz_krawedz=NULL;
	struct krawedz_el *tmp_krawedz=NULL;
	struct kolejka_el *start_kolejka=NULL;
	struct kolejka_el *teraz_kolejka=NULL;
	struct kolejka_el *koniec_kolejka=NULL;
	struct kolejka_el *tmp_kolejka=NULL;

	
	numer_wezla=1;
	wynik=scanf("%d",&liczba);

	//Wczytujemy
	if(wynik!=EOF)//jesli nie bylo znakow w pierwszym wierszu.
	{
		//pierwszy element ciagu znakow
		start_wezel=malloc(sizeof(struct wezel_el));
		start_wezel->nastepny=NULL;
		start_wezel->krawedzie=malloc(sizeof(struct krawedz_el));
		start_wezel->wypisanie=NULL;
		start_wezel->krawedzie->nastepny=NULL;
		start_wezel->krawedzie->cel=liczba;
		start_wezel->liczba=numer_wezla;
		start_wezel->odwiedzony=0;
		wynik=scanf("%c",&znak);
		teraz_wezel=start_wezel;
		teraz_krawedz=teraz_wezel->krawedzie;

			while(wynik!=EOF)
			{
			
				if(znak==' ')
				{
					//Wczytalismy spacje. Zaraz bedzie nowa krawedz.
					teraz_krawedz->nastepny=malloc(sizeof(struct krawedz_el));
					teraz_krawedz=teraz_krawedz->nastepny;
					teraz_krawedz->nastepny=NULL;
					teraz_krawedz->cel=0;
				}
				else if((znak>='0')&&(znakcel=teraz_krawedz->cel*10 + (znak-'0');
				}
				else if(znak=='n')
				{
				
					//Wczytalismy nowy wiersz. Budujemy nowy wezel.
					numer_wezla++;
					teraz_wezel->nastepny=malloc(sizeof(struct wezel_el));
					teraz_wezel->wypisanie=NULL;
					teraz_wezel=teraz_wezel->nastepny;
					start_wezel->odwiedzony=0;
					teraz_wezel->nastepny=NULL;
					teraz_wezel->liczba=numer_wezla;

					teraz_wezel->krawedzie=malloc(sizeof(struct krawedz_el));
					teraz_krawedz=teraz_wezel->krawedzie;
					teraz_krawedz->cel=0;
					teraz_krawedz->nastepny=NULL;
				}
				
				wynik=scanf("%c",&znak);
				
			}
			//powinno byc wczytane.
			
	
	
		// Teraz przetworzymy dane.
	
		koniec_kolejka=malloc(sizeof(struct kolejka_el));
		koniec_kolejka->nastepny=NULL;
		koniec_kolejka->poziom=1;
		koniec_kolejka->wezel=1;
		start_kolejka=koniec_kolejka;
		teraz_kolejka=start_kolejka;
	
	
	
		while(teraz_kolejka!=NULL)
		{
		
			//Odszukujemy wskaznik do wezla.
			teraz_wezel=start_wezel;
			i=1;
			while((iwezel)&&(teraz_wezel!=NULL))
			{
				teraz_wezel=teraz_wezel->nastepny;
				i++;
			}
			
			//Jesli jeszcze nie byl odweidzony
			if(teraz_wezel->odwiedzony==0)
			{
				//Odwiedzilismy wezel.
				teraz_wezel->odwiedzony=1;
				//Wypiszmy go.
				i=1;
				tmp_wezel=start_wezel;
				while((ipoziom)&&(tmp_wezel!=NULL))
				{
					tmp_wezel=tmp_wezel->nastepny;
					i++;
				}
				//jestesmy na odpowiednim poziomie.
		
				if(tmp_wezel->wypisanie==NULL)
				{
					tmp_wezel->wypisanie=malloc(sizeof(struct krawedz_el));
					tmp_wezel->wypisanie->nastepny=NULL;
					tmp_wezel->wypisanie->cel=teraz_wezel->liczba;
				}
				else
				{
					//jest tu cos, trzeba znalezc odpowiednie miejsce. - insertion sort.
					if(tmp_wezel->wypisanie->cel>teraz_wezel->liczba)
					{
						//Pierwszy element zamieniamy.
						tmp_krawedz=tmp_wezel->wypisanie;
						tmp_wezel->wypisanie=malloc(sizeof(struct krawedz_el));
						teraz_krawedz=tmp_wezel->wypisanie;
						teraz_krawedz->nastepny=tmp_krawedz;
						teraz_krawedz->cel=teraz_wezel->liczba;
					}
					else
					{
						teraz_krawedz=tmp_wezel->wypisanie;
						
						while((teraz_krawedz->nastepny!=NULL)&&(teraz_krawedz->nastepny->celliczba))
						{
							teraz_krawedz=teraz_krawedz->nastepny;
						}
						
						//znalezlismy miejsce do wstawienia.
						tmp_krawedz=teraz_krawedz->nastepny;
						teraz_krawedz->nastepny=malloc(sizeof(struct krawedz_el));
						teraz_krawedz=teraz_krawedz->nastepny;
						teraz_krawedz->nastepny=tmp_krawedz;
						teraz_krawedz->cel=teraz_wezel->liczba;
					}
					
				}
				//Wstawiony do listy do wypisania.

				//Dodajmy jego krawedzie do kolejki.
				teraz_krawedz=teraz_wezel->krawedzie;
				while(teraz_krawedz!=NULL)
				{
					if(teraz_krawedz->cel!=0)
					{
						koniec_kolejka->nastepny=malloc(sizeof(struct kolejka_el));
						koniec_kolejka=koniec_kolejka->nastepny;
						koniec_kolejka->nastepny=NULL;
						koniec_kolejka->poziom=teraz_kolejka->poziom+1;
						koniec_kolejka->wezel=teraz_krawedz->cel;
					}
					teraz_krawedz=teraz_krawedz->nastepny;
				}
			
			}
			tmp_kolejka=teraz_kolejka;
			teraz_kolejka=teraz_kolejka->nastepny;
			free(tmp_kolejka);
		}
	

		//Wezly przetworzone i gotowe do wypisania.
	
		teraz_wezel=start_wezel;
		while(teraz_wezel->nastepny!=NULL)
		{
			teraz_krawedz=teraz_wezel->wypisanie;
			
			if(teraz_krawedz!=NULL)
			{
				while(teraz_krawedz!=NULL)
				{
					printf("%d ",teraz_krawedz->cel);
					tmp_krawedz=teraz_krawedz;
					teraz_krawedz=teraz_krawedz->nastepny;
					free(tmp_krawedz);
				}
				printf("n");
			}
			
			teraz_krawedz=teraz_wezel->krawedzie;
			while(teraz_krawedz!=NULL)
			{
					tmp_krawedz=teraz_krawedz;
					teraz_krawedz=teraz_krawedz->nastepny;
					free(tmp_krawedz);
			}
			
			tmp_wezel=teraz_wezel;
			teraz_wezel=teraz_wezel->nastepny;
			free(tmp_wezel);
		}

		free(teraz_wezel);

	}
	else
	{
		//Szwindel. Nie bylo znakow.
		return 1;
	}

return 0;
}