Токенизация строки для разных разделителей

#cpp #строки

Как лучше всего разделить строку std::string на токены по заданным разделителям?
Например для разделителей {" ", ",", ", "} и строки "один два,три, четыре" функция
должна выдавать std::vector вида {"один","два","три","четыре"}.

Обновление: мне казалось, что это видно из примера - разделитель может быть произвольной
длины. То есть если разделитель ", ", то разделять надо именно им, а не отдельно ","
и/или " ".

Обновление 2: благодаря комментарию AnT понял, что условие всё таки не до конца определено.
Если в строке встречается несколько разделителей подряд, причём один из разделителей
является подстрокой другого, то деление должно происходить по большему из разделителей.
Например, "один,  два"(два пробела) должно разделить на "один" и " два"(один пробел),
а не на какую-либо другую пару.
    

Ответы

Ответ 1

Для нетривиального набора разделителей (взаимно включают друг друга) лучшим решением
будет использование сторонней библиотеки (например, Boost.Tokenizer). Однако попробуем
решить вашу задачу с использованием стандартной библиотеки.



Проблема заключается в том, что вы используете кириллические символы, а значит для
портабельной обработки текста опять таки требуются сторонние библиотеки. При допущении,
что в качестве разделителей будут использованы только ASCII символы (как у вас в примере),
можно попробовать находить разделители по шаблону с помощью регулярных выражений. В
таком случае кодировка остальных символов нас не волнует. 

Напишем функцию, которая будет выполнить разделение строки на токены с помощью передаваемого
ей регулярного выражения:

#include 
#include 
#include 


std::vector regex_split(const std::string& str, const std::regex& reg) {
    const std::sregex_token_iterator beg{str.cbegin(), str.cend(), reg, -1};
    const std::sregex_token_iterator end{};

    return {beg, end};
}


Здесь -1 как раз и означает итерацию по non-matched фрагментам. То есть передаваемое
регулярное выражение должно искать именно разделители, не затрагивая кириллический текст.

Для тестирования будем использовать следующий код:

#include 
#include 
#include 
#include 


std::vector regex_split(const std::string& str, const std::regex& reg) {
    const std::sregex_token_iterator beg{str.cbegin(), str.cend(), reg, -1};
    const std::sregex_token_iterator end{};

    return {beg, end};
}  


int main() {
    constexpr auto regex_str = R"()"; // сюда будем вставлять текст регулярного выражения
    const std::string str{"один два,три, четыре,  пять  ,шесть ,семь, ,восемь,  
девять"}; // строка для тестов

    const std::regex reg{regex_str};
    const auto tokens = regex_split(str, reg);

    for (auto&& token : tokens) {
        std::cout << token << '\n';
    }
}


В большинстве случаев будет достаточно следующего регулярного выражения (далее текст
регулярного выражения нужно вставлять в R(...) без кавычек):

" *, *| +"

То есть запятая, окружённая произвольным количеством пробелов (0+), ИЛИ 1+ пробел
без запятых.

На тестовом примере получим:

один
два
три
четыре
пять
шесть
семь

восемь
девять


Что в большинстве случаев и ожидается.

Если же мы считаем отсутствие строки неприемлимым (как между "семь" и "восемь"),
то можно убрать "-1" и просто находить всё, что не является разделителем:

"[^, ]+"

Однако судя по комментариям и правкам к вопросу, вам нужно нечто более сложное. Попробуем
для начала такое выражение (далее оставляем "-1"):

", | |,"

То есть запятая и пробел ИЛИ пробел ИЛИ запятая. Возможно, это именно то, что вам
надо. Результаты для тестовой строки:

один
два
три
четыре

пять


шесть

семь

восемь


девять


Как видно, проблема в том, что это не соотносится с вашим примером из "обновления
2". Между "четыре" и "пять" находится лишний пробел и он должен примыкать к пять, а
на данный момент, хоть мы и находим больший разделитель ", ", но также находим и пробел
после него как разделитель "пять" и пробела. Нужно как-то указать в регулярном выражении,
что в случае пробела после разделителя ", " этот пробел не считается разделителем,
а является частью следующего слова.

Сделать это можно с помощью т.н. negative look-behind, проверив, что символ перед
пробелом не является пробелом, при этом не захватывая этот символ. Если же символ всё
же являлся пробелом (как между "четыре" и "пять" в тестовой строке) и захват не произошёл,
то будет осуществлён greedy match, т.е. будет выбран разделитель ", ", что нам и нужно.
Таким образом, регулярное выражение будет иметь вид:

", |(?! ) |,"

То есть запятая и пробел ИЛИ пробел, перед которым нет пробела ИЛИ запятая. Думаю,
это именно то, что вам нужно (по крайней мере все условия соблюдаются), однако есть
небольшая проблема: look-behind не поддерживается стандартной грамматикой ECMAScript
:). А судя по этому ответу остальные существующие в С++ грамматики также его не поддерживают.
Но не беда, ведь look-ahead поддерживаются!

Нетрудно видеть, что если мы перевернём строку и в регулярном выражении заменим ",
" на " ,", а также negative look-behind на negative look-ahead, то получим такое же
поведение:

constexpr auto regex_str = R"( ,| (?! )|,)";
const std::string str{"один два,три, четыре,  пять  ,шесть ,семь, ,восемь,   девять"};

const std::regex reg{regex_str};
const std::string reversed{str.crbegin(), str.crend()};
const auto reversed_tokens = regex_split(reversed, reg);

for (auto it = reversed_tokens.crbegin(); it != reversed_tokens.crend(); ++it) {
    auto&& reversed_token = *it;
    std::cout << std::string{reversed_token.crbegin(), reversed_token.crend()} << '\n';
}


Результаты для тестовой строки:

один
два
три
четыре
 пять

шесть

семь

восемь
  девять


Теперь перед "пять" появился пробел, между " пять" и "шесть" один пробел вместо двух.
Аналогичная "склейка" и для "девять".

Окончательный код:

#include 

#include 
#include 
#include 


std::vector regex_split(const std::string& str, const std::regex& reg) {
    const std::sregex_token_iterator beg{str.cbegin(), str.cend(), reg, -1};
    const std::sregex_token_iterator end{};

    return {beg, end};
}


int main() {
    constexpr auto regex_str = R"( ,| (?! )|,)";
    const std::string str{"один два,три, четыре,  пять  ,шесть ,семь, ,восемь,  
девять"};

    const std::regex reg{regex_str};
    const std::string reversed{str.crbegin(), str.crend()};
    const auto reversed_tokens = regex_split(reversed, reg);

    for (auto it = reversed_tokens.crbegin(); it != reversed_tokens.crend(); ++it) {
        auto&& reversed_token = *it;
        std::cout << std::string{reversed_token.crbegin(), reversed_token.crend()}
<< '\n';
    }
}




Если я не всё учёл, пишите в комментарии. Если не надо моделировать поведение look-behind,
то скорее всего проблема решается изменением регулярного выражения.


Ответ 2

Для решения такой задачи пригодился бы алгоритм одновременного поиска нескольких
подстрок в строке, вроде алгоритма Ахо-Корасик. 

Если же решать подручными средствами "на коленке", то можно предложить такой вариант.
Пусть у нас есть N разделителей


Отсортировать массив разделителей по убыванию длины
Начиная с текущей позиции C в строке (изначально C = 0), выполнить поиск первой подстроки
для каждого разделителя и сформировать массив размера найденных позиций (массив размера N)
Среди N полученных позиций найти минимальную позицию M. Если разделителей с такой
позицией несколько, то берем самый первый (т.е. самый длинный, согласно упорядочению
с шага 1).
Подстрока от С до M уходит на выход
Перемещаем текущую позицию C в позицию M плюс длина использованного разделителя
Обновляем содержимое массива, полученного на шаге 2: те позиции, которые оказались
меньше C обновляем путем поиска соответствующей подстроки с позиции C
Переходим на шаг 3


Например

#include 
#include 
#include 
#include 
#include 

std::vector split(const std::string_view &str, 
                                    std::vector delimiters)
{
  std::vector result;    

  std::sort(delimiters.begin(), delimiters.end(), 
    [](const std::string &lhs, const std::string &rhs) 
      { return lhs.length() > rhs.length(); });

  std::vector nexts(delimiters.size());
  for (unsigned i = 0; i < delimiters.size(); ++i)
    nexts[i] = str.find(delimiters[i]);

  std::string::size_type current = 0;

  do
  {
    auto it_next = std::min_element(nexts.begin(), nexts.end());
    if (*it_next == std::string::npos)
      break;

    if (current < *it_next)
      result.emplace_back(&str[current], *it_next - current);

    current = *it_next + delimiters[it_next - nexts.begin()].length(); 

    for (unsigned i = 0; i < delimiters.size(); ++i)
      if (nexts[i] < current)
        nexts[i] = str.find(delimiters[i], current);

  } while (true);

  if (current < str.length())
    result.emplace_back(&str[current], str.length() - current);

  return result;
}

int main()
{
    auto r = split("abc..def, ghij ief.dkj ,ddd.", { ",", ", ", ".", ".." });
    for (auto &s : r)
      std::cout << "'" << s << "'" << std::endl; 
}


Эта реализация пропускает пустые строки, если разделители идут подряд.


Ответ 3

std::string s, delim(" ,-");
std::vector vs;
while (getline(std::cin, s))
    vs.emplace_back(s.substr(0, s.find_first_of(delim)));


После обновления вопроса:
Я напишу на простом примере, а вы по этой логике работайте над любой строкой с любым
разделителем:

std::string s("one,-         two"), del(",-");
std::vector vs;
int k = del.size(),
        pos = s.find(del); // находим позицию разделителья
vs.emplace_back(s.substr(0, pos));  // строка от начала до разделителья
vs.emplace_back(s.substr(pos + k)); // строка от конца разделителья