Klasa 4 · rozdział 3 · lekcje 14–21

Stos, kolejka i ONP

Stos zdejmuje to, co położyłeś ostatnio. Kolejka oddaje to, co przyszło pierwsze. Odwrotna notacja polska ustawia działanie tak, że stos sam liczy wartość wyrażenia. Konwersja z zapisu szkolnego używa algorytmu stacji rozrządowej.

Po tym rozdziale powinieneś umieć

  • wyjaśnić LIFO i FIFO oraz podać zastosowanie stosu;
  • zaimplementować stos na tablicy i na vector, potem jako szablon klasy;
  • odróżnić zapis infiksowy, prefiksowy i ONP na przykładzie 2 3 +;
  • policzyć wartość wyrażenia ONP stosem, także na kartce;
  • zamienić infiks na ONP (nawiasy i priorytety) i połączyć to z obliczeniem;
  • obsłużyć pusty stos i złe wyrażenie wyjątkiem albo kodem.

1. Stos

Stos talerzy: kładziesz na wierzch, zdejmujesz z wierzchu. Ostatni położony schodzi pierwszy (LIFO). Nie sięgasz do środka. Operacje z lekcji: poloz, zdejmij, szczyt (podgląd bez zdejmowania), pusty, pelny.

Zastosowania, które naprawdę używają LIFO: cofanie ostatniej operacji, sprawdzanie nawiasów, wywołania funkcji (adres powrotu), obliczanie ONP. Kolejka ludzi do kasy stosem nie jest — tam pierwszy ma wyjść pierwszy.

Stos Kolekcja z dostępem tylko do szczytu. poloz(1) potem poloz(2): pierwsze zdejmij zwraca 2.

2. Tablica i vector

Szczyt leży pod indeksem ile - 1. Tablica o stałym limicie pokazuje, że pojemnik może być pełny. vector rośnie i pełnego stanu nie ma — zostaje tylko błąd pustego stosu.

class StosInt {
    static const int MAX = 100;
    int dane[MAX];
    int ile;
public:
    StosInt() : ile(0) {}
    bool pusty() const { return ile == 0; }
    bool pelny() const { return ile == MAX; }
    void poloz(int x) {
        if (pelny()) throw logic_error("stos pelny");
        dane[ile++] = x;
    }
    int zdejmij() {
        if (pusty()) throw logic_error("stos pusty");
        return dane[--ile];
    }
    int szczyt() const {
        if (pusty()) throw logic_error("stos pusty");
        return dane[ile - 1];
    }
};
class StosVector {
    vector<int> dane;
public:
    bool pusty() const { return dane.empty(); }
    void poloz(int x) { dane.push_back(x); }
    int zdejmij() {
        if (pusty()) throw logic_error("stos pusty");
        int x = dane.back();
        dane.pop_back();
        return x;
    }
};

Obie wersje dają ten sam ślad: poloz(10), poloz(20), poloz(30), zdejmij → 30, szczyt → 20. Różnica jest w limicie i w tym, kto zarządza pamięcią. Na sprawdzianie „zaimplementuj stos” piszesz klasę. Gotowe std::stack stosujesz tylko, gdy polecenie na to pozwala.

Pusty stos nie zwraca zera Zero może być prawdziwą wartością na stosie. Brak elementu to wyjątek albo kod PUSTY z poprzedniego rozdziału. Pytanie „czy pusty?” zostaje metodą bool.

3. Stos jako klasa-szablon

Nawiasy potrzebują stosu znaków, ONP — stosu liczb. Jedna klasa z parametrem typu. Metody zostają w klasie (szablon w nagłówku, nie w osobnym .cpp bez wywołań).

template <typename T>
class Stos {
    vector<T> dane;
public:
    bool pusty() const { return dane.empty(); }
    void poloz(const T& x) { dane.push_back(x); }
    T szczyt() const {
        if (pusty()) throw logic_error("stos pusty");
        return dane.back();
    }
    T zdejmij() {
        T x = szczyt();
        dane.pop_back();
        return x;
    }
};

Stos<char> znaki;
znaki.poloz('A');
cout << znaki.zdejmij();    // A

Pola są prywatne. main nie pisze dane[0]. To jest stos „jako klasa”, nie luźne funkcje przy tablicy globalnej.

4. Kolejka

Kolejka w sklepie: kto stanął pierwszy, ten pierwszy wychodzi (FIFO). Dopisujesz na końcu, bierzesz z przodu. Te same liczby 10, 20, 30: ze stosu schodzi 30, z kolejki schodzi 10.

template <typename T>
class Kolejka {
    vector<T> dane;
public:
    bool pusta() const { return dane.empty(); }
    void dodaj(const T& x) { dane.push_back(x); }
    T pobierz() {
        if (pusta()) throw logic_error("kolejka pusta");
        T x = dane.front();
        dane.erase(dane.begin());
        return x;
    }
};

erase z przodu przesuwa resztę. Przy krótkiej kolejce na lekcji to jest czytelne. Stos do ONP i tak jest ważniejszy niż optymalna kolejka: wyrażenie liczy się LIFO, nie FIFO. Kolejka zostaje w programie tam, gdzie kolejność przyjścia ma zostać kolejnością obsługi (zadania do wydruku, klienci).

5. Infiks, prefiks, ONP

Szkolny zapis 2 + 3 jest infiksowy: operator stoi między argumentami. Trzeba znać priorytet (* przed +) i nawiasy. Prefiks stawia operator przed argumentami: + 2 * 3 4 to 2 + (3 · 4). ONP (odwrotna notacja polska, zapis postfiksowy) stawia operator po argumentach: 2 3 + to 2 + 3. 2 3 4 * + to 2 + (3 · 4).

InfiksPrefiksONPWartość
2 + 3+ 2 32 3 +5
2 + 3 * 4+ 2 * 3 42 3 4 * +14
(2 + 3) * 4* + 2 3 42 3 + 4 *20

W ONP nie ma nawiasów. Kolejność operatorów na końcu zastępuje priorytet i nawiasy. Dlatego do liczenia wystarczy stos, bez tabeli „co silniejsze”.

Najkrótszy sprawdzian 2 3 + nie jest infiksem. Infiks tego samego działania to 2 + 3. Kto czyta 2 3 + jako „dwadzieścia trzy dodać”, myli zapis z liczbą.

6. Obliczanie ONP

Wyrażenie jest ciągiem tokenów rozdzielonych spacją. Liczbę kładziesz na stos. Operator zdejmuje dwa elementy (najpierw prawy argument, potem lewy), liczy i kładzie wynik. Na końcu na stosie zostaje jedna liczba — to wartość. Tokeny na lekcji: liczby całkowite (także wielocyfrowe) oraz + - * /.

Ślad 2 3 4 * +:

  1. 2 — stos: 2
  2. 3 — stos: 2 3
  3. 4 — stos: 2 3 4
  4. * — zdejmij 4 i 3, połóż 12. Stos: 2 12
  5. + — zdejmij 12 i 2, połóż 14. Stos: 14
int obliczOnp(const string& onp) {
    Stos<int> s;
    for (int i = 0; i < (int)onp.size(); ) {
        if (onp[i] == ' ') { i++; continue; }
        if (isdigit((unsigned char)onp[i])) {
            int v = 0;
            while (i < (int)onp.size() && isdigit((unsigned char)onp[i]))
                v = v * 10 + (onp[i++] - '0');
            s.poloz(v);
        } else {
            char op = onp[i++];
            if (s.pusty()) throw logic_error("zle wyrazenie");
            int b = s.zdejmij();
            if (s.pusty()) throw logic_error("zle wyrazenie");
            int a = s.zdejmij();
            if (op == '+') s.poloz(a + b);
            else if (op == '-') s.poloz(a - b);
            else if (op == '*') s.poloz(a * b);
            else if (op == '/') {
                if (b == 0) throw logic_error("dzielenie przez zero");
                s.poloz(a / b);
            } else throw logic_error("zly operator");
        }
    }
    int wynik = s.zdejmij();
    if (!s.pusty()) throw logic_error("zle wyrazenie");
    return wynik;
}

obliczOnp("2 3 +") → 5. obliczOnp("2 3 4 * +") → 14. obliczOnp("2 3 + 4 *") → 20. obliczOnp("8 0 /") rzuca dzielenie przez zero. obliczOnp("+") rzuca „złe wyrażenie”, bo stos jest pusty przy operatorze. Kolejność zdejmowania ma znaczenie przy - i /: 8 2 - to 8 − 2 = 6, nie 2 − 8. Najpierw schodzi prawy argument.

isdigit jest w <cctype>. Rzutowanie na unsigned char jest tu po to, żeby funkcja dostała znak z właściwego zakresu.

7. Stacja rozrządowa

Algorytm Dijkstry (stacja rozrządowa) zamienia infiks na ONP. Na lekcji wyrażenie składa się z liczb, operatorów + - * / i nawiasów. Spacje wolno pominąć w infiksie. Wyjście jest ONP ze spacjami, gotowe dla obliczOnp.

  1. Liczbę dopisujesz od razu na wyjście.
  2. ( kładziesz na stos operatorów.
  3. ) zdejmuje operatory aż do (. Nawias otwierający zdejmujesz i wyrzucasz, nie na wyjście.
  4. Operator: zdejmuj ze stosu operatory o priorytecie większym lub równym (łączność lewostronna), potem połóż bieżący. Nie zdejmuj (.
  5. Na końcu opróżnij stos na wyjście. Zostawiony ( znaczy brak nawiasu.

Priorytet: + i - mają 1, * i / mają 2.

Ślad 2+3*4:

  • 2 → wyjście 2
  • + → stos: +
  • 3 → wyjście 2 3
  • * ma wyższy priorytet niż +, więc + zostaje. Stos: + *
  • 4 → wyjście 2 3 4
  • koniec: zdejmij *, potem + → 2 3 4 * +

Ślad (2+3)*4: po ) na wyjściu jest 2 3 +, stos pusty, potem * i 4 dają 2 3 + 4 *. Ślad 8-3-2: drugi minus zdejmuje pierwszy (ten sam priorytet, łączność w lewo) → 8 3 - 2 -, czyli (8 − 3) − 2 = 3, nie 8 − (3 − 2).

int priorytet(char op) {
    if (op == '+' || op == '-') return 1;
    if (op == '*' || op == '/') return 2;
    return 0;
}

string naOnp(const string& infiks) {
    Stos<char> stos;
    string wyj;
    for (int i = 0; i < (int)infiks.size(); ) {
        if (infiks[i] == ' ') { i++; continue; }
        if (isdigit((unsigned char)infiks[i])) {
            if (!wyj.empty()) wyj += ' ';
            while (i < (int)infiks.size() && isdigit((unsigned char)infiks[i]))
                wyj += infiks[i++];
        } else if (infiks[i] == '(') {
            stos.poloz(infiks[i++]);
        } else if (infiks[i] == ')') {
            i++;
            while (!stos.pusty() && stos.szczyt() != '(') {
                wyj += ' ';
                wyj += stos.zdejmij();
            }
            if (stos.pusty()) throw logic_error("brak nawiasu");
            stos.zdejmij();
        } else {
            char op = infiks[i++];
            while (!stos.pusty() && stos.szczyt() != '('
                   && priorytet(stos.szczyt()) >= priorytet(op)) {
                wyj += ' ';
                wyj += stos.zdejmij();
            }
            stos.poloz(op);
        }
    }
    while (!stos.pusty()) {
        if (stos.szczyt() == '(') throw logic_error("brak nawiasu");
        wyj += ' ';
        wyj += stos.zdejmij();
    }
    return wyj;
}

naOnp("2+3*4") → 2 3 4 * +. naOnp("(2+3)*4") → 2 3 + 4 *. naOnp("12+3") → 12 3 +. Liczba wielocyfrowa zostaje jednym tokenem.

8. Kalkulator

Kalkulator z planu to złożenie dwóch funkcji i obsługi błędów. Użytkownik podaje infiks. Program zamienia go na ONP, liczy wartość i wypisuje albo komunikat. Obie funkcje są bez cin. Stos jest w środku — wołający go nie widzi. To przygotowanie pod fasadę z rozdziału o wzorcach; tu jeszcze wolno wołać funkcje po imieniu.

int obliczInfiks(const string& wyrazenie) {
    return obliczOnp(naOnp(wyrazenie));
}

int main() {
    string w;
    getline(cin, w);
    try {
        cout << obliczInfiks(w);
    } catch (const logic_error& e) {
        cout << e.what();
    }
}

Testy, zanim uznasz kalkulator za gotowy:

WejścieWyjście
2+35
2+3*414
(2+3)*420
8-3-23
8/0komunikat o dzieleniu przez zero
(2+3komunikat o nawiasie
Najpierw kartka Dla (2+3)*4 rozpisz stos operatorów i wyjście po każdym znaku. Dopiero potem odpal program. Zgodność z tabelą powyżej jest warunkiem, nie ozdobą.

Ćwiczenia do samodzielnego wykonania

Folder: Dokumenty\cwiczenia-po\klasa-4\rozdzial-03.

Ćwiczenie 1. Ślad LIFO i FIFO łatwe

Na kartce: połóż 10, 20, 30 na stos i dodaj te same liczby do kolejki. Wypisz, co schodzi jako pierwsze z każdej struktury.

Ćwiczenie 2. Stos-klasa łatwe

Stos<int> na vector. Odtwórz ślad 30, potem 20. Pusty stos łapiesz w main.

Ćwiczenie 3. ONP na kartce średnie

Policz 2 3 +, 2 3 4 * + i 8 2 /. Wyniki: 5, 14, 4. Potem funkcją obliczOnp.

Ćwiczenie 4. Stacja średnie

naOnp dla 2+3*4, (2+3)*4 i 8-3-2. Wyniki: 2 3 4 * +, 2 3 + 4 *, 8 3 - 2 -.

Ćwiczenie 5. Kalkulator trudne

Połącz konwersję z ewaluacją. Sześć testów z tabeli rozdziału, w tym dwa błędne. Funkcje bez we/wy.

Ćwiczenie 6. Uzasadnienie trudne

W 6–8 zdaniach: czemu ONP liczy się stosem, a nie kolejką. Pokaż na 2 3 4 * +, który argument zszedłby z kolejki przy operatorze * i czemu wynik byłby zły.

Sprawdź się

1. Po poloz(1) i poloz(2) pierwsze zdejmij zwraca:
2. Zapis 2 3 + to:
3. Wartość ONP 2 3 4 * + wynosi:
4. (2+3)*4 w ONP to:
5. Przy operatorze w ONP najpierw zdejmujesz:

Wymagania na ocenę

Dział 3 planu (lekcje 14–21). Stos, kolejka i ONP są obowiązkowe. Ocena wyższa zawiera wymagania na oceny niższe.

OcenaUczeń
2 Wyjaśnia LIFO i podaje przykład użycia stosu. Odróżnia infiks od ONP na przykładzie 2 3 +. Wykonuje poloz/zdejmij według wzoru.
3 Implementuje stos (tablica lub vector) z poloz, zdejmij, szczyt, pusty. Wyjaśnia FIFO. Liczy proste ONP na kartce lub w programie.
4 Stos jest klasą z polami prywatnymi. Programuje ewaluację ONP. Obsługuje pusty stos. Implementuje kolejkę w podstawowym zakresie.
5 Definiuje szablon stosu. Konwertuje infiks do ONP (nawiasy, priorytety). Łączy konwersję z ewaluacją. Testuje błędne wyrażenia.
6 Projektuje kalkulator (wejście, konwersja, wynik, błędy). Uzasadnia, czemu służy stos, nie kolejka. Porównuje stos tablicowy ze stosem na vector.

Lista „już umiem”