Zmienne dynamiczne, wskaźniki, dynamiczne struktury danych. Listy liniowe: budowa, operacje na listach. Stos: implementacja na liście.
Przed przystąpieniem do zajęć:
push(stos, element)
,
pop(stos, element)
, które odpowiednio pozwalają na
umieszczenie na stosie stos
i zdjęcie z niego elementu
+eleme, który jest liczbą całkowitą, oraz funkcje
empty(stos)
, print(stos)
, które pozwalają na uzyskanie
informacji, czy stos jest pusty oraz wyświetlenie na standardowym
wyjściu elementów znajdujących się na nim. Do tego dodaj funkcję
inicjuj(stos)
, która w poprawny sposób zainicjuje pusty stos.
Stos powinien zostać zrealizowany z wykorzystaniem dynamicznej listy
jednokierunkowej. Wszystkie funkcje z wyjątkiem funkcji
print
, która ma charakter pomocniczy, będą operowały jedynie
na początku listy. Opcjonalnie, w zastępstwie funkcji empty
można dostarczyć zmodyfikowaną funkcję pop
, której zwracana
wartość będzie informowała o tym, czy stos jest pusty czy nie.
Przetestuj funkcjonowanie przygotowanego stosu w serii próbnych wywołań w rodzaju (użyj gdzie trzeba operatora referencji/dereferencji):
init(stos); arg = 7; push(stos, arg); arg = 14; push(stos, arg); print(stos); arg = 7; pop(stos, arg); print(stos); printf("Zdjeta wartosc:%d\n",arg);
Program ma działać na liczbach całkowitych, czytając dane wejściowe
ze standardowego wejścia. W strumieniu wejściowym będą mogły pojawić
się liczby oraz symbole operacji w postaci znaków: +
,
-
, *
, i /
(dzielenie całkowitoliczbowe). Za
każdym razem, gdy na wejściu pojawi się liczba, zostaje ona
umieszczona na początku listy argumentów. Gdy pojawi się symbol
operacji, zostaje wykonane odpowiednie działanie na dwóch liczbach
pobranych z początku listy, z sygnalizacją błędu, gdyby na liście
były mniej niż dwie liczby. Wynik działania zostaje umieszczony na
początku listy argumentów. Tak używane listy nazywane są stosami
albo strukturami LIFO (ang. last-in-first-out, czyli
„ostatni wchodzi, pierwszy wychodzi''). Mówimy o umieszczaniu
danych na stosie (szczycie stosu) i zdejmowaniu ze stosu.
Jakkolwiek powyższy schemat daje pełny kalkulator czterodziałaniowy, w
omawianym programie powinno znaleźć się jeszcze kilka operacji dla
ułatwienia posługiwania się kalkulatorem. Wprowadźmy dodatkowy symbol
operacji P
, który będzie służył usunięciu ostatnio wprowadzonej
liczby i odpowiadał operacji pop
, to znaczy usuwaniu argumentu
ze szczytu stosu, oraz symbol operacji c
(clear), który będzie
„czyścił stos'', to znaczy usuwał z niego wszystkie elementy (takie
operatory mogą być przydatne dla korekcji błędów popełnionych przy
wpisywaniu danych). Kolejnym, dodatkowym operatorem będzie r
(reverse) i powinien on spowodować zamianę miejscami dwóch argumentów
na szczycie stosu. Dalej, podanie znaku d
(duplicate) ma
spowodować zduplikowanie argumentu znajdującego się na szczycie
stosu. Następnym użytym symbolem będzie p
(print) i jeśli pojawi
się w strumieniu wejściowym, powinien spowodować wydrukowanie szczytu
stosu oraz f
(full print), którego pojawienie się spowoduje
wydrukowanie zawartości całego stosu argumentów. Ostatni symbol, znak
q
będzie służył zakończeniu pracy programu.
Opisaną powyżej funkcjonalność zapewnia standardowy program
uniksowy dc
, będący kalkulatorem działającym w oparciu
o odwrotną notację polską. Przetestuj jego działanie. Więcej szczegółów: man dc
.
czytaj1.c
, czytaj2.c
i czytaj3.c
)
z propozycjami sposobu realizacji interfejsu użytkownika
rozpatrywanego programu, w zakresie rozróżniania wczytywanych
argumentów (liczb) od danych nieliczbowych (operatorów).
Przeanalizuj i przetestuj zaproponowane schematy postępowania, oceń ich
przydatność przy rozwiązywaniu postawionego zadania (odróżnianie
klas liczba/operator/pozostałe, umożliwienie wczytywania liczb ze znakiem).
dc
.
(2+4*5)/(1+7)
.
This document was generated using the LaTeX2HTML translator Version 2008 (1.71)
Copyright © 1993, 1994, 1995, 1996,
Nikos Drakos,
Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999,
Ross Moore,
Mathematics Department, Macquarie University, Sydney.
The command line arguments were:
latex2html -html_version 3.2,latin2,unicode -split 0 -no_navigation PProg_lab_06
The translation was initiated by Robert Muszyński on 2021-02-06