Using Library Algorithms

Kategori: C++ , 12 Kasım 2019 , JanFranco


Bu yazımda algoritm kütüphanesini inceleyeceğiz. Bu kütüphaneyi kullanabilmek için include ifadesi ile kütüphaneyi alalım:


#include <algorithm>
Bir önceki yazımda split fonksiyonu yazmıştık ve bu fonksiyon ile stringleri boşluklara göre ayırmıştık. i ve j indisleri yerine i ve j iteratorlarını kullanalarak da bu problemi çözebiliriz. İlk olarak bir karakterin boşluk olup olmadığını kontrol eden iki fonksiyon yazalım:


bool space(char c){
    return isspace(c);
}

bool not_space(char c){
    return !isspace(c);
}
Bu fonksiyonları find_if() fonksiyonuna argüman olarak göndereceğiz. find_if() fonksiyonu algoritm kütüphanesinden geliyor. Fonksiyonun üç parametresi mevcut. Fonksiyonun ilk iki argümanına bir dizi ifade eden iki iterator göndereceğiz (start, end). Üçüncü argümanına da boolean bir fonksiyon göndereceğiz. Her adımda bu fonksiyon çağırılacak ve return değeri true ise find_if çalışmayı sonlandıracak:


vector<string> split(const string& s){
    typedef string::const_iterator iter;
    vector<string> ret;

    iter i = s.begin();
    while(i != s.end()){
        i = find_if(i, s.end(), not_space);
        iter j = find_if(i, s.end(), space);

        if(i != s.end()){
            ret.push_back(string(i, j));
        }
        i = j;
    }
    return ret;
}
Burada find_if() fonksiyonları ile kelimeleri aldık. Yani ilk olarak başlangıçtan boşluk olana kadar ilerledik. Boşluk olunca durduk ve durduğumuz yeri j iterine attık. string(i, j) diyerek başlangıçtan j'ye kadar olan kısmı aldık ve vektöre attık. Daha sonra i = j işlemi ile i iterinin j iterinin olduğu yere gelmesini sağladık. Bir sonraki while adımında i iteri, bir karaktere denk gelene kadar devam edecek. Daha sonra j iteri i iterinin kaldığı yerden boşluk bulana kadar ilerleyecek. Bu döngü bu şekilde ilerleyecek. Bir stringi boşluklara göre bölmek dışında, palindrome da yaygın bir problemdir. "civic", "level" gibi tersten okunduğunda da anlamı değişmeyen kelimeler palindromic kelimelerdir. Bir kelimenin palindrome olup olmadığını test eden bir fonksiyon yazalım:


bool is_palindrome(const string& s){
    return equal(s.begin(), s.end(), s.rbegin());
}
Burada algorithm kütüphanesinde bulunan equal() fonksiyonunu kullandık. Fonksiyona gönderdiğimiz ilk iki argüman bir dizi belirten iteratorlardır. Üçüncü argüman ise kontrol edilecek değerdir. Burada argüman olaran s.rbegin() iteratorunu gönderdik. begin() gibi çalışır fakat tersten başlar ve stringin başına doğru gider. İlk karakterden başlayarak, son karakter ile karşılaştırıyoruz. Eğer eşleşme olmazsa false değer return edecek. Bir başka örnek yapalım. http://janfranco.com şeklinde bir string gönderdiğimizde bu stringi :// karakterlerine göre parçalayacak bir fonksiyon yazalım. Bu problem için ilk olarak bir karakterin url karakteri olup olmadığını return eden bir fonksiyonla başlayalım:


bool not_url_char(char c){
    static const string url_ch = "~;/?:@=&$-_.+!*'(),";
    return !(isalnum(c)) || find(url_ch.begin(), url_ch.end(), c) != url_ch.end();
}
Eğer c karakteri url içerisinde bulunabilecek bir karakter değilse true return edilecek. İki iter değişkeni alan bir fonksiyon yazalım. Fonksiyon bir bu şekilde bir dizi almış olacak. find_if() fonksiyonunu kullanarak bu dizide, başlangıçtan url içerisinde olmaması gereken bir karakter bulunan yere kadarki kısmı return edecek:


typedef string::const_iterator iter;

iter url_end(iter b, iter e){
    return find_if(b, e, not_url_char);
}
Her seferinde string::const_iterator yazmamak için typedef ifadesi ile bu yazımı iter olaran kısalttık. Bu arada url içersinde olmaması gereken karakter olarak bahsediyorum fakat onu site adresi içerisinde olmaması gereken karakter olarak güncelleyelim, bu şekilde daha doğru olur. Bir stringte url bulan fonksiyonu yazalım:


vector<string> find_urls(const string& s){
    vector<string> ret;
    iter b = s.begin(), e = s.end();

    while(b != e){
        b = url_beg(b, e);

        if(b != e){
            iter after = url_end(b, e);
            ret.push_back(string(b, after));
        }

        b = after;
    }

    return ret;
}
Bu fonksiyonda bir string alacağız. b iteratoru stringin başını, e iteratoru sonunu gösterecek. İlk olarak url_beg() fonksiyonu ile protokolü (htpp://) alacağız. Eğer b, e iteratorune eşit değilse bulmuşuz demektir. Bulduktan sonra url_end() fonksiyonu ile sitenin adresini alıp, vektöre atacağız. url_end() fonksiyonun zaten tanımlamıştık. Şimdi url_begin() fonksiyonunu tanımlayalım:


iter url_beg(iter b, iter e){
    static const string sep = "://";
    iter i = b;

    while((i = search(i, e, sep.begin(), sep.end())) != e){
        if(i != b && i + sep.size() != e){
            iter beg = i;
            while(beg != b && isalpha(beg[-1]))
                beg--;
            if(beg != i && !not_url_char(i[sep.size()]))
                return beg;
        }
        i += sep.size();
    }

    return e;
}
Burada ilk olarak search() fonksiyonu ile "://" karakterlerini aradık. Eğer karakter bulunamazsa ikinci argüman olan e return edilecek. Bu nedenle döngüyü bu koşul ile kurduk. Eğer iter i başta ve sonda ise sadece iterationu artıracağız. Eğer başta ve sonda değilse iter beg iter i'nin olduğu yerde olacak. Bir döngü daha açıp, iter beg'i başa kaydıracağız. Eğer beg iter i'ye eşit değilse ve i + 3'teki karakter url'de barınabilen bir char ise beg iterini return edeceğiz. Fonksiyonları test edelim:


int main()
{
    string str = "hello http://www.janfranco.com world";
    vector<string> url = find_urls(str);

    for(vector<string>::size_type i = 0; i != url.size(); i++){
        cout << url[i];
    }
    return 0;
}


Sonraki Yazı: Using Associative Containers
Yorumlar

Henüz bir yorum bulunmuyor.