ansi C

Ogłoszenia

(4 grudnia 2005) Pomyliłem się w punktacji na 7 liście. Można będzie oddać jedno dodatkowe zadanie z tej listy na następnych zajęciach, aby uzupełnić ewentualne braki punktowe (co najwyżej dwa punty za nieoddane na ostatnich zajęciach zadanie).
(7 października 2005) Proszę dopilnować, aby każdy uczestnik zajęć miał założone konto w lokalnej sieci Windows'owej.

Terminy

wykład (Z.Płoski):: piątek 8-10, sala 31
laboratorium:: wtorek 18-20, sala 50a

Literatura

papierowa:

B.W.Kernighan, D.M.Ritchie: Język ANSI C. WNT, Warszawa 1994, ISBN 83-204-2433-X.

elektroniczna:

Standard ANSI C
Opis bibliotek standardowych
Steve Summit: Introductory Class Notes oraz Intermediate Class Notes
Marshall Brain: How C Programming Works
Steven Holmes: C Programming
Robert Chwastek: Język C

Przygotowanie studentów

wymagane:

samodzielna nauka z podręcznika

wskazane:

samodzielne pisanie prostych programów

Forma zaliczenia przedmiotu

ogólnie:: Na każde zajęcia będzie układana oddzielna lista z zadaniami. Zadania będą miały określoną maksymalną liczbę punktów możliwych do uzyskania za ich poprawne wykonanie w terminie.
obecności:: Obecność na zajęciach jest obowiązkowa. Za każdą nieusprawiedliwioną nieobecność na zajęciach student(ka) otrzymuje ujemną liczbę punktów równą połowie punktów możliwych do uzyskania za zadania na dany dzień.
terminy:: Zadania do zaprogramowania będą ogłaszane kilka dni przed terminem ich realizacji. W przypadku usprawiedliwionej nieobecności będzie można oddawać zaległe zadania na najbliższych zajęciach.
prezentacje:: Programy należy prezentować osobiście w czasie pracowni (proszę nie wysyłać programów pocztą elektroniczną, ani nie przekazywać dyskietek poprzez kolegów/koleżanki). W trakcie prezentacji programu trzeba się liczyć z pytamiami dotyczącymi zadania, jego rozwiązania, oraz zastosowanych konstrukcji językowych. Jeżeli zaliczający zadanie nie potrafi sensownie odpowiedzieć na pytania dotyczące swojego programu, prowadzący może przyznać mu(jej) punkty karne.
programy:: Każdy program jest oceniany za zgodność z treścią, efektywność algorytmów, styl programowania, czytelność (komentarze, sensowne nazwy zmiennych, wcięcia itp.). Każdy plik z kodem źródłowym powinien zawierać na początku komentarz z danymi autora i nazwą zadania.
listy zadań:: Na każdej liście będzie kilka zadań różnie punktowanych. Do listy z zadaniami będzie też dopisana maksymalna liczba punktów możliwych do uzyskania za zrobione zadania. Należy więc wybrać sobie z listy tylko część zadań i starannie je opracować.
oceny:: Aby zaliczyć zajęcia laboratoryjne na ocenę dostateczną trzeba do końca semestru zdobyć 50% z wszystkich możliwych do uzyskania punktów; na ocenę bardzo dobra trzba będzie zgromadzić 90% punktów; oceny pośrednie pozostją w liniowej zależności od przedstawionych wymagań granicznych.

Zadania na laboratorium

Lista 1 (11 października 2005): 10 punktów.

Przeczytaj z książki B.W.Kernighana i D.M.Ritchiego Język ANSI C rozdział 1: Elementarz.

(1 punkt) Zaloguj się i sprawdź, czy na Twoim komputerze jest zainstalowany Dev-C++ 4.9.9.2. Jeżeli nie, ściągnij go ze strony Bloodshed Software (plik devcpp-4.9.9.2_setup.exe) i zainstaluj na dysku lokalnym. Sprawdź działanie tego zintegrowanego środowiska programowania kompilując i uruchamając program hello world.
(2 punkty) Napisz program, który wczytuje dwie liczby rzeczywiste i wypisuje sumę ich kwadratów.
(3 punkty) Napisz program, który wczytuje dwie liczby całkowite i wypisuje ich sumę, różnicę, iloczyn, iloraz oraz resztę z dzielenia całkowitoliczbowego. Pamiętaj, że nie dzielimy przez zero. Jeżeli użytkownik poda zero jako drugą liczbę, program powinien zareagować odpowiednim komunikatem.
(3 punkty) Napisz program, który wczytuje trzy liczby rzeczywiste i wypisuje wartość środkową co do wielkości.
(2 punkty) Napisz program, który wypisuje na ekran kolejne potęgi liczby 2.
(2 punkty) Napisz program, który wczytuje liczbę całkowitą i wypisuje informacje na temat jej parzystości.
(2 punkty) Napisz program, który wczytuje liczbę całkowitą i wypisuje 10 jej kolejnych wielokrotności.
(5 punktów) Napisz program, który wczytuje liczbę całkowitą i sprawdza, czy jest to liczba pierwsza.

Lista 2 (18 października 2005): 11 punktów.

Jeszcze raz przeczytaj z książki B.W.Kernighana i D.M.Ritchiego Język ANSI C rozdział 1: Elementarz. Tym razem czytaj powoli, dokładnie, z głębokim zrozumieniem.

(2 punkty) Napisz program, który wczyta dodatnią liczbę całkowitą i wypisze jej rozwinięcie w układzie dwójkowym.
Uwaga: Zastosuj rekurencję do rozwiązania tego zadania.
(3 punkty) Napisz program, który wczytuje do tablicy znakowej napis ze standardowego wejścia i sprawdza, czy jest on palindromem. Wczytany napis ma mieć nie więcej niż 79 znaków.
Uwaga:
Uwaga: Palindrom to napis, który ma to samo znaczenie niezależnie od tego, czy czytamy go normalnie czy wspak. Przykładowe znane palindromy w języku polskim to: Kajak, Anna, KobyłaMaMałyBok, ZakopaneNaPokaz, MożeJutroTaDamaDaTortuJeżom.
(2 punkty) Napisz program, który wczytuje liczbę rzeczywistą oznaczającą prędkość pojazdu liczoną w km/h. Oblicz i wypisz, ile wynosi ta prędkość liczona w mi/h i m/s.
Uwaga: 1[km]=0.621371[mi].
(3 punkty) Napisz program, który wczytuje długość ciągu, a później ciąg liczb całkowitych. Określ jaka jest w tym ciągu wartość najmniejsza i największa.
Uwaga: Program nie powinien tablicować wczytywanych danych.
(5 punktów) Napisz program, który wczytuje ze standardowego wejścia kolejne znaki, aż do napotkania symbolu EOF. Na końcu program powinien wypisać na standardowym wyjściu dla błędów statystykę dotycząca wczytanego tekstu: ile było wszystkich przeczytanych znaków, z ilu linii składał się tekst, oraz ile razy występowały poszczególne litery alfabetu.
Uwaga: Program powinien posłużyć się tablicą liczników dla wszystkich wczytywanych znaków.
(7 punktów) Zaprogramuj prosty kalkulator. Ma on działać w pętli: najpierw wczytuje liczbę, potem symbol działania arytmetycznego, i znowu liczbę i symbol działania arytmetycznego, itd. Program działa, wyliczając na bieżąco wyniki operacji arytmetycznych, aż do wczytania symbolu równości (=).
Uwaga: Dopuszczalne operacje arytmetyczne to: dodawanie (+), odejmowanie (-), mnożenie (*), dzielenie (/).

Lista 3 (25 października 2005): 12 punktów.

Przeczytaj z książki B.W.Kernighana i D.M.Ritchiego Język ANSI C rozdział 2: Typy, operatory i wyrażenia.

(2 punkty) Napisz program, który wczytuje liczbę całkowitą reprezentującą rok. Program ma sprawdzić, czy podany rok jest przestępny i wypisać odpowiedni komunikat. Do testowania przestępności roku użyj funkcji czyPrzestepny(int), która zwraca 1 gdy rok jest przestępny, albo 0 w przeciwnym przypadku.
(2 punkty, kontynuacja poprzedniego zadania) Napisz program, który wczytuje dwie liczby całkowite reprezentujące odpowiednio miesiąc i rok. Program ma sprawdzić, ile dni ma zadany miesiąc (luty ma różną liczbę dni w zależności od roku). Skorzystaj z dwuwymiarowej tablicy dniWMiesiacu, w której są zapisane liczby dni w poszczególnych miesiącach, osobno dla lat zwykłych i przestępnych. Do tablicy tej powinieneś się odwoływać w nastepujacy sposób: dniWMiesiacu[czyPrzestepny(rok)][mies].
(2 punkty, kontynuacja poprzedniego zadania) Napisz program, który wczytuje trzy liczby całkowite reprezentujące odpowiednio dzień, miesiąc i rok. Program ma wyliczyć, ile dni upłynęło do zadanego dnia od początku roku, oraz ile dni zostało jeszcze do jego końca włącznie z tym dniem. Skorzystaj z pomocniczej tablicy dwuwymiarowej dniOdPoczRoku, która będzie zawierała informacje o liczbie dni od poczatku roku do końca poprzedniego miesiąca minus jeden dzień. Obie wartości będziesz mógł wtedy bardzo prosto wyliczyć. Przykładowo, dystans czasowy od początku roku do 1 stycznia wynosi 0 dni, a od 1 grudnia do końca roku 31 dni.
(3 punkty, kontynuacja poprzedniego zadania) Napisz program, który wczytuje trzy liczby całkowite reprezentujące odpowiednio dzień, miesiąc i rok. Program ma sprawdzić czy podana data jest prawidłowa (miesiąc z zakresu 1...12, dzień 1...). Weź też pod uwagę fakt, że kalendarz Gregoriański obowiązuje od 15 października 1582. W swoim programie koniecznie zaimplementuj funkcję porownanieDat(int,int,int,int,int,int) porównującą dwie daty, która będzie odpowiadać wartością -1 gdy pierwsza data jest późniejsza niż druga, 0 gdy daty są takie same, 1 gdy pierwsza data jest wcześniejsza niż druga.
(3 punkty, kontynuacja poprzedniego zadania) Napisz program, który dwukrotnie wczytuje trzy liczby całkowite reprezentujące odpowiednio dzień, miesiąc i rok (wczytujemy dwie daty). Program ma sprawdzić, czy podane daty są poprawne, a potem wyliczyć, ile dni upłynęło od pierwszej daty do drugiej. Liczba tych dni ma wynieść 0 gdy obie daty są takie same, a w przypadku gdy pierwsza data jest późniejsza niż druga program powinien wypisać liczbę ujemną.

(5 punktów) Napisz program, który wczyta najpierw liczbę rzeczywistą r≥0 a potem liczbę naturalną k<50. Następnie program ma stablicować wartości p_i dla i=0...k-1 określone następującym wzorem rekurencyjnym:
p₀ = 1
p_i = (r/p_i-1+p_i-1)/2 : i>0
Na koniec program ma wypisać w dwóch kolumnach wszystkie wyniki: w pierwszej kolumnie wartości p_i a w drugiej różnicę pomiędzy p_i a pierwiastkiem kwadratowym z r (użyj funkcji sqrt z biblioteki matematycznej).
(7 punktów, kontynuacja poprzedniego zadania) Napisz program, który będzie w pętli wczytywał liczby rzeczywiste i obliczał ich pierwiastki kwadratowe. Program ma działać, dopóki użytkownik nie wpisze liczby ujemnej albo ciągu znaków, który nie reprezentuje liczby (funkcja scanf zwraca liczbę poprawnie dopasowanych wzorców). Do wyliczenia pierwiastka z zadanej liczby n napisz własną rekurencyjną funkcję pierwiastek(double,double), która będzie korzystała z podanego w poprzednim zadaniu wzoru. W kolejnych wywołaniach rekurencyjnych obliczana wartość zbiega właśnie do pierwiastka kwadratowego z n. Obliczenia należy kontynuować, dopóki |p_i-p_i-1| / p_i-1 ≥ 10^-6.

Lista 4 (8 listopada 2005): 13 punktów.

Przeczytaj z książki B.W.Kernighana i D.M.Ritchiego Język ANSI C rozdział 3: Sterowanie.

(2 punkty) Napisz program, który wczytuje tekst ze standardowego wejścia i wypisuje go na standardowe wyjście z małymi literami zamienionymi na wielkie. Wykorzystaj własną funkcję zamieniającą małą literę na wielką. Pozostałe znaki nie powinny być zmieniane. Do czytania danych ze strumienia wejściowego wykorzystaj funkcję getchar() a do pisania do strumienia wyjściowego funkcję putchar(). Program ma działać w pętli, dopóki nie zostanie wczytany znak końca pliku EOF.
(2 punkty) Napisz program, który wczytuje tekst ze standardowego wejścia i po przefiltrowaniu wypisuje go na standardowe wyjście. Filtrowanie ma polegać na usunięciu z tekstu wszystkich znaków o kodach <32 (za wyjątkiem znaków '\n' i '\t') lub ==127. Wykorzystaj własną funkcję sprawdzającą, czy znak ma być zatrzymany (wartość 1) czy odrzucony (wartość 0). Do czytania danych ze strumienia wejściowego wykorzystaj funkcję getchar() a do pisania do strumienia wyjściowego funkcję putchar(). Program ma działać w pętli, dopóki nie zostanie wczytany znak końca pliku EOF.
(3 punkty) Napisz program, który wczytuje tekst ze standardowego wejścia i wypisuje go na standardowe wyjście po przeformatowaniu. Formatowanie ma polegać na zastąpieniu w tekście wszystkich długich odstępów pojedynczą spacją i na usunięciu odstępów sprzed znaku końca linii '\n'. Przez długi odstęp należy rozumieć spójny ciąg złożony ze znaków spacji ' ' i tabulacji '\t' za wyjątkiem pojedynczej spacji. Do czytania danych ze strumienia wejściowego wykorzystaj funkcję getchar() a do pisania do strumienia wyjściowego funkcję putchar(). Program ma działać w pętli, dopóki nie zostanie wczytany znak końca pliku EOF.
(3 punkty) Napisz program, który wczytuje tekst ze standardowego wejścia i wypisuje go na standardowe wyjście po przeformatowaniu. Formatowanie ma polegać na zastąpieniu w tekście wszystkich znaków tabulacji '\t' odpowiednią liczbą spacji ' ' (od 1 do 8), tak aby wygenerowany tekst wyglądał tak samo jak oryginał. Do czytania danych ze strumienia wejściowego wykorzystaj funkcję getchar() a do pisania do strumienia wyjściowego funkcję putchar(). Program ma działać w pętli, dopóki nie zostanie wczytany znak końca pliku EOF.
(3 punkty) Napisz program, który wczytuje tekst ze standardowego wejścia i wypisuje go na standardowe wyjście po przeformatowaniu. Formatowanie ma polegać na wypisaniu każdego słowa w osobnej linii. Słowa w tekście są porozdzielane ciągami białych znaków (spacje ' ', tabulacje '\t', znaki przejścia do nowej linii '\r' i '\n'). Do czytania danych ze strumienia wejściowego wykorzystaj funkcję getchar() a do pisania do strumienia wyjściowego funkcję putchar(). Program ma działać w pętli, dopóki nie zostanie wczytany znak końca pliku EOF.

(2 punkty) Równanie algebraiczne drugiego stopnia (równanie kwadratowe) ma następującą postać:
ax² + bx + c = 0
Napisz program, który wczyta współczynniki rzeczywiste (typu double) tego równania ze standardowego wejścia (funkcja scanf()) i rozwiąże je (wyznaczy pierwiastki rzeczywiste). Jeśli wczytany współczynnik a będzie równy 0, to należy natychmiast zakończyć działanie programu. Komunikaty zachęcające do wpisywania wanych należy kierować na standardowe wyjście dla błędów (funkcja fprintf()). Jako wynik, należy wypisać na standardowym wyjściu (funkcja printf()) w pierwszej linii liczbę pierwiastków rzeczywistych tego równania, a w następnych liniach kolejno te pierwiastki (po jednym w każdej linii).
(11 punktów) Równanie algebraiczne trzeciego stopnia (równanie sześcienne) ma następującą postać:
ax³ + bx² + cx + d = 0
Napisz program, który wczyta współczynniki rzeczywiste (typu double) tego równania ze standardowego wejścia (funkcja scanf()) i rozwiąże je (wyznaczy pierwiastki rzeczywiste). Jeśli wczytany współczynnik a będzie równy 0, to należy natychmiast zakończyć działanie programu. Komunikaty zachęcające do wpisywania danych należy kierować na standardowe wyjście dla błędów (funkcja fprintf()). Jako wynik, należy wypisać na standardowym wyjściu (funkcja printf()) w pierwszej linii liczbę pierwiastków rzeczywistych tego równania, a w następnych liniach kolejno te pierwiastki (po jednym w każdej linii). Informacji na temat rozwiązywania równań trzeciego stopnia powinieneś poszukać w internecie (na przykład w Wikipedii) lub w fachowej literaturze matematycznej.

Lista 5 (22 listopada 2005): 15 punktów.

Przeczytaj z książki B.W.Kernighana i D.M.Ritchiego Język ANSI C rozdział 4: Funkcje i struktura programu.

(3 punkty) Dość często potrzebujemy ustawiać lub sprawdzać wartości pojedynczych bitów w słowie typu int lub unsigned int. Zdefiniuj dwie funkcje: jedną do odczytywania wartości określonego bitu (funkcja ma zwracać wartość 0 lub 1), a drugą do ustawiania wartości określonego bitu:
int jakiBit (unsigned *komorka, int nrBitu);
void ustawBit (unsigned *komorka, int nrBitu, int wartosc);
Przy programowaniu tych funkcji skorzystaj z operatorów bitowych. Następnie napisz krótki program testowy, sprawdzający ich poprawne działanie (numer bitu to wartość z zakresu od 0 do (sizeof(unsigned)<<3)-1).
(2 punkty, kontynuacja poprzedniego zadania) Zaprogramuj analogiczne funkcje działające na całych tablicach:
int jakiBit (unsigned *tablica, int nrBitu);
void ustawBit (unsigned *tablica, int nrBitu, int wartosc);
Następnie napisz krótki program testowy, sprawdzający ich poprawne działanie (numer bitu to nieujemna liczba całkowita).
(5 punktów, kontynuacja poprzedniego zadania) Zadeklaruj globalną tablicę unsigned sito[] o najmniejszym możliwym rozmiarze, która będzie zawierała co najmniej MAX_BIT bitów (wartość MAX_BIT zdefiniuj dyrektywą #define dla preprocesora). Zaprogramuj dodatkową funkcję, która wypełni tą tablicę wartościami 1 tylko na tych pozycjach, które odpowiadają liczbom pierwszym (na i-tej pozycji znajduje się 1 tylko wtedy, gdy liczba i jest pierwsza):
void sitoEratostenesa ();
Popraw funkcje jakiBit() i ustawBit(), tak aby sprawdzały one wartość parametru nrBitu (dla wartości <0 lub ≥MAX_BIT funkcja jakiBit() zawsze zwraca 0 a funkcja ustawBit() nie robi nic). Napisz też funkcję, która dla zadanej liczby całkowitej sprawdzi, czy jest ona pierwsza (zwracana wartość to 1) czy nie (zwracana wartość to 0); dla liczb >(MAX_BIT-1)² funkcja może nie odpowiadać (zwracana wartość to -1):
int czyPierwsza (int liczba);
Następnie napisz krótki program testowy, wypisujący wszystkie liczby pierwsze niewiększe od zadanej liczby wczytanej ze standardowego wejścia. Komunikaty zachęcające do wpisywania danych należy kierować na standardowe wyjście dla błędów.
(5 punktów, kontynuacja poprzedniego zadania) Podziel poprzednie zadanie na trzy części: plik nagłówkowy (z dyrektywami włączania warunkowego #ifndef i #endif dla preprocesora) z deklaracją funkcji do testowania pierwszości liczby, plik źródłowy z implementacją funkcji z pliku nagłówkowego (oraz lokalnymi funkcjami pomocniczymi i tablicą bitową z sitem Eratostenesa), a także plik źródłowy z funkcją main(), która w pętli będzie wczytywała liczbę całkowitą i wypisywała komunikat o jej pierwszości.

(2 punkty) Średniej wielkości tablicę liczb całkowitych (jej rozmiar określ dyrektywą #define dla preprocesora) wypełnij losowymi wartościami z zakresu -999...999. Następnie wypisz te wartości na standardowym wyjściu w 10 kolumnach. Przy każdym uruchomieniu programu losowane wartości powinny być inne (wywołaj funkcję srand((unsigned)time(NULL)) na początku programu). Do wypełniania tablicy losowymi wartościami użyj osobnej funkcji.
(3 punkty) Średniej wielkości tablicę liczb całkowitych (jej rozmiar określ dyrektywą #define dla preprocesora) wypełnij losowymi wartościami z zakresu 0...999999999 z rozkładem jednostajnym (każda wartość ma być jednakowo prawdopodobna). Następnie oblicz wypisz na standardowym wyjściu średnią arytmetyczną wszystkich wylosowanych przez ciebie liczb. Do wypełniania tablicy losowymi wartościami i do obliczania wartości średniej użyj osobnych funkcji. Czy otrzymywane w trakcie testowania wyniki były zbliżone do 499999999.5?

Lista 6 (29 listopada 2005): 11 punktów.

Jeszcze raz przeczytaj z książki B.W.Kernighana i D.M.Ritchiego Język ANSI C rozdział 4: Funkcje i struktura programu. Zwróć szczególną uwagę na dyrektywy dla preprocesora.

(11 punktów) W pliku nagłówkowym zadeklaruj dwie funkcje: fibonacci_iter (int n) i fibonacci_rek (int n), które będą wyliczać zadaną liczbę Fibonacciego w sposób iteracyjny i rekurencyjny. Implementację tych funkcji umieść w pliku pliku źródłowym, w którym na początku włączysz wspomniany plik nagłówkowy dyrektywą #include (dyrektywy włączania warunkowego #ifndef i #endif umieść tylko w pliku nagłówkowym). W kolejnym pliku źródłowym napisz program, który będzie testował czas działania (najlepiej z dokładnościa do milisekund) obu funkcji wyliczających liczby Fibonacciego i wypisywał na bieżąco te czasy na standardowym wyjściu w formie tabelarycznej dla kolejnych wartości poczynając od 1.
Uwaga: Liczby Fibonacciego są zdefiniowane wzorem rekurencyjnym: F₀=0, F₁=1 i F_n=F_n-1+F_n-2 dla n≥2.
Uwaga: Do mierzenia czasu wykonania określonego fragmentu programu skorzystaj z funkcji ftime(struct timeb *tp) zadeklarowanej w pliku nagłówkowym sys/timeb.h, wywołując ją dwukrotnie (tuż przed uruchomieniem procedury oraz tuż po jej zakończeniu) i wyliczając różnicę czasów.
(11 punktów) W pliku nagłówkowym zadeklaruj funkcję porownajizamien (double *p1, double *p2), która ma porównać ze sobą dwie liczby rzeczywiste wskazywane przez argumenty funkcji, a jeśli pierwsza z nich będzie większa od drugiej, to zamienia je miejscami. Implementację tej funkcji umieść w pliku pliku źródłowym, w którym na początku włączysz wspomniany plik nagłówkowy dyrektywą #include (dyrektywy włączania warunkowego #ifndef i #endif umieść tylko w pliku nagłówkowym). Implementując funkcję porownajizamien() skorzystaj z dwóch funkcji pomocniczych: porownaj (double d1, double d2) i zamien (double *p1, double *p2). Funkcja porownaj() ma porównywać dwie liczby rzeczywiste i odpowiadać wartością -1, 0 lub 1 gdy liczba pierwsza jest w stosunku do drugiej odpowiednio mniejsza, równa lub większa. Natomiast funkcja zamien() ma zamieniać miejscami wskazywane przez argumenty liczby rzeczywiste. Ogranicz zasięg widoczności tych funkcji tylko do tego pliku, w którym są one zdefiniowane. W kolejnym pliku źródłowym napisz program, który będzie wypełniał tablicę liczb rzeczywistych o określonym rozmiarze (dyrektywa #define) losowymi wartościami z zakresu od -99 do 99, sortował je metodą bąbelkową i wypisywał już uporządkowane na standarowym wyjściu. Wypełnanie tablicy losowymi wartościami powinno być zaprogramowane w osobnej funkcji losuj (int rozm, double *tab). Do sortowania tablicy liczb także napisz osobną funkcję sortowaniebabelkowe (int rozm, double *tab), która będzie korzystała z funkcji porownajizamien() zadeklarowanej w pliku nagłówkowym. Zmierz czas działania (z dokładnością do milisekund) samego procesu sortowania i wypisz go na standardowym wyjściu dla błędów.
Uwaga: Do mierzenia czasu wykonania określonego fragmentu programu skorzystaj z funkcji ftime(struct timeb *tp) zadeklarowanej w pliku nagłówkowym sys/timeb.h, wywołując ją dwukrotnie (tuż przed uruchomieniem procedury oraz tuż po jej zakończeniu) i wyliczając różnicę czasów.

Lista 7 (6 grudnia 2005): 14 punktów.

Przeczytaj z książki B.W.Kernighana i D.M.Ritchiego Język ANSI C rozdział 5: Wskaźniki i tablice.

(2 punkty) Zaprogramuj funkcję, która dla zadanego znaku char oraz słowa char[] zwróci wskaźnik do pierwszego wystąpienia tego znaku w słowie lub NULL jeżeli znak nie występuje. Następnie napisz program, który wczyta napis i sprawdzi (korzystając z tej funkcji), które samogłoski występują w tym napisie, a które w ogóle w nim nie występują.
Uwaga: Program powinien wypisać wszystkie samogłoski występujące w napisie.
(2 punkty) Zaprogramuj funkcję, która pobiera dwa wskaźniki do łańcuchów znakowych i sprawdza, czy pierwszy występuje w drugim. Następnie napisz program, który wczyta określoną liczbę napisów i sprawdzi czy istnieją wśród nich takie pary, że jeden napis występuje w drugim.
Uwaga: Program powinien wypisać wszystkie takie pary.
(3 punkty) Napisz program, który wczyta określoną liczbę napisów, a następnie wypisze je uporządkowane leksykograficznie.
Uwaga: Twój program powinien porządkować tylko tablicę ze wskaźnikami na napisy (sortowanie napisów poprzez przestawianie wskaźników do tablic znakowych).
Wskazówka: Do porównywania napisów użyj funkcji z biblioteki standardowej strcmp().
(2 punkty) Napisz program, który wczyta nie więcej niż 1000000000 liczb całkowitych z zakresu od 0 do 999 i wypisze liczbę wystąpień (o ile jest niezerowa) każdej liczby z tego zakresu.
(2 punkty) Napisz program, który wypełni losowymi wartościami całkowitymi z zakresu od 0 do 999 tablicę liczb o określonym rozmiarze, a następnie wyznaczy wszystkie pary liczb różniące się o jakąś potęgę 2 (czyli o 1, 2, 4,... 512).
Uwaga: Program powinien wypisać wszystkie takie pary.
(3 punkty) Zaprogramuj funkcję, która będzie mnożyła dwie kwadratowe macierze liczb. Rozmiar tych macierzy jest przekazywany jako parametr wywołania. Funkcja ta ma umieszczać wynik w tablicy, do której wskaźnik także jest przekazywany poprzez parametr wywołania funkcji. Następnie napisz program, który wczyta niedużą liczbę naturalną n i podniesie do potęgi n-tej macierz A. Sama macierz A ma wymiary 2x2 i jest cała wypełniona jedynkami za wyjątkiem pierwszego zerowego elementu (a_1,1=0 oraz a_1,2=a_2,1=a_2,2=1).
Uwaga: Program powinien wypisać macierz Aⁿ.

(7 punktów) Napisz program, który będzie w pętli wczytywał ze standardowego wejścia liczby całkowite z zakresu od 0 do 999 i wypisywał je w postaci słownej w języku polskim na standardowe wyjście. Program ma zakończyć działanie dopiero po wczytaniu liczby spoza tego zakresu. Komunikaty zachęcające do wprowadzania danych wypisuj na standardowe wyjście dla błędów.
Uwaga: Zamieniając liczbę na postać słowną skorzystaj z zainicjalizowanych tablic globalnych JEDNOSCI[20], DZIESIATKI[10] i SETKI[10]. Tablice te zdefiniuj w oddzielnym pliku źródłowym, a w pliku nagłówkowym umieść stosowne deklaracje zapowiadające.
Uwaga: Przy zamianie liczby na postać słowną skorzystaj z funkcji, która będzie zwracała wskaźnik do powstałego napisu (lokalna zmienna statyczna). Napis ten nie powinien posiadać żadnych spacji na początku i na końcu, a poszczególne liczebniki powinny być pooddzielane dokładnie jedną spacją.
(7 punktów, kontynuacja poprzedniego zadania) Napisz program, który będzie w pętli wczytywał ze standardowego wejścia liczby całkowite z zakresu od -999999999 do 999999999 i wypisywał je w postaci słownej w języku polskim na standardowe wyjście. Program ma zakończyć działanie dopiero po wczytaniu liczby spoza tego zakresu.
Uwaga: Pamiętaj o poprawnej odmianie liczebników tysiąc i milion.

Lista 8 (13 grudnia 2005): 12 punktów.

Przeczytaj z książki B.W.Kernighana i D.M.Ritchiego Język ANSI C rozdział 6: Struktury.

(5 punktów) W pliku nagłówkowym zdefiniuj strukturę struct Student z trzema polami: imie, nazwisko i indeks. Zadeklaruj także funkcję porownaj() do porównywania studentów (leksykograficzne najpierw według nazwiska, podem według imienia, a gdy obie te wartości są równe to według numeru indeksu). Dalej, w oddzielnym pliku źródłowym zdefiniuj tą funkcję. W następnym pliku źródłowym napisz program, który wczyta pewną liczbę studentów (podaną przez użytkownika w trakcie działania programu) do tablicy ze studentami, posortuje wszystkie wczytane rekordy przy pomocy funkcji porównującej i wypisze je w porządku niemalejącym na standardowym wyjściu.
Uwaga: Do sortowania godzin zapisanych w tablicy napisz oddzielną funkcję.
(7 punktów) W pliku nagłówkowym zdefiniuj strukturę struct Godzina z czterema polami bitowymi: godz, min, sek i setne_sek, wszystkie zadeklarowane jako unsigned int. Zadeklaruj także dwie funkcje: jedną ustaw() do nadawania nowych wartości w strukturze reprezentującej godzinę (o ile podane w argumentach wartości są prawidłowe) i drugą porownaj() do porównywania godzin zapisanych w takich strukturach (w obu przypadkach do funkcji należy przekazywać wskaźniki do struktur). Dalej, w oddzielnym pliku źródłowym zdefiniuj obie funkcje. W następnym pliku źródłowym napisz program, który wczyta pewną liczbę godzin (podaną przez użytkownika w trakcie działania programu) do tablicy z godzinami, posortuje wszystkie wczytane rekordy od najwcześniejszej do najpóźniejszej przy pomocy funkcji porównującej i wypisze je w porządku niemalejącym na standardowym wyjściu.
Uwaga: Do sortowania godzin zapisanych w tablicy napisz oddzielną funkcję.

(5 punktów) Napisz program, który wszystkie liczby w systemie dziesiętnym podane jako parametry wywołania programu wypisze na standardowe wyjście w systemie rzymskim. Twój program powinien sprawdzać, czy dany argument wywołania programu jest liczbą dziesiętną z zakresu od 1 do 3999, a jeśli nie to go pomijać (skorzystaj z funkcji atoi()).
Uwaga: Do zamiany liczby całkowitej na postać rzymską napisz oddzielną funkcję, która będzie zwracać wskaźnik do napisu reprezentującego określoną wartość (wynik umieszczaj w lokalnej statycznej tablicy znakowej).
Uwaga: Przy zamianie liczby na postać rzymską skorzystaj z globalnej tablicy struktur struct Rzym. Struktura ta powinna posiadać dwa pola: wskaźnik na napis char* reprezentujący liczbę w zapisie rzymskim i odpowiadającą mu wartość całkowitą int. Tablicę tą zainicjuj strukturami odpowiadającymi następującym liczbom: 1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4 i 1.
Uwaga: Wartości cyfr w rzymskim systemie liczbowym:

cyfra rzymska wartość

I 1

V 5

X 10

L 50

C 100

D 500

M 1000
(7 punktów, kontynuacja poprzedniego zadania) Napisz program, który wszystkie liczby w systemie rzymskim podane jako parametry wywołania programu wypisze na standardowe wyjście w systemie dziesiętnym.
Uwaga: Do zamiany liczby rzymskiej na wartość całkowitą napisz oddzielną funkcję.
Uwaga: Przy zamianie liczby rzymskiej na wartość całkowitą skorzystaj z globalnej tablicy struktur struct Rzym zdefiniowanej jak w poprzednim zadaniu. Tablicę tą zainicjuj strukturami o odpowiednio dobranych wartościach.

Lista 9 (20 grudnia 2005): 15 punktów.

Przeczytaj z książki B.W.Kernighana i D.M.Ritchiego Język ANSI C rozdział 6: Struktury. Zapoznaj się z funkcjami przydzielającymi pamięć na stercie (malloc() i calloc()) i funkcją zwalniającą wcześniej przydzieloną pamięć (free()). Potem przeczytaj jeszcze raz podrozdział poświęcony strukturom dynamicznym i zastanów się nad tworzeniem takich struktur właśnie na stercie.

(7 punktów) W pliku nagłówkowym zdefiniuj strukturę reprezentującą element listy jednokierunkowej struct ElementLiczbowy , w której będą pola nast wskazujące na element tego samego typu oraz wartosc przechowujące liczbę rzeczywistą:
struct ElementLiczbowy { ElementLiczbowy *nast; double wartosc; }; Oprócz struktury zadeklaruj również funkcje wstawNaPocz() (wstawienie nowego elementu na początek listy), wstawNaKon() (wstawienie nowego elementu na koniec listy), policz() (policzenie ile jest elementów na liście) oraz wypisz() (wypisanie kolejno wszystkich wartości zapamiętanych w liście). Jednym z parametrów tych funkcji powinien być wskaźnik na pierwszy element listy. Dalej, w oddzielnym pliku źródłowym zdefiniuj wymienione funkcje (zaimplementuj je iteracyjnie). W oddzielnym pliku źródłowym napisz program testujący działanie zdefiniowanej przez Ciebie struktury danych. Testowanie ma się odbywać w sposób interakcyjny, a więc program ma realizować wydawane na konsoli polecenia. Powinniśmy mieć możliwość wydawania następujących rozkazów:
- sprawdzenie liczby elementów na liście:
  > rozmiar 2 >
- dopisanie elementu na początku listy:
  > poczatek 17 >
- dopisanie elementu na końcu listy:
  > koniec 43 >
- wypisanie wszystkich elementów listy:
  > wypisz 17, 23, 37, 43 >
- wyjście z programu:
  > stop
Uwaga: Program ma być odporny na błędy użytkownika.
(5 punktów, kontynuacja poprzedniego zadania) Do poprzedniego zadania dopisz funkcje wstaw() (wstawienie nowego elementu na i-tą pozycję w liście: i-ta pozycja oznacza, że i elementów poprzedza dany element) i usun() (usunięcie elementu z i-tej pozycjji w liście). Tak jak poprzednio, delaracje obu funkcji mają być umieszczone w pliku nagłówkowym, a definicje w pliku źródłowym (zaimplementuj je iteracyjnie). W programie testującym dopisz dwa rozkazy: wstaw i usun.
(3 punkty, kontynuacja poprzedniego zadania) Do poprzedniego zadania dopisz funkcję odwroc() (odwrócenie kolejności elementów na liście). Tak jak poprzednio, delaracja funkcji ma być umieszczona w pliku nagłówkowym, a definicja w pliku źródłowym (zaimplementuj ją iteracyjnie). W programie testującym dopisz rozkaz: odwroc.

(5 punktów) W pliku nagłówkowym zdefiniuj strukturę reprezentującą element drzewa binarnych poszukiwań struct ElementBST , w której będą pola lewy wskazujące na lewego syna (element tego samego typu), prawy wskazujące na prawego syna (element tego samego typu) oraz wartosc przechowujące liczbę rzeczywistą:
struct ElementBST { ElementBST *lewy, *prawy; double wartosc; }; Oprócz struktury zadeklaruj również funkcje wstaw() (wstawienie nowego elementu do drzewa), policz() (policzenie ile jest elementów w drzewie) oraz wypisz() (wypisanie wszystkich wartości zapamiętanych w drzewie w sposób uporządkowany: metoda in-order). Jednym z parametrów tych funkcji powinien być wskaźnik na korzeń drzewa. Dalej, w oddzielnym pliku źródłowym zdefiniuj wymienione funkcje (zaimplementuj je rekurencyjnie). W oddzielnym pliku źródłowym napisz program testujący działanie zdefiniowanej przez Ciebie struktury danych. Testowanie ma się odbywać w sposób interakcyjny, a więc program ma realizować wydawane na konsoli polecenia. Powinniśmy mieć możliwość wydawania następujących rozkazów:
- sprawdzenie liczby elementów w drzewie:
  > rozmiar 8 >
- dopisanie elementu do drzewa:
  > wstaw 23 >
- wypisanie wszystkich elementów drzewa w sposób uporządkowany:
  > wypisz 17, 23, 37, 43 >
- wyjście z programu:
  > stop
Uwaga: Program ma być odporny na błędy użytkownika.
(5 punktów, kontynuacja poprzedniego zadania) Do poprzedniego zadania dopisz funkcje szukaj() (sprawdzenie czy element z podaną wartością jest w drzewie) i usun() (usunięcie elementu podaną wartością z drzewa). Tak jak poprzednio, delaracje obu funkcji mają być umieszczone w pliku nagłówkowym, a definicje w pliku źródłowym (zaimplementuj je rekurencyjnie). W programie testującym dopisz dwa rozkazy: szukaj i usun.
(5 punktów, kontynuacja poprzedniego zadania) Do poprzedniego zadania dopisz funkcję drukuj() (wyświetlenie struktury drzewa wraz z wartościami w węzłach). Przykładowe wywołanie tej funkcji w programie testującym może wygenerować następujący wynik:
> drukuj +--*11 | +--*13 +--*17 | +--*23 *37 +--*43 | +--*47 +--*53 +--*57 > Tak jak poprzednio, delaracja funkcji ma być umieszczona w pliku nagłówkowym, a definicja w pliku źródłowym (zaimplementuj ją rekurencyjnie). W programie testującym dopisz rozkaz: drukuj.

Lista 10 (3 stycznia 2006): 10 punktów.

Przeczytaj z książki B.W.Kernighana i D.M.Ritchiego Język ANSI C rozdział 7: Wejście i wyjście.

(2 punkty) Napisz program, który wczyta nazwę pliku tekstowego, a następnie wypisze jego zawartość, o ile plik istnieje, na standardowym wyjściu. Plik należy napierw otworzyć do czytania, potem przeczytać go linia po linii, a na końcu zamknąć. Jeśli linia jest dłuższa niż 79 znaków, to pozostałe znaki w tej linii należy zignorować.
Uwaga: Należy korzystać tylko z funkcji standardowych zadeklarowanych w pliku nagłówkowym <stdio.h>.
Wskazówka: Posłuż się funkcją fgets().
(3 punkty) Napisz program, który wczyta nazwę pliku tekstowego, a następnie zapisze w nim 1000 pierwszych liczb pierwszych (2, 3, 5, 7, ...). Plik należy napierw otworzyć do pisania, potem zapisać w nim tysiąc liczb (każda w osobnej linii), a na końcu zamknąć.
Uwaga: Należy korzystać tylko z funkcji standardowych zadeklarowanych w pliku nagłówkowym <stdio.h>.
Wskazówka: Zaprogramuj sito Eratostenesa.
(5 punktów) W tekstowym pliku z danymi jest zapisanych N liczb rzeczywistych a₁, ..., a_N. Format pliku z danymi jest taki, że w pierwszej linii jest zapisana liczba całkowita N typu int, a w kolejnych liniach pooddzielane białymi znakami wartości rzeczywiste a₁, ..., a_N typu double. Należy te liczby odczytać, zapamiętując je równocześnie w dynamicznie przydzielonej tablicy. Na koniec trzeba je zapisać do pliku binarnego (bez wartości N na początku) i zwolnić przydzieloną pamięć.
Uwaga: Należy korzystać tylko z funkcji standardowych zadeklarowanych w pliku nagłówkowym <stdio.h>.
(5 punktów, kontynuacja poprzedniego zadania) W binarnym pliku z danymi jest zapisane są liczby typu double. Określ ile tych liczb jest zapisanych w pliku, przydziel dynamicznie odpowiedni obszar pamięci i wczytaj je tam. Następnie policz średnią arytmetyczną i odchylenie standardowe i wypisz te wielkości na standardowym wyjściu. Na końcu zwolnij przydzieloną pamięć.
Uwaga: Należy korzystać tylko z funkcji standardowych zadeklarowanych w pliku nagłówkowym <stdio.h>.
Uwaga: W celu określenia ilości zapisanych w pliku binarnym danych posłuż się funkcjami fseek() i ftell().

Lista 11 (10 stycznia 2006): 12 punktów.

Argumenty wywołania programu i operacje na plikach.

(5 punktów) Napisz program, który przekopiuje zawartość jednego pliku do drugiego. Nazwy plików mają być podawane jako argumenty wywołania programu. Jeżeli plik docelowy już istnieje, program powinien się zapytać użytkownika, czy chce zastąpić plik, dołączyć pierwszy do drugiego, zmienić nazwę drugiego, czy też zrezygnować.
Uwaga: Pamiętaj, że w pierwszym pliku mogą się znaleźć dowolne znaki ASCII.
Wskazówka: Sprawdź, czy program wywołano z prawidłową liczbą argumentów, oraz czy podane nazwy są poprawnymi nazwami plików i czy pierwszy z nich istnieje w lokalnym systemie.
(5 punktów) Napisz program, który porówna ze sobą zawartości dwóch plików. Nazwy plików mają być podawane jako argumenty wywołania programu. Po napotkaniu pierwszej różnicy program powinien wypisać numer wiersza i numer pozycji w wierszu, w którym występuje różnica, po czym przerwać dalsze porównywanie.
Uwaga: Pamiętaj, że w plikach mogą się znaleźć dowolne znaki ASCII.
Wskazówka: Sprawdź, czy program wywołano z prawidłową liczbą argumentów, oraz czy podane nazwy są nazwami istniejących plików w lokalnym systemie.
(7 punktów) Napisz program, który (de)szyfruje podany w linii poleceń plik. Kluczem powinno być jedno słowo podawane jako drugi argument wywołania programu. Szyfrowanie powinno cyklicznie "przykładać" klucz do pliku i odpowiednio modyfikować jego zawartość. Na parach kolejnych znaków pliku i klucza wykonuj operację XOR (^); kiedy zabraknie liter klucza, należy zacząć ponownie od jego początku. Metodę szyfrowania tekstu zadanym kluczem zaprogramuj koniecznie jako oddzielną funkcję (zadeklarowaną w pliku nagłówkowym).
Wskazówka: Sprawdź, czy program wywołano z prawidłową liczbą argumentów, oraz czy podana nazwa pliku jest nazwą istniejącego pliku w lokalnym systemie.
(7 punktów) Napisz program, który przeszuka podany w linii poleceń plik w poszukiwaniu zadanego słowa. Słowo to ma być podawane jako drugi argument wywołania programu. Program powinien wypisać wszystkie wiersze zawierające zadane słowo. Algorytm wyszukiwania słowa w tekście zaprogramuj koniecznie jako oddzielną funkcję (zadeklarowaną w pliku nagłówkowym).
Wskazówka: Sprawdź, czy program wywołano z prawidłową liczbą argumentów, oraz czy podana nazwa pliku jest nazwą istniejącego pliku w lokalnym systemie.

Lista 12 (17 stycznia 2006): 11 punktów.

Argumenty wywołania programu i generator liczb pseudolosowych.

(11 punktów) Napisz program, który wygeneruje losowy labirynt na planszy o zadanych rozmiarach. Rozmiary labiryntu mają być podawane jako argumenty wywołania programu (19x19 to rozmiar maksymalny). Labirynt (komnaty z przejściami) pamiętaj w prostokątnej tablicy int[][]. Każda ściana komnaty ma być opisana jednym bitem (bit 0 dla sciany górnej, bit 1 dla sciany prawej, bit 2 dla sciany dolnej i bit 3 dla sciany lewej): jeśli bit jest ustawiony na 1, to jest przejście do następnej komnaty, a jeśli na 0, to przejścia nie ma. Po wygenerowaniu labiryntu wydrukuj go na standardowym wyjściu przy pomocy znaków +, -, | i spacji, tak jak w przykładzie zamieszczonym poniżej.
Uwaga: Pomiędzy dwiema komnatami musi istnieć dokładnie jedna droga.
Uwaga: Labirynt ma być dookoła otoczony ścianami.
Wskazówka: Pomyśl o labiryncie jak o drzewie rozpinającym grafu, który jest kratą.
Przykład: Wydrukowany labirynt 3x4 może wyglądać następująco: +---+---+---+---+ | | | | + +---+ + + | | +---+ + +---+ | | | +---+---+---+---+

(11 punktów) Napisz program, który wygeneruje losową krzyżówkę na planszy o zadanych rozmiarach. Rozmiary krzyżówki mają być podawane jako argumenty wywołania programu (19x19 to rozmiar maksymalny). Krzyżówkę (pola czarne i białe z przejściami) pamiętaj w prostokątnej tablicy int[][]. Każda ściana pola ma być opisana jednym bitem (bit 0 dla sciany górnej, bit 1 dla sciany prawej, bit 2 dla sciany dolnej i bit 3 dla sciany lewej): jeśli bit jest ustawiony na 1, to sąsiednie pole jest białe, a jeśli na 0, to sąsiednie pole jest czarne; ponadto musi być opisany kolor pola (bit 4 dla koloru): jeśli bit jest ustawiony na 1, to pole jest białe, a jeśli na 0, to pole jest czarne. Po wygenerowaniu krzyżówki wydrukuj ją na standardowym wyjściu przy pomocy znaków +, -, |, # i spacji, tak jak w przykładzie zamieszczonym poniżej.
Uwaga: Długości słów w krzyżówce nie mogą być krótsze niż 3-literowe.
Uwaga: Pomiędzy każdą parą białych pól powinna istnieć biała droga.
Uwaga: Przy każdym boku krzyżówki powinno się znaleźć jakieś białe pole.
Uwaga: W krzyżówce nie może być jednokolorowych prostokątów większych niż 2x2.
Wskazówka: Dopuszczam drobne odstępstwa od powyższych reguł.
Przykład: Wydrukowana krzyżówka 7x3 może wyglądać następująco: +---+---+---+ | | | | +---+---+---+ | | # | # | +---+---+---+ | | | | +---+---+---+ | # | # | | +---+---+---+ | | | | +---+---+---+ | | # | | +---+---+---+ | | # | | +---+---+---+

Lista 13 (24 stycznia 2006): 11 punktów.

Argumenty wywołania programu i dynamiczne struktury danych.

(11 punktów) Napisz program, który przekształci wyrażenie infiksowe z nawiasami do postfiksowej postaci Łukasiewicza (odwrotna notacja polska). Wyrażenie infiksowe ma być podane jako argument wywołania programu. Wyrażenie infiksowe nie może zawierać w środku żadnej spacji. Postfiksowa postać wyrażenia powinna być przechowywana w kolejce. Program powinien wypisać podane wyrażenie infiksowe w postaci postfiksowej (poszczególne elementy tego wyrażenia mają być pooddzielane pojedynczymi spacjami), a potem obliczyć i wypisać wartość tego wyrażenia.
Wyrażenie infiksowe jest wyrażeniem arytmetycznym w naturalnej (dla przeciętnego człowieka) postaci. Składa się ono z liczb rzeczywistych połączonych operatorami i pogrupowanych przy pomocy nawiasów. Nawiasy służą do zmiany kolejności obliczeń wynikającej z priorytetów użytych operatorów. Dla uproszczenia przyjmiemy, że wszystkie operatory są binarne (nie ma unarnego operatora minus, zmieniającego znak wyrażenia na przeciwny): mamy więc dodawanie (symbol +), odejmowanie (symbol -), mnożenie (symbol *) i dzielenie (symbol /). Priorytety dodawania i odejmowania są niższe niż mnożenia i dzielenia (najpierw mnożymy i dzielimy, a potem dodajemy i odejmujemy); ponadto dodawanie ma taki sam priorytet jak odejmowanie, a mnożenie taki sam jak dzielenie (ciąg obliczeń o takim samym priorytecie wykonujemy od strony lewej do prawej). Co do liczb, to są dopuszczalne tylko nieujemne liczby rzeczywiste (aby dostać wartość o przeciwnym znaku należy ją odjąć od zera), w których ewentualna część ułamkowa jest zapisywana po kropce dziesiętnej.
Wyrażenie postfiksowe jest sposobem zapisu wyrażeń arytmetycznych, w którym symbol operatora operacji umieszczony jest po operandach, a nie pomiędzy nimi jak w konwencjonalnym zapisie algebraicznym. Zapis ten pozwala na całkowitą rezygnację z użycia nawiasów w wyrażeniach, jako że jednoznacznie określa kolejność wykonywanych działań.
Wskazówka: Do przekształcenia wyrażenia infiksowego na postfiksowe (odwrotna notacja polska) użyj dynamicznych struktur danych (stosy i kolejki) zrealizowanych na listach.
Wskazówka: Algorytm translacji wyrażenia arytmetycznego do postaci ONP jest następujący:
1. Przygotuj struktury danych: kolejkę, w której umieść kolejne symbole wyrażenia infiksowego (wejście); pomocniczy stos, początkowo pusty; pustą kolejkę na wyrażenie w postaci postfiksowej (wyjście).
2. pobierz symbol z kolejki wejściowej;
3. jeśli jest to operand (liczba), to dopisz go do kolejki wyjściowej;
4. jeśli jest to nawias otwierający (, to przepisz go na stos;
5. jeśli jest to nawias zamykający), to przepisz ze stosu do kolejki wyjściowej wszystkie symbole do nawiasu otwierającego i usuń ten nawias ze stosu (bez przepisywania go do kolejki wyjściowej;
6. jeśli jest to operator działania algebraicznego, to przepisz ze stosu do kolejki wyjściowej wszystkie operatory, które mają wyższy lub równy priorytet (jeśli priorytet operatora na wierzchu stosu jest mniejszy lub na stosie jest symbol nawiasu otwierającego lub stos jest pusty, to zakończ przepisywanie);
7. jeśli w kolejce wejściowej są jeszcze jakieś symbole, to przejdź do punktu 2;
8. przepisz wszystkie operatory ze stosu do kolejki wyjściowej.
Uwaga: Twój program powinien wyłapać ewentualne błędy w podanym do programu wyrażeniu.
Uwaga: Opis algorytmu konwersji wyrażenia z postaci konwencjonalnej do postaci ONP oraz algorytm obliczenia wartości wyrażenia zapisanego w postaci ONP można znaleźć na stronie Wikipedii.