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.
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
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).
| Infiks | Prefiks | ONP | Wartość |
|---|---|---|---|
| 2 + 3 | + 2 3 | 2 3 + | 5 |
| 2 + 3 * 4 | + 2 * 3 4 | 2 3 4 * + | 14 |
| (2 + 3) * 4 | * + 2 3 4 | 2 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”.
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 * +:
2— stos: 23— stos: 2 34— stos: 2 3 4*— zdejmij 4 i 3, połóż 12. Stos: 2 12+— 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.
- Liczbę dopisujesz od razu na wyjście.
(kładziesz na stos operatorów.)zdejmuje operatory aż do(. Nawias otwierający zdejmujesz i wyrzucasz, nie na wyjście.- Operator: zdejmuj ze stosu operatory o priorytecie większym lub równym (łączność lewostronna), potem połóż bieżący. Nie zdejmuj
(. - 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ście2+→ stos:+3→ wyjście2 3*ma wyższy priorytet niż+, więc+zostaje. Stos:+ *4→ wyjście2 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ście | Wyjście |
|---|---|
| 2+3 | 5 |
| 2+3*4 | 14 |
| (2+3)*4 | 20 |
| 8-3-2 | 3 |
| 8/0 | komunikat o dzieleniu przez zero |
| (2+3 | komunikat o nawiasie |
(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ę
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.
| Ocena | Uczeń |
|---|---|
| 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. |