8

Eu recebi este simples (eu realmente pensava que fosse!) desafio de criar um "tokenizer". Eu tinha que dividir a string " O rato roeu a roupa do rei de roma " em espaços. Então, depois de muito tempo, eu desenvolvi o seguinte algorítimo usando vetores, o header algorithm e strings.

#ifndef STR_PARSE_HPP
#define STR_PARSE_HPP
#include <algorithm>
#include <string>
#include <vector>
using std::reverse;
using std::vector;
using std::string;
    vector<string> split(string str, char delimiter = ' ')
    {
        vector<string> ret;
        if((str.find(delimiter) == string::npos) && (str.find_first_not_of(delimiter) == string::npos)) throw nullptr;
        else if ((str.find(delimiter) == string::npos)) ret.push_back(str);
        else if(str.find_first_not_of(delimiter) == string::npos) ret.push_back(string(""));
        else
        {
            unsigned i = 0;
            string strstack;
            while(str[0] == delimiter) {str.erase(0,1);}
            reverse(str.begin(), str.end());
            while(str[0] == delimiter) {str.erase(0,1);}
            reverse(str.begin(), str.end());
            while(!str.empty())
            {
                ret.push_back(str.substr(i, str.find(delimiter)));
                str.erase(0,str.find(delimiter));
                while(str[0] == delimiter) {str.erase(0,1);}
            }
        }
        return ret;
    }
#endif // STR_PARSE_HPP

O teste:

#include <iostream>
#include "str_parse.hpp"
using std::string;
using std::cout;


int main()
{
    string a = "        O    rato roeu a roupa do rei de roma             ";
    for(int i = 0; i < split(a).size(); i++)
    cout << split(a)[i];
}

O output foi o esperado:

O
rato
roeu
a
roupa
do
rei
de
roma

Então, como perdi um "bocado" de tempo, resolvi testar com outros delimitadores. O crash é instantâneo, e o debbuger aqui está "estragado" (os breakpoints passam reto). O que está errado no meu código?

3
  • Talvez a função strtok atenda a suas necessidades: cplusplus.com/reference/cstring/strtok
    – user4552
    Commented 3/03/2014 às 22:56
  • Olha normalmente o resultado esperado seria que os "itens" vazios fossem retornados, nas implementações que conheço é o mais comum. Não que isso seja um erro, estou fazendo somente uma observação.
    – HwapX
    Commented 3/03/2014 às 23:19
  • @HwapX serio? Obrigado!
    – user2692
    Commented 4/03/2014 às 12:30

4 Respostas 4

7

É interessante notar que muitas vezes a stdlib já possui algoritmos bastante semelhantes que podem ser usados para os seus propósitos. Se o delimitador for sempre o espaço, você pode se basear na leitura de strings a partir de streams. Faça assim:

vector<string> split(const string& str) {
    stringstream ss(str);
    vector<string> vec {istream_iterator<string>{ss}, istream_iterator<string>{}};
    return vec;
}

Ou ainda: (como sugeriu @pepper_chico)

vector<string> split(const string& str) {
    stringstream ss(str);
    return {istream_iterator<string>{ss}, istream_iterator<string>{}};
}

Exemplo: coliru.

Para o caso de ter diferentes delimitadores, pode usar uma outra função pronta para isso: a getline. Embora o nome não pareça, ela faz exatamente o que você quer: quebrar uma string. O detalhe é que o delimitador padrão é a quebra de linha, daí o nome. Use assim:

vector<string> split(const string& str, char delim=' ') {
    stringstream ss(str);
    string tok;
    vector<string> vec;
    while (getline(ss, tok, delim)) {
        if (!tok.empty())
            vec.push_back(tok);
    }
    return vec;
}

Exemplo: coliru.

13
  • Guilherme, eu sempre costumei criar meus próprios algoritmos, acabando que eu não seu muito sobre o standard. Você poderia me explicar como funcionam os iterators?
    – user2692
    Commented 4/03/2014 às 12:28
  • 2
    @LucasHenrique Os iterators funcionam como uma sequencia genérica de alguma coisa. Quando usando um istream_iterator, estou criando uma sequencia de leituras de um determinado tipo de uma stream. Sendo a leitura de strings, a quebra ocorre nos espaços e quebras de linhas, assim como ocorreria com cin >> str;. Me usei de um dos construtores do vector que pega um par de iterators, Assim não tenho que fazer eu mesmo o loop. O código acaba ficando bastante limpo. Commented 4/03/2014 às 14:20
  • 2
    @LucasHenrique Já no segundo caso usei a getline que é de certa forma similar ao strtok, mas funcionado com strings. Escrever os algoritmos usando funções do standard lhe dá a melhor combinação de desempenho e clareza. É seguro assumir que essas funções são naturalmente rápidas se usadas da forma certa. É provável que essa minha versão do código seja mais eficiente. Commented 4/03/2014 às 14:23
  • 1
    @LucasHenrique getline lê do primeiro argumento (uma stream), coloca o resultado no segundo argumento (uma string), parando ao encontrar um delimitador (o terceiro argumento). Como esse terceiro é por padrão a quebra de linha, temos que getline(cin,str) lê uma linha inteira da entrada padrão cin e a coloca na string str. Commented 5/03/2014 às 2:37
  • 1
    return { istream_iterator<string>{ss}, istream_iterator<string>{} } também funciona ;-)
    – oblitum
    Commented 5/03/2014 às 21:43
5

Olhando o seu código a primeira coisa que reparei foi que não tem como sua função main ser do jeito que você postou, isso nem ao menos compila, acredito que deva estar faltando algo na sua postagem. Supondo que você fez algo semelhante a isso:

int main()
{
    string a = "        O    rato roeu a roupa do rei de roma             ";
    vector<string> split_vector = split(a);
    for(unsigned int i = 0; i < split_vector.size(); i++) {
    cout << split_vector[i];
    }
}

O problema de sua função split é que no seguinte trecho:

while(!str.empty())
 {
    ret.push_back(str.substr(i, str.find(delimiter)));
    str.erase(0,str.find(delimiter));
     while(str[0] == delimiter) {str.erase(0,1);}
 }

Esse while

while(str[0] == delimiter) {str.erase(0,1);}

Não testa se a string já chegou no fim, por isso o crash ocorre. O correto seria somente executar isso se não for uma string vazia.

while(!(str.empty()) && (str[0] == delimiter)) {str.erase(0,1);}

Na verdade o correto seria fazer o teste sempre que tiver um código semelhante a esse. Refiz sua função com o que acredito ser o correto, removi alguns testes que achei desnecessários:

vector<string> split(string str, char delimiter = ' ')
{
    vector<string> ret;
    if(str.empty()) 
    {
        ret.push_back(string(""));
        return ret;
    }

    unsigned i = 0;
    string strstack;
    while(!(str.empty()) && (str[0] == delimiter)) {str.erase(0,1);}
    reverse(str.begin(), str.end());
    while(!(str.empty()) && (str[0] == delimiter)) {str.erase(0,1);}
    reverse(str.begin(), str.end());
    while(!str.empty())
    {
        ret.push_back(str.substr(i, str.find(delimiter)));
        str.erase(0,str.find(delimiter));
        while(!(str.empty()) && (str[0] == delimiter)) {str.erase(0,1);}
    }

    return ret;
}
5
  • Eu nao entendo! Se fosse assim, o while principal (!str.empty) deveria sair antes do bug da string ocorrer. Por que?
    – user2692
    Commented 3/03/2014 às 23:58
  • Porque quando chegar na última palavra, no seu exemplo "roma", a linha (str.erase(0,str.find(delimiter));) vai fazer com que a string fique vazia e o código (while(str[0] == delimiter) {str.erase(0,1);}) vai rodar antes do while principal.
    – Selma
    Commented 4/03/2014 às 0:15
  • Haha, agora entendi. Obrigado @Selma!
    – user2692
    Commented 4/03/2014 às 12:32
  • Selma, sua resposta está errada. O while, do erase, vai apagar toda a string (pelo menos deveria), e outros delimitadores também não funcionam.
    – user2692
    Commented 5/03/2014 às 13:21
  • Lucas, ao rodar a função que postei com a string do seu exemplo o primeiro e o segundo while vão remover os espaços do começo e do fim, ficando assim O rato roeu a roupa do rei de roma, dentro do while maior while(!str.empty()) vai chegar um momento em que a iteração vai começar com a string tendo somente a última palavra, nesse caso roma, o push_back vai inserir ela no vetor, o ` str.erase(0,str.find(delimiter));` fazer com que a string fique vazia, e vai entrar um string vazia no quarto while, o que, no código antigo tornava a instrução (str[0] == delimiter) inválida.
    – Selma
    Commented 5/03/2014 às 14:27
2

Olha a @Selma já respondeu qual o problema com seu código, então só vou compartilhar uma implementação alternativa.

#include <string>
#include <vector>

using namespace std;

vector<string> split(string str, char delimiter = ' ')
{
    vector<string> ret;

    int start = 0;

    for(int i = 0; i < str.length(); ++i) {
        if(str[i] == delimiter) {
            ret.push_back(str.substr(start, i-start));
            start = i+1;
        }
    }

    ret.push_back(str.substr(start, start - str.length()));

    return ret;
}

Essa implementação retorna os "itens".

#include <string>
#include <vector>

using namespace std;

vector<string> split(string str, char delimiter = ' ')
{
    vector<string> ret;

    int start = 0;

    for(int i = 0; i < str.length(); ++i) {
        if(str[i] == delimiter) {
            if(i - start != 0)
                ret.push_back(str.substr(start, i-start));
            start = i+1;
        }
    }

    if(str.length() - start != 0)
        ret.push_back(str.substr(start, start - str.length()));

    return ret;
}

Nessa eu adicionei dois if's para ignorar os "itens" vazios.

0

Não queria acordar esta pergunta morta, mas eu refiz o algoritmo, agora que conheço mais sobre iteradores.

#include <iostream>
#include <string>
#include <vector>
std::vector<std::string> tokenize(std::string str, char delimiter = ' ')
{
    std::vector<char> string_ret;
    std::vector<std::string> ret;
    for(auto a : str)
    {
        if(a == delimiter)
        {
            std::cout << "Delimiter found >>" << a << "<<" <<  std::endl;
            if(!string_ret.empty())
            {
                std::cout << "Pushing string to ret!\n";
                std::string push;
                for(auto b : string_ret)
                {
                    push.push_back(b);
                }
                string_ret.clear();
                ret.push_back(push);
            }
            else std::cout << "Delimiter found, but string return is empty!" << std::endl;
        }
        else
        {
            std::cout << "char which is not delimiter found! >>" << a << "<<" << std::endl;
            string_ret.push_back(a);
        }
    }
    if(!string_ret.empty())
    {
        std::string push;
        for(auto b : string_ret)
        {
            push.push_back(b);
        }
        ret.push_back(push);
    }
    std::cout << "\n\n\n\n\n";
    return ret;
}

int main()
{
    for(auto a : tokenize("O rato roeu a roupa do rei de roma", 'r'))
    std::cout << a << std::endl;
}

Você deve fazer log-in para responder a esta pergunta.