OBOWIĄZKOWE DO PRZESŁANIA: jedno zadanie
Stos to ADT, który pozwala zapisywać dane i następnie pobierać je w kolejności odwrotnej do zapisu (ang. last in, first out, LIFO; ostatni wchodzi, pierwszy wychodzi). Typowe operacje dla ADT STACK są następujące:
// https://en.cppreference.com/w/cpp/container/stack // https://en.cppreference.com/w/cpp/container/deque #include <stack> // W STL stack jest zbudowany na bazie std::deque. // Przykład użycia stosu. std::stack<int> S; // stos liczb int na bazie deque assert( S.empty() ); for (auto item : {1, 2, 3, 5, 7}) S.push(item); // wstawienie do stosu assert( S.size() == 5 ); assert( S.top() == 7 ); S.top() = 77; // zmiana na szczycie stosu while (!S.empty()) { std::cout << S.top() << std::endl; // odczyt S.pop(); // usunięcie 77, 5, 3, 2, 1 }
// Interfejs stosu na bazie kontenera std::vector. template <typename T> class MyStack { std::vector<T> lst; public: MyStack(std::size_t s=10) { lst.reserve(s); } // default constructor ~MyStack() { lst.clear(); } MyStack(const MyStack& other); // copy constructor MyStack(MyStack&& other); // move constructor MyStack& operator=(const MyStack& other); // copy assignment operator, return *this MyStack& operator=(MyStack&& other); // move assignment operator, return *this bool empty() const { return lst.empty(); } // checks if the container has no elements bool full() const { return lst.size() == lst.capacity(); } std::size_t size() const { return lst.size(); } std::size_t max_size() const { return lst.capacity(); } void push(const T& item) { lst.push_back(item); } void push(T&& item) { lst.push_back(std::move(item)); } T& top() { return lst.back(); } // zwraca koniec, nie usuwa void pop() { lst.pop_back(); } // usuwa koniec void clear() { lst.clear(); } void display(); };
https://pl.wikipedia.org/wiki/Odwrotna_notacja_polska
Potrzebna jest implementacja stosu, która umożliwia przechowywanie na nim elementów dwóch różnych typów.
Zapis konwencjonalny: (2+3)*6 // wynik 30 Zapis w ONP: 2 3 + 6 * Zapis konwencjonalny: 6/2 // wynik 3 Zapis w ONP: 6 2 / Zapis konwencjonalny: +4-(-2) // wynik 6 Zapis w ONP: +4 -2 - Pseudokod algorytmu obliczania wartości wyrażenia w ONP: S = Stack() for item in input: if item is number: S.push(item) elif item is operator: a = S.pop() b = S.pop() S.push(b item a) // kolejność odwrotna! +-------+-------+-----------------------------------------+ | input | stack | operations | +-------+-------+-----------------------------------------+ | 2 | 2 | S.push(2) | | 3 | 2 3 | S.push(3) | | + | 5 | a = S.pop() ; b = S.pop() ; S.push(b+a) | | 6 | 5 6 | S.push(6) | | * | 30 | a = S.pop() ; b = S.pop() ; S.push(b*a) | +-------+-------+-----------------------------------------+
Zaimplementować algorytm obliczania wartości wyrażenia podanego w ONP. Zakładamy, że na wejściu będą liczby całkowite i cztery możliwe działania: "+", "-", "*", "/". Algorytm może mieć postać funkcji:
int rpn(const std::vector<std::string>& input); // for (auto w : input) { /* sprawdzanie w */ } // std::vector<std::string> input { "-6", "+2", "/" }; // assert( rpn(input) == -3 );
Przygotować implementację realizującą ADT STACK na bazie tablicy. Wykorzystać klasę ArrayList lub std::array. Operacje push() i pop() działające w stałym czasie można uzyskać przy użyciu push_back() i pop_back().
Przygotować implementację realizującą ADT STACK na bazie listy powiązanej pojedynczo. Wykorzystać klasę SingleList lub std::forward_list. Operacje push() i pop() działające w stałym czasie można uzyskać przy użyciu push_front() i pop_front().
Przygotować implementację realizującą ADT STACK na bazie listy powiązanej podwójnie. Wykorzystać klasę DoubleList lub std::list. Możliwe są dwa warianty realizacji push() i pop(), działające w stałym czasie: (a) push_back() i pop_back(), (b) push_front() i pop_front().
Zaimplementować algorytm dopasowywania ograniczników [Drozdek str. 134]. Algorytm wykorzystuje stos do przechowywania kolejno odczytanych ograniczników. Dla prostoty argumentem funkcji może być napis zawierający ograniczniki i inne znaki, komentarze w pierwszym przybliżeniu można pominąć. Funkcja zwraca bool.
Zaimplementować algorytm dodawania wielkich liczb całkowitych dodatnich [Drozdek str. 135]. Algorytm wykorzystuje trzy stosy do przechowywania cyfr: dla pierwszej liczby, dla drugiej liczby, dla wyniku. Dla prostoty argumentem funkcji będą dwa napisy zawierające ciągi cyfr. Funkcja zwraca napis będący ciągiem cyfr.