Matura: C++ - operacje na tekstach, cz.2

Problem jest następujący: mamy wiersz znaków, w którym należy zamienić wszystkie małe litery na duże. Zadanie rozwiązujemy następująco:

Przeglądamy kolejne znaki tekstu, jeśli natrafimy na małą literę, to od jej kodu odejmujemy 32. W efekcie otrzymamy kod ASCII litery dużej.

Problemem są polskie litery, które należy przetwarzać osobno, ponieważ ich kody nie podlegają tej regule. Jeśli napotkamy polską literę (ą, ć, ę...) zamieniamy ją odpowiednią literą dużą.

Algorytm: zamiana liter małych w duże

Dane wejściowe: s: tekst do do zamiany liter małych na duże
Dane wyjściowe: s: tekst z zamienionymi literami małymi na duże

Lista kroków:
K01: Dla i = 0,1,...,długość s - 1:
     wykonuj kroki K02...K03
K02:   Jeśli s[i] = mała litera,
       to s[i] ← s[i] - 32

K03:   Jeśli s[i] = mała polska litera,
       to s[i] ← = odpowiednia duża litera polska
K04: Zakończ

Program C++ dla cstring

// Zamiana na duże litery
//-----------------------

#include <iostream>
#include <cstring>

using namespace std;

void PL(char * t)
{
    while(*t)
    {
        switch((unsigned char)*t)
        {
            case 164 : *t = 165; break;
            case 143 : *t = 198; break;
            case 168 : *t = 202; break;
            case 157 : *t = 163; break;
            case 227 : *t = 209; break;
            case 224 : *t = 211; break;
            case 151 : *t = 140; break;
            case 141 : *t = 143; break;
            case 189 : *t = 175; break;
            case 165 : *t = 185; break;
            case 134 : *t = 230; break;
            case 169 : *t = 234; break;
            case 136 : *t = 179; break;
            case 228 : *t = 241; break;
            case 162 : *t = 243; break;
            case 152 : *t = 156; break;
            case 171 : *t = 159; break;
            case 190 : *t = 191; break;
            default  : break;
        }
        t++;
    }
}

int main()
{
    char s[100];
    int i,n;

    setlocale(LC_ALL,"");

    cout << "Wpisz tekst poniżej:" << endl << endl;
    cin.getline(s ,100); PL(s); // Odczytujemy tekst
    cout << endl;

    n = strlen(s);

    for(i = 0; i < n; i++)
    {
        if((s[i] >= 'a') && (s[i] <= 'z'))
            s[i] -= 32;
        else
            switch(s[i]) // Polskie litery
            {
                case 'ą': s[i] = 'Ą'; break;
                case 'ć': s[i] = 'Ć'; break;
                case 'ę': s[i] = 'Ę'; break;
                case 'ł': s[i] = 'Ł'; break;
                case 'ń': s[i] = 'Ń'; break;
                case 'ó': s[i] = 'Ó'; break;
                case 'ś': s[i] = 'Ś'; break;
                case 'ź': s[i] = 'Ź'; break;
                case 'ż': s[i] = 'Ż'; break;
            }
    }
    cout << s << endl << endl;

    return 0;
}

Wpisz tekst poniżej:

Książe, zażółć żabią jaźń.

KSIĄŻE, ZAŻÓŁĆ ŻABIĄ JAŹŃ.

Program C++ dla string

// Zamiana na duże litery
//-----------------------

#include <iostream>
#include <string>

using namespace std;

void PL(string & t)
{
    unsigned i,len = t.length();
    for(i = 0; i < len; i++)
        switch((unsigned char) t[i])
        {
            case 164 : t[i] = 165; break;
            case 143 : t[i] = 198; break;
            case 168 : t[i] = 202; break;
            case 157 : t[i] = 163; break;
            case 227 : t[i] = 209; break;
            case 224 : t[i] = 211; break;
            case 151 : t[i] = 140; break;
            case 141 : t[i] = 143; break;
            case 189 : t[i] = 175; break;
            case 165 : t[i] = 185; break;
            case 134 : t[i] = 230; break;
            case 169 : t[i] = 234; break;
            case 136 : t[i] = 179; break;
            case 228 : t[i] = 241; break;
            case 162 : t[i] = 243; break;
            case 152 : t[i] = 156; break;
            case 171 : t[i] = 159; break;
            case 190 : t[i] = 191; break;
            default  : break;
        }
}

int main()
{
    string s;
    unsigned int i;

    setlocale(LC_ALL,"");

    cout << "Wpisz tekst poniżej:" << endl << endl;
    getline(cin ,s); PL(s); // Odczytujemy tekst
    cout << endl;

    for(i = 0; i < s.length(); i++)
    {
        if((s[i] >= 'a') && (s[i] <= 'z'))
            s[i] -= 32;
        else
            switch(s[i]) // Polskie litery
            {
                case 'ą': s[i] = 'Ą'; break;
                case 'ć': s[i] = 'Ć'; break;
                case 'ę': s[i] = 'Ę'; break;
                case 'ł': s[i] = 'Ł'; break;
                case 'ń': s[i] = 'Ń'; break;
                case 'ó': s[i] = 'Ó'; break;
                case 'ś': s[i] = 'Ś'; break;
                case 'ź': s[i] = 'Ź'; break;
                case 'ż': s[i] = 'Ż'; break;
            }
    }
    cout << s << endl << endl;

    return 0;
}

Zadanie:

Zmień program tak, aby wykonywał zamianę dużych znaków na małe.

Napisz program, który zastępuje w tekście wszystkie polskie literki ich odpowiednikami łacińskimi: ą → a, ć → c, ..., Ą → A, Ć → C, ...

do podrozdziału do strony

Tekst jest rodzajem tablicy, której elementami są znaki. Dlatego wyszukiwanie znaków nie różni się od wyszukiwania wartości w tablicy. Stosujemy algorytm wyszukiwania liniowego:

Algorytm wyszukiwania znaku w tekście:

Dane wejściowe:

s: tekst do przeszukania
c: poszukiwany znak
p: pozycja startowa w tekście

Dane wyjściowe:

Wartość pozycji poszukiwanego znaku c lub -1, jeśli znak c nie został znaleziony w tekście s

Lista kroków:
K01: Dopóki s[p] ≠ NUL:
     wykonuj kroki K02...K03
K02:   Jeśli s[p] = c,
       to zakończ z wynikiem p
K03:   p ← p + 1
K04: Zakończ z wynikiem -1

Program zamienia każde wystąpienie podanego znaku we wprowadzonym tekście znakiem #.

Program C++ dla cstring

// Wyszukiwanie znaku
//-------------------

#include <iostream>
#include <cstring>

using namespace std;

void PL(char * t)
{
    while(*t)
    {
        switch((unsigned char)*t)
        {
            case 164 : *t = 165; break;
            case 143 : *t = 198; break;
            case 168 : *t = 202; break;
            case 157 : *t = 163; break;
            case 227 : *t = 209; break;
            case 224 : *t = 211; break;
            case 151 : *t = 140; break;
            case 141 : *t = 143; break;
            case 189 : *t = 175; break;
            case 165 : *t = 185; break;
            case 134 : *t = 230; break;
            case 169 : *t = 234; break;
            case 136 : *t = 179; break;
            case 228 : *t = 241; break;
            case 162 : *t = 243; break;
            case 152 : *t = 156; break;
            case 171 : *t = 159; break;
            case 190 : *t = 191; break;
            default  : break;
        }
        t++;
    }
}
// Funkcja wyszukująca
// s - tablica znaków z tekstem
// c - poszukiwany znak
// p - pozycja startowa
//-----------------------------
int SzukanieZnaku(char * s, char c, int p)
{
    while(s[p])
    {
        if(s[p] == c) return p;
        p ++;
    }
    return -1;
}

int main()
{
    char s[100], c[100];
    int p = 0;

    setlocale(LC_ALL,"");

    cout << "c = ";
    cin.getline(c,100); PL(c);
    cout << "s = ";
    cin.getline(s,100); PL(s);
    cout << endl;

    while((p = SzukanieZnaku(s,c[0],p)) != -1)
        s[p++] = '#';

    cout << "s = " << s << endl << endl;

    return 0;
}

c = ś
s = Kubuś Musuś lubi mioduś

s = Kubu# Musu# lubi miodu#

Program C++ dla string

// Wyszukiwanie znaku
//-------------------

#include <iostream>
#include <string>

using namespace std;

void PL(string & t)
{
    unsigned i,len = t.length();
    for(i = 0; i < len; i++)
        switch((unsigned char) t[i])
        {
            case 164 : t[i] = 165; break;
            case 143 : t[i] = 198; break;
            case 168 : t[i] = 202; break;
            case 157 : t[i] = 163; break;
            case 227 : t[i] = 209; break;
            case 224 : t[i] = 211; break;
            case 151 : t[i] = 140; break;
            case 141 : t[i] = 143; break;
            case 189 : t[i] = 175; break;
            case 165 : t[i] = 185; break;
            case 134 : t[i] = 230; break;
            case 169 : t[i] = 234; break;
            case 136 : t[i] = 179; break;
            case 228 : t[i] = 241; break;
            case 162 : t[i] = 243; break;
            case 152 : t[i] = 156; break;
            case 171 : t[i] = 159; break;
            case 190 : t[i] = 191; break;
            default  : break;
        }
}

// Funkcja wyszukująca
// s - tablica znaków z tekstem
// c - poszukiwany znak
// p - pozycja startowa
//-----------------------------
int SzukanieZnaku(string s, char c, int p)
{
    while(s[p])
    {
        if(s[p] == c) return p;
        p ++;
    }
    return -1;
}

int main()
{
    string s,c;
    int p = 0;

    setlocale(LC_ALL,"");

    cout << "c = ";
    getline(cin,c); PL(c);
    cout << "s = ";
    getline(cin,s); PL(s);
    cout << endl;

    while((p = SzukanieZnaku(s,c[0],p)) != -1)
        s[p++] = '#';

    cout << "s = " << s << endl << endl;

    return 0;
}

Zadanie

Przerób program tak, aby wyliczał liczbę wystąpień w tekście podanego znaku.

do podrozdziału do strony

Wyszukiwanie wzorca polega na znalezieniu w tekście określonego ciągu znaków.

Na przykład:

tekst:   Miś Puchatek uwielbia miodek.
ciąg:    hate
wynik:   Miś Puchatek uwielbia miodek.
pozycja:        ^---

Prosty algorytm działa następująco:

Mamy znaleźć w tekście s o długości n znaków wystąpienie tekstu t o długości m znaków poczynając od pozycji p. Jeśli tekst t ma występować w s, to nie może on zajmować pozycji większej od n - m , ponieważ wtedy brakłoby mu liter. Zatem tekst t może występować tylko na pozycjach mniejszych od n - m + 1. Przeglądamy zatem kolejne znaki tekstu s poczynając o pozycji p do n - m. Przeglądany znak porównujemy z pierwszym znakiem tekstu t. Jeśli trafimy na zgodność, to kolejno porównujemy następne znaki tekstu s z następnymi znakami tekstu t. Jeśli wszystkie znaki są zgodne, to kończymy zwracając p. Jeśli wystąpi niezgodność, to p zwiększamy o 1 i algorytm kontynuujemy. Gdy przeglądnięte zostały wszystkie znaki tekstu s na pozycjach od p do n - m, to algorytm kończymy zwracając -1.

Algorytm #1 wyszukiwania wzorca:

Dane wejściowe:

s: tekst do przeszukania
t: poszukiwany tekst
p: pozycja startowa w tekście s

Dane wyjściowe:

Wartość pozycji wystąpienia tekstu t w tekście s lub -1, jeśli tekst t nie został znaleziony w tekście s

Lista kroków:
K01: n ← długość tekstu s
K02: m ← długość tekstu t
K03: Dla i = p, p+1, ... n-m:
     wykonuj kroki K04...K08
K04:   f ← true
K05:   j ← 0
K06:   Dopóki j < m:
       wykonuj krok K07
K07:     Jeśli s[i+j] ≠ t[j], to
           f ← false
           Zakończ pętlę K06
         Inaczej j ← j + 1
K08:   Jeśli f = true, to
       Zakończ z wynikiem i
K09: Zakończ z wynikiem -1

Program C++ dla cstring

// Wyszukiwanie wzorca #1
//-----------------------

#include <iostream>
#include <cstring>

using namespace std;

void PL(char * t)
{
    while(*t)
    {
        switch((unsigned char)*t)
        {
            case 164 : *t = 165; break;
            case 143 : *t = 198; break;
            case 168 : *t = 202; break;
            case 157 : *t = 163; break;
            case 227 : *t = 209; break;
            case 224 : *t = 211; break;
            case 151 : *t = 140; break;
            case 141 : *t = 143; break;
            case 189 : *t = 175; break;
            case 165 : *t = 185; break;
            case 134 : *t = 230; break;
            case 169 : *t = 234; break;
            case 136 : *t = 179; break;
            case 228 : *t = 241; break;
            case 162 : *t = 243; break;
            case 152 : *t = 156; break;
            case 171 : *t = 159; break;
            case 190 : *t = 191; break;
            default  : break;
        }
        t++;
    }
}

// Funkcja wyszukująca
// s - tablica znaków z tekstem
// c - poszukiwany znak
// p - pozycja startowa
//-----------------------------
int Szukanie(char * s, char * t, int p)
{
    int i,j,n,m;
    bool f;

    n = strlen(s);
    m = strlen(t);

    for(i = p; i <= n - m; i++)
    {
        f = true;
        for(j = 0; j < m; j++)
            if(s[i + j] != t[j])
            {
                f = false;
                break;
            }
        if(f) return i;
    }
    return -1;
}
const int N = 75; // długość tekstu
int main()
{
    char s[N],t[N],w[N];
    unsigned i;
    int p = 0;

    setlocale(LC_ALL,"");

    cout << "s = ";
    cin.getline(s,N); PL(s);
    cout << "t = ";
    cin.getline(t,N); PL(t);

    for(i = 0; i < strlen(s); i++)
        w[i] = ' ';
    w[strlen(s)] = 0; // NUL
    p = 0;
    while((p = Szukanie(s,t,p)) != -1)
    {
        w[p++] = '^';
        for(i = 0; i < strlen(t) - 1; i++)
            w[p + i] = '-';
    }

    cout << endl
         << "    " << s << endl
         << "    " << w << endl << endl;

    return 0;
}

s = Misiek Rysiek i Krokodyl Zdzisiek
t = isiek

    Misiek Rysiek i Krokodyl Zdzisiek
     ^----                      ^----

Program C++ dla string

// Wyszukiwanie wzorca #1
//-----------------------

#include <iostream>
#include <string>

using namespace std;

void PL(string & t)
{
    unsigned i,len = t.length();
    for(i = 0; i < len; i++)
        switch((unsigned char) t[i])
        {
            case 164 : t[i] = 165; break;
            case 143 : t[i] = 198; break;
            case 168 : t[i] = 202; break;
            case 157 : t[i] = 163; break;
            case 227 : t[i] = 209; break;
            case 224 : t[i] = 211; break;
            case 151 : t[i] = 140; break;
            case 141 : t[i] = 143; break;
            case 189 : t[i] = 175; break;
            case 165 : t[i] = 185; break;
            case 134 : t[i] = 230; break;
            case 169 : t[i] = 234; break;
            case 136 : t[i] = 179; break;
            case 228 : t[i] = 241; break;
            case 162 : t[i] = 243; break;
            case 152 : t[i] = 156; break;
            case 171 : t[i] = 159; break;
            case 190 : t[i] = 191; break;
            default  : break;
        }
}

// Funkcja wyszukująca
// s - tablica znaków z tekstem
// c - poszukiwany znak
// p - pozycja startowa
//-----------------------------
int Szukanie(string s, string t, int p)
{
    int i,j,n,m;
    bool f;

    n = s.length();
    m = t.length();

    for(i = p; i <= n - m; i++)
    {
        f = true;
        for(j = 0; j < m; j++)
            if(s[i + j] != t[j])
            {
                f = false;
                break;
            }
        if(f) return i;
    }
    return -1;
}

int main()
{
    string s,t,w;
    unsigned i;
    int p = 0;

    setlocale(LC_ALL,"");

    cout << "s = ";
    getline(cin,s); PL(s);
    cout << "t = ";
    getline(cin,t); PL(t);

    w = "";
    for(i = 0; i < s.length(); i++)
        w = w + " ";

    p = 0;
    while((p = Szukanie(s,t,p)) != -1)
    {
        w[p++] = '^';
        for(i = 0; i < t.length() - 1; i++)
            w[p + i] = '-';
    }


    cout << endl
         << "    " << s << endl
         << "    " << w << endl << endl;

    return 0;
}

Jeśli chcesz poznać lepsze algorytmy wyszukiwania wzorca, to zapoznaj się z następującymi artykułami:

do podrozdziału do strony

Matura - programowanie w C++

Operacje na tekstach, cz.2

Zamiana wielkości liter

Algorytm: zamiana liter małych w duże

Wyszukiwanie znaków

Algorytm wyszukiwania znaku w tekście:

Zadanie

Wyszukiwanie wzorca

Algorytm #1 wyszukiwania wzorca:

Zliczanie wyrazów