AiSD (index)

AiSD (7) - ADT STACK

OBOWIĄZKOWE DO PRZESŁANIA: jedno zadanie

WPROWADZENIE

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:

• konstruktor tworzący pusty stos,
• testowanie, czy stos nie jest pusty [empty()],
• odczyt liczby elementów na stosie [size()],
• dołączanie elementu do stosu [push(item)],
• usuwanie ostatniego elementu ze stosu [pop()],
• dostęp do ostatniego elementu stosu [top()],
• czyszczenie stosu [clear()].

// 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(int 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(); }
    int size() const { return lst.size(); }
    int 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();
};

ODWROTNA NOTACJA POLSKA

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) |
+-------+-------+-----------------------------------------+

ZADANIE 7.1

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 );

ZADANIE 7.2

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().

ZADANIE 7.3

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().

ZADANIE 7.4

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łąjące w stałym czasie: (a) push_back() i pop_back(), (b) push_front() i pop_front().

ZADANIE 7.5

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.

ZADANIE 7.6

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.

AiSD (index)