Lab 04 - Pliki, wyrażenia regularne

Wyrażenia regularne

Wyrażenia regularne pozwalają tworzyć uogólnione wzorce a następnie znajdować je w tekście (search) lub sprawdzać czy tekst spełnia kryteria wzorca (match). Zadanie to można również zrealizować stosujące pętle i instrukcje warunkowe jednak taki kod będzie skomplikowany i mało ekspresywny.

Podstawowe symbole uogólniające

W wyrażeniu regularnym mogą pojawić się następujące elementy służące go uogólnionej reprezentacji znaku (więcej informacji dotyczących składni można znaleźć tutaj:

🛠🔥Zadanie 🛠🔥

Do sprawdzenia działania przykładów możesz użyć strony regex101.com. Wejdź na podaną stronę i zapoznaj się z jej działaniem, następnie wykonaj przedstawione poniżej zadania 1-3:

1. Kod pocztowy w Polsce jest reprezentowany za pomocą wyrażenia (przetestuj jego działanie podając prawidłowe i nieprawidłowe kody): \d\d-\d\d\d

   W wyrażeniu tym cyfry są oznaczone wzorcem, natomiast kreska jest konkretnym znakiem (elementem nieuogólnionym).

2. Jeśli wyrażenie regularne miałoby weryfikować np. czy numer rejestracyjny pochodzi z Poznania i czy jest to numer rejestracyjny, może mieć postać: PO[A-Z0-9][A-Z0-9][A-Z0-9][A-Z0-9][A-Z0-9]

3. Spróbuj napisać pojedynczy wzorzec, który będzie pasował zarówno do numerów rejestracyjnych rozpoczynających się na PO jak i na PZ.

Kwantyfikatory

Dla powtarzających się elementów wzorca możemy określić reguły dotyczące ich wystąpień:

Uwaga: jeśli w danym wzorcu chcemy wykorzystać któryś z w/w kwantyfikatorów lub symboli uogólniających jako zwykły znak należy go poprzedzić backslashem np.: \. zostanie potraktowana jako znak kropki a nie oznaczenie dowolnego znaku.

🛠🔥Zadanie cd 🛠🔥

4. Stosując kwantyfikatory spróbuj uogólnić zarówno wzorce dla kodu pocztowego jak i numeru rejestracyjnego, wiedząc, że: np. \w+ jest wzorcem dla wyrazu (gdzie znak alfanumeryczny występuje 1 lub więcej razy)
5. Kawantyfikatory mogą być używane zarówno do pojedynczych symboli uogólniających jak i grup np. :(sth)+. Spróbuj napisać wzorzec, który sprawdzi czy dany ciąg jest numerem telefonu. W wersji prostszej wystarczy że wyrażenie będzie w stanie poprawnie rozpoznać cztery pierwsze podane poniżej przykłady. W wersji trudniejszej (dla chętnych) spróbuj uwzględnić żę numer ten może, ale nie musi być podawany z prefiksem kraju lub numer kierunkowy miejscowości może być podany w nawiasie. Wzorzec powinien akceptować następujące formy numeracji:

      12-34-56-789
      12 34 56 789
      12 429 34 30
      123-45-67-89
      0048123456789
      +48123456789
      +48 123-45-67-89
      (032) 6700327

Ciągi w których występuje więcej cyfry lub dodatkowe znaki nie powinny być akceptowane

6. Sprawdź działanie powyższego wyrażenia wklejając wyniki wyszukiwania ze strony google (np. fraza wyszukiwania: "numery telefonów filie") lub skorzystaj z przykładowego pliku html. Plik możesz obejrzeć w przeglądarce, następnie wyświetl i skopiuj jego źródło i wklej je do regex101. Spróbuj zrozumieć dlaczego prócz numerów telefonów jako wyniki dopasowanie pojawiły się również inne elementy i dlaczego część numerów nie została znaleziona. Na tym etapie nie ma konieczności wprowadzania istotnych modyfikacji wzorca (ale możesz wprowadzić kilka zmian zwiększających skuteczność dopasowania), będziesz to robił w ramach zadania domowego.

Uwaga do zadania 6: Pamiętaj, że stworzenie wzorca, który w udostępnionym pliku znajdzie wszystkie numery telefonu, a jednocześnie nie wykryje innych błędnych dopasowań jest trudne do wykonania z uwagi na występowanie w tym pliku dodatkowych informacji w innym kodowaniu, nazw linków i funkcji JavaScript. Poprawne odróżnienie numeru telefonu od innych kombinacji cyfr występujących w kodzie jest możliwe tylko wtedy gdy uwzględnimy kontekst, w którym pojawia się dany ciąg. Stąd np. numery telefonów powinny być szukane tylko w części pliku, w którym pojawiają się wyniki wyszukiwania a nie w obrębie całego kodu strony. Czy jesteś w stanie zidentyfikować w pliku początek i koniec sekcji, w której znajdują się wyniki wyszukiwań. Spróbuj w tym celu w przeglądarce wykorzystać narzędzie inspekcji.

std::regex

Wyrażenia regularne w języku C++ (w STL w pliku nagłówkowym <regex>) są zgodne z składnią ECMAScript (opisaną powyżej), mogą być również wykorzystywane w innych językach programowania i części edytorów tekstu.

Przy używaniu ich w języku C++ należy pamiętać żeby wszystkie wystąpienia znaku \ zastąpić podwójnym backslashem \\ np. \\w lub poprzedź tekst wyrażenia regularnego znakiem R"(text)" np. std::regex re(R"(\d*)") - zwróć uwagę na dodatkowe nawiasy okrągłe, w których należy umieścić całe wyrażenie.

std::regex_match

Funkcja służy do zweryfikowania czy ciąg przekazany jako argument jest w pełni zgodny ze wzorcem. Uruchom i przeanalizuj poniższy kod:

std::regex re(R"(\d+)");;
std::smatch m;
std::string text = "1234";
bool res = std::regex_match(text, m, re); //zwróci wartość true
text = "1234m";
res = std::regex_match(text, m, re); //zwróci wartość false

std::regex_search

Funkcja służy do zweryfikowania czy pewien podciąg jest zgodny ze wzorcem. Uruchom i przeanalizuj poniższy kod:

std::regex re(R"(\d+)");
std::smatch m;
std::string text = "1234";
bool res = std::regex_search(text, m, re); //zwróci wartość true
text = "1234m 78910";
res = std::regex_search(text, m, re); //zwróci wartość true i zwróci do m pierwszy pasujący podciąg czyli 1234

Funkcja znajduje i dopasowuje tylko pierwszy pasujący podciąg. Zmienna wyniku std::smatch m jest kolekcją (podobną do wektora) elementów typu string. Jeśli nie znaleziono dopasowania to;

m.ready() == true
m.empty() == true
m.size() == 0

jeśli znaleziono dopasowanie to:

Żeby znaleźć w tekście więcej (wszystkie) pasujące do wzorca ciągi funkcję std::regex_search można wywoływać cyklicznie, podając jako tekst m.sufix() z ostatnio znalezionego dopasowania. Przeanalizuj poniższy przykład zawierający użycie grup i iterowane przeszukiwanie tekstu:

std::cout << std::endl << "regex_search all" << std::endl;
std::string log(R"(
      Speed: 366
      Mass: 35
      Speed: 378
      Mass: 32
      Speed: 400
      Mass: 30)");
std::regex re(R"(Speed:\s(\d+))");
std::smatch sm;
while (regex_search(log, sm, re)) {
      std::cout << sm[0] << std::endl; //Podciąg dla którego wzorzec jest w pełni dopasowany
      std::cout << "Group 1: " << sm[1] << std::endl << std::endl; //grupa nr 1 (\d*)

      log = sm.suffix(); //przycięcie napisu do przeszukania
}

Uwaga: iterowane przeszukiwanie można również zrealizować przy pomocy iteratora std::regex_iterator sprawdź go w dokumentacji.

🛠🔥Zadanie cd 🛠🔥

7. Spróbuj napisać program, który wykorzystuje wyrażenia regularne stworzone w zadaniu 4 i używając std::regex_match przeparsuj następującą kolekcję numerów rejestracyjnych zwracając te, które pochodzą z poznania (PO) lub powiatu poznańskiego (PZ):

   std::vector<std::string> lines = {"PO12345", "PO 12345", "PZ973ND", "WE20456"};

Pliki

W Lab02 zapoznałeś się z wczytywaniem plików z danymi w formie tabelarycznej. W aktualnym ćwiczeniu przedstawiono dodatkowe informacje przydatne przy realizacji zadań.

Aby uzyskać dostęp do plików bez podawania ścieżki bezwzględnej, należy umieścić otwierane pliki w folderze uruchamiania programu. W przypadku uruchamiania programu z poziomu Qt Creator domyślnym folderem uruchomieniowym jest folder kompilacji znajdujący się obok folderu projektu, o nazwie: build-<project_name>-<kit_name>-<build_type>, np. build-regex-Desktop_Qt_5_13_2_MinGW_64_bit-Debug.

Wczytanie pliku wyraz po wyrazie

std::fstream input_file("filename", std::ios::in);
std::vector<std::string> words;
if (input_file.is_open()) {
      while (!input_file.eof()) {
            std::string word;
            input_file >> word; //wczytuje słowo
            words.emplace_back(word); //dodaje słowo do kolekcji
      }
}

Wczytanie całego pliku do pamięci

Poniższy kod wczytuje całą zawartość pliku tekstowego do zmiennej std::string full_text. Przeanalizuj kod i wykorzystaj gdy będzie to potrzebne:

std::fstream input_file("filename", std::ios::in);
if(input_file.is_open()){
      std::stringstream str_stream;
      str_stream << input_file.rdbuf(); //przepisuje zawartość pliku do strumienia
      std::string full_text = str_stream.str(); //zapisuje całą zawartość strumienia do std::string
}

Uwaga: kod wymaga dodatkowych plików nagłówkowych <fstream>, <sstream>

Zapisywanie danych do pliku

Zapis danych do pliku tekstowego jest analogiczny do wyświetlania danych na konsoli, z tą różnicą że dane zapisywane są do innego strumienia. Poniższy kod zapisuje kolejne wartości funkcji sinus oraz wartość argumentu:

std::fstream output("filename", std::ios::out);
if (output.is_open()) {
      for (double x = 0; x < 10; x += 0.1) {
            output << x << ";" << sin(x) << std::endl;
      }
      output.close();
}

Uwaga: Pamiętaj że po zakończeniu zapisu należy plik zamknąć, w innym przypadku część danych może się nie zapisać.

🛠🔥Zadanie cd 🛠🔥

8. Wczytaj plik z wynikami wyszukiwania numerów telefonów z Google i używając std::regex_search lub std::regex_iterator wyświetl wszystkie numery pasujące do stworzonego wcześniej wzorca.

std::pair/std::tuple

W przypadku operacji na plikach często przechowuje się pary informacji np. nazwisko i ocenę studenta, symbol i kurs waluty. Te informacje mogą być reprezentowane jako struktura, ale dla prostych elementów (par elementów) nie zawsze ma sens definiowanie nowego typu strukturalnego (z nazwanymi polami). Możliwe jest wtedy wykorzystanie kontenera STL typu std::pair, który jest wzorcem struktury o dwóch polach: first i second.

Np. definicja pary przechowującej kurs waluty może mieć postać:

//para z wartościami domyślnymi "" i 0:
std::pair<std::string, double> exchange_rate_empty;

//zmiana wartości pary:
exchange_rate_empty = {"EUR", 4.5}; // lub std::make_pair<string,double>("EUR",4.5);

//definicja para z zainicjowaną dwoma wartościami:
std::pair<std::string, double> exchange_rate_usd("usd",4.10);

Odwołanie się do pól pary może mieć postać:

//odwołanie się do pól first i second
std::cout << "currency: " << exchange_rate_usd.first << " - rate: " << exchange_rate_usd.second;

//lub z użyciem structured binding od C++17
auto[currency, rate] = exchange_rate_usd;
std::cout << "currency: " << currency << " - rate: " << rate;

Użycie auto[currency, rate] = exchange_rate_usd; w domyślnie skonfigurowanym środowisku spowoduje pojawienie się Warning w czasie kompilacji. Aby korzystać z standardu C++17 należy wyedytować plik .pro projektu i zamienić:

CONFIG += console c++11

na:

CONFIG += console c++17

Następnie klikamy prawym klawiszem na nazwę projektu i wybieramy Run qmake.

Krotka (std::tuple), jest wzorcem podobnym do pary, ale może się składać się z większej niż 2 liczby pól. Krotka/para może być wykorzystana np. do zwracania przez funkcję więcej niż jednej wartości:

std::tuple<char, int, bool> mytuple() {
    char a = 'a';
    int i = 123;
    bool b = true;
    return {a, i, b};// lub std::make_tuple(a, i, b);
}

Wywołanie funkcji z wykorzystaniem structured binding może mieć postać:

auto [a, i, b] = mytuple();

std::map

Mapa jest tablicą asocjacyjną przechowującą dane jako parę klucza i wartości zorganizowaną w formie drzewa binarnego (BST) (ang. binary search tree)). Oznacza to, że kontener jest posortowanym (wg klucza) zbiorem danych, w którym może istnieć wyłącznie jedna wartość przypisana do danego klucza.

Elementem kontenera jest para taka że: std::pair<typ_klucza,typ_wartości> a definicja kontenera ma postać:

Definiowanie mapy

std::map<key_type,value_type> container_name;

np.

std::map<std::string, int> word_statistics;

Dodawanie elementu do mapy/Odwoływanie się do elementu

Element dodawany do mapy musi być umieszczony w ściśle określonym miejscu wynikającym z organizacji BST. Stąd kontener ten nie posiada metody emplace_back, tylko metodę emplace i metodę try_emplace.

word_statistics.emplace("the",1); //dodaje słowo "the" i przyporządkowaną mu wartość: 1 odpowiada to dodaniu pary: make_pair<std:string, int>("the",1)

Element może również zostać dodany do mapy przez odwołanie się do klucza z wykorzystaniem operatora indeksowania:

word_statistics["the"] = 1; //dodaje słowo "the" i przyporządkowaną mu wartość: 1// jeśli element istnieje wartość zostanie nadpisana

Ten sam sposób może być użyty do odczytu wartości przypisanej do danego klucza:

std::cout << word_statistics["the"]; //zostanie wartość 1
std::cout << word_statistics["computer"]; //element nie istnieje, zostanie utworzony i przypisana zostanie wartość domyślna dla int ->0

Odwołanie się do elementu tablicy asocjacyjnej po kluczu pozwala na odczyt wartości, jednak w przypadku gdy taki klucz nie istnieje, do mapy zostanie dodany nowy element i zainicjowany wartością domyślną, a następnie wartość ta zostanie zwrócona. Czasem jest to niepożądane stąd żeby temu zapobiec, należałoby sprawdzić czy element istnieje używając np. metody find lub contains (C++20). Można również użyć metody at, która w przypadku nie znalezienia elementu generuje wyjątek std::out_of_range.

std::string word2find = "elephant";
try{
      int val = word_statistics.at(word2find);
}
catch(std::out_of_range e){
      std::cout << "Exception: " << e.what() << std::endl;
}

jeśli nie chcesz używać wyjątków do odnalezienia elementu w mapie możesz wykorzystać std::map::find:

std::string word2find = "elephant";
auto search = word_statistics.find(word2find); //zwraca iterator
if(search != word_statistics.end()) {
      int val = search->second; //znaleziona wartość 
}
else {
      std::cout << "Element nie został znaleziony" << std::endl;
}

Iterowanie po mapie

Mapa jest kontenerem STL, stąd iterowanie po kontenerze odbywa się, tak jak w przypadku wektorów i list, przy pomocy iteratorów lub range-based for loop. Pierwszy element w kontenerze (*word_statistics.begin()) jest najmniejszy (w porządku klucza) a ostatni element jest największy. Należy pamiętać, że elementem kontenera jest para.

for(auto it = word_statistics.begin(); it != word_statistics.end(); it++){ //gdzie it jest iteratorem typu: std::map<std::string,int>::iterator
      std::cout<< it->first << " - " << it->second<< std::endl; // wyświetla klucz i wartość poszczególnych elementów listy
}

//lub z wykorzystaniem structure binding i for range loop
for(auto [word, frequency] : word_statistics){ // rzutowanie klucza i wartości elementu na zmienną word (klucz) i frequency (wartość)
      std::cout<< word << " - " << frequency << std::endl;
}

Zadanie końcowe 🛠🔥

1. Wczytaj plik zawierający licencję GNU, w std::map umieść wyrazy wraz z częstością ich występowania:
   • Wczytuj wyraz po wyrazie i dodawaj element do mapy inkrementując wartość o 1 (będzie ona stanowiła licznik liczby wystąpień danego wyrazu).
   • Po zakończeniu wczytywania wyświetl statystykę wyrazów z liczbą ich wystąpień.
   • Używając algorytmu std::copy przekopiuj dane z mapy do std::vector<std::pair<std::string,int>> i posortuj słowa po częstości wystąpień. PODPOWIEDŹ: Przed skorzystaniem z std::copy zobacz jak wygląda przykład (Example) na stronie referencyjnej https://en.cppreference.com/w/cpp/algorithm/copy.
   • Zapisz wynik do pliku.
   • Zmodyfikuj program tak, aby używając wyrażeń regularnych wybrać z wczytywanego tekstu tylko słowa, usuwając znaki, które nie są literami (np. znaki interpunkcyjne).
   • Używając algorytmu std::transform i predykatu std::tolower przed dodaniem słowa do mapy zmień wielkość liter tak by w mapie umieszczone były unikalne słowa pisane małymi literami.

Zadanie domowe 🏠🔥

Zadanie 1

Wczytaj pliki zawierające wyniki wyszukiwania stron internetowych, m.in. plik dla którego poprzednio wyodrębniałeś telefony (lista plików zawierająca wyniki wyszukiwań w Google: plik1, plik2 , plik3, plik4. Zauważ, że telefon wizualnie skojarzony jest z hyperlinkiem (umieszczonym w nagłówku wyniku wyszukiwania) prowadzącym na stronę, na której został opublikowany. np. https://www.biblioteka.wroc.pl/filie/filia-nr-7. Łatwiej to zauważyć gdy np. w Google Chrome, na podglądzie strony, wybierzesz funkcję inspect preview, wtedy możesz zobaczyć zagnieżdżoną strukturę dokumentu html.

• Stwórz wyrażenie regularne, które wyodrębnia wyniki poszczególnych znalezionych w wyszukiwarce pozycji i wyodrębni z niego hyperlink z adresem znalezionej strony
• Zastosuj wyrażenie regularne z zadania wprowadzającego nr 5 i 6, które w obrębie znalezionej pozycji wyszukiwania wyodrębni wszystkie ciągi pasujące do wzorca numeru telefonu. Wersja trudniejsza: zmodyfikuj tak wyrażenie regularne żeby znaleźć jak najwięcej numerów telefonów pojawiających się w wynikach wyszukiwania.
• znalezione dane zapisuj do mapy std::map<std::string, std::vector<std::string>>, której kluczem jest hyperłącze, a wartościami wektor zawierający numery telefonów skojarzone z danym łączem. Otwórz 1-2 stron w przeglądarce i zweryfikuj skuteczność z jaką udało Ci się wyodrębnić numery telefonów i hyperliniki odnoszące się do wyników wyszukiwania. W wersji podstawowej możesz założyć, żę jeśli znajdziesz większość (>50%) numerów pasujących do założonego wzorca, to wymagania zadania zostały spełnione.
• dokonaj transformacji numerów telefonów do znormalizowanej postaci usuwając z nich spacje i myślniki oraz nawiasy
• stwórz funkcję std::string href_trimmed = href_trim(href_full), która z hyperlinku wyodrębni wyłącznie nazwę domeny np. dla https://www.biblioteka.wroc.pl/filie/filia-nr-7 będzie to biblioteka.wroc.pl. Użyj tej wartości jako klucza mapy (wtedy telefony różnych filii zostaną pogrupowane w obrębie jednego klucza)
• używając algorytmu std::unique_copy lub kontenera std::set spraw, żeby dla danego wpisu numery telefonów się nie powtarzały (może się zdarzyć, że dany numer pojawia się na kilku stronach należących do tej samej domeny)
• zapisz dane do pliku CSV, w którym w pierwszej kolumnie znajduje się nazwa domeny, a w kolejnych znalezione numery telefonów (może się zdarzyć, że w każdym wierszu będzie inna liczba kolumn)

Autorzy: Piotr Kaczmarek