Code-Live.ru

Портал о программировании

Разминка для мозгов: парсер строки

Дана строка вида:
«число1, число2, число3, ..., числоN»

Необходимо написать функцию,
которая возвращает вектор с числами из этой строки.
Числа разделены запятыми, но не более, чем одной.
Разделители (пробелы, табуляция и т.д.),
между числами и разделяющими их запятыми не играют роли.
Если исходная строка имеет ошибки,
то необходимо бросить исключение
std::invalid_argument(message),
где message — описание ошибки и её место в строке.
Если в строке ошибок несколько, то достаточно информации о первой из них.
Числа могут быть как положительные, так и отрицательные.
Положительные числа могут начинаться со знака «+».
Знак числа должен примыкать к числу без пробелов:
«+55» — ok
«- 55» — ошибка
В случае, если число не может вместится в тип int,
необходимо также выбросить исключение std::invalid_argument.
Использовать можно любые средства из стандартных библиотек C и C++.
Продемонстрировать использование функции на различных строках,
вывести для каждой строки получившийся вектор
или сообщение об ошибке в std::cout.

Примеры строк:
«1, 4, 5, -6, 8, 3, 1» — ok
« 5 , 6, 57, +68 , 18, 32, 4 » — ok
«77» — ok
«» — ок
« » — ок
«1, 4, 5, 6, 8, 3, 1,» — ошибка (отсутствует значение там-то там-то)
« , 6, 57, 68 , 18, 32, 4» — ошибка (отсутствует значение там-то там-то)
«5, 6, , 68, 18, 32, 4» — ошибка (отсутствует значение там-то там-то)
«5, 6, T, 68, 18, 32, 4» — ошибка (аргумент не является числом там-то там-то)
«5, 6, 34T, 68, 18, 32, 4» — ошибка (аргумент содержит не только число там-то там-то)
«5, 6, 34 55, 68, 18, 32, 4» — ошибка (аргумент содержит не только число там-то там-то)
«,» — ошибка (отсутствует значение там-то там-то)
«,,» — ошибка (отсутствует значение там-то там-то)

Функция должна иметь прототип

std::vector<int> parse(const std::string&);

Дополнительно: сделать функцию шаблоном,
чтобы работать не только с типом int,
но и с другими целочисленными типами.

В чём подвох? ;)

В качестве параметра функция получает const std::string&, или const char *, или просто char *?

Вообще лучше бы ты точно указал сигнатуру функции — меньше вопросов.

Числа в строке могут быть со знаком? Если да, то знак + допускается?

Что должно происходить, если в строке указано формально корректное число, которое приводит к переполнению?

Вообще лучше бы ты точно указал сигнатуру функции — меньше вопросов.

В принципе, без разницы, но давайте остановимся на std::string.

Числа в строке могут быть со знаком? Если да, то знак + допускается?

Конечно допускаются, как же иначе-то :)
Но только не в отрыве от числа.

Что должно происходить, если в строке указано формально корректное число, которое приводит к переполнению?

Хм... а давайте тоже будем кидать
исключение std::invalid_argument с нужным текстом.

Дополню первый пост.
Спасибо за замечания.

В чём подвох? ;)

Ни в чем, почему здесь должен быть подвох?
Это же не Вам задание, а новичкам.
Думаю, вы минут за 10 такое напишите :)

На счет 10 минут, вы мне, сударь, льстите )) Тут только клавиатуру топтать не меньше 10 минут потребуется. А ещё и подумать надо, и отладить.

Что-то мне сдаётся, что новичкам не по зубам будет. Или просто, как обычно, по кустам отсидятся. Осмысленно в обсуждении примут участие три человека: два — уже понятно, третий — думаю, сам догадаешься ;)

На счет 10 минут, вы мне, сударь, льстите

Недавно мне как раз пришлось выполнить эту задачу.
Ушло где-то полчаса, но это с объяснением новичку
того, как работает всё это дело работает,
думаю, без объяснений ушло бы минут 10-20.
Конечно же, я использовал прелести стандартной библиотеки :)

Или просто, как обычно, по кустам отсидятся.

Если они здесь вообще есть.
Ну пусть сидят, так и не научаться.

Раз никто не хочет предложить решение, то я предложу свой говнокод :)

#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <stdexcept>
#include <cctype>

bool isnumber(const std::string &str)
{
    if (!std::isdigit(str[0]) && !(str[0] == '-' || str[0] == '+'))
        return false;

    if (str.size() == 1 && !(std::isdigit(str[0])))
        return false;

    for (std::size_t i = 1; i < str.size(); i++)
    {
        if (!std::isdigit(str[i]))
            return false;
    }

    return true;
}

int strToInt(const std::string &str)
{
    int val;

    if (!isnumber(str))
        throw std::invalid_argument("Can't convert " + str + " to number");

    try
    {
        val = std::stoi(str);
    }
    catch(std::out_of_range &o)
    {
        throw std::invalid_argument("Too much value for int type");
    }

    return val;
}

int skipSpace(const std::string &str, int index)
{
    while (index < (int)str.size() && std::isspace(str[index]))
        index++;

    return index;
}

std::vector<int> parse(const std::string &str)
{
    std::vector<int> out;

    int pos = 0;

    //Переходим к первому числу
    int index = skipSpace(str, 0);

    //Обработка строки проходит по следующему алгоритму:
    //пропускаем пробельные символы
    //если встретили запятую - пропущено число
    //иначе собираем все символы, отличные от
    //пробельных и запятой в отдельную строку и переводим её в число
    //после пропускам пробельные символы и запятую

    while (index < (int)str.size())
    {
        if (str[index] == ',')
            throw std::invalid_argument("Expected number at position " + std::to_string(pos));

        //Выделяем число и переводим его в строку

        std::string number;

        while (index < (int)str.size() && (str[index] != ',' && !std::isspace(str[index])))
            number += str[index++];

        try { out.push_back(strToInt(number)); }
        catch (std::invalid_argument &e)
        {
            throw std::invalid_argument(e.what() + (std::string)" at position " + std::to_string(pos));
        }


        //Переходим к следующему числу
        index = skipSpace(str, index);

        if (index == (int)str.size())
            break;

        if (str[index] != ',')
            throw std::invalid_argument("Expected comma after position " + std::to_string(pos));

        if (skipSpace(str, index + 1) == (int)str.size())
            throw std::invalid_argument("Expected number at position " + std::to_string(pos + 1));

        index = skipSpace(str, index + 1);

        pos++;
    }

    return out;
}

void test(const std::string &str)
{
    std::cout << "\"" << str << "\" -> ";

    std::vector<int> n;

    try
    {
        n = parse(str);
        std::cout << "| ";
        for (std::size_t i = 0; i < n.size(); i++)
            std::cout << n[i] << " ";
        std::cout << " |" << std::endl;
    }
    catch (std::invalid_argument &e)
    {
        std::cout << e.what() << std::endl;
    }
}

int main()
{
    test("1, 4, 5, -6, 8, 3, 1");
    test(" 5 , 6, 57, +68 , 18, 32, 4   ");
    test("77");
    test("");
    test("    ");
    test("1, 4, 5, 6, 8, 3, 1,");
    test(" ,6, 57, 68 , 18, 32, 4");
    test("5, 6, , 68, 18, 32, 4");
    test("5, 6,, 68, 18, 32, 4");
    test("5, 6, T, 68, 18, 32, 4");
    test("5, 6, 34T, 68, 18, 32, 4");
    test("5, 6, 34 55, 68, 18, 32, 4");
    test(",");
    test(",,");
    test(",, ,, ,,,");
    return 0;
}

А вот и третий.

Осмысленно в обсуждении примут участие три человека: два — уже понятно, третий — думаю, сам догадаешься ;)

А вот и третий.

Я угадал кто это будет )))
Вывод один — ему это тоже интересно,
человек практикуется на простеньких задачках.

Видимо больше ни кто не подключится. Значит будем соображать «на троих» ))

Я тоже накидал решение задачи. Не совсем им доволен, но, к сожалению, времени на доводку сейчас нет. Но как концепт вполне ничего.

Вариация на тему конечных автоматов, если быть более точным, на ДКА.

#include <iostream>
#include <vector>
#include <string>
#include <cstdlib>



std::vector<int> parse(const std::string& a_str) {

    enum State { START = 0, BLANK, COMMA, SIGN, DIGIT, FINISH, ERROR };
    std::vector<int> vec;
    const char *str = a_str.c_str();
    char *ptr = const_cast<char *>(str);
    State state_cur = START;
    State state_next = START;
    bool in_process = true;

    int permit[5][6] = {
        //                START   BLANK   COMMA   SIGN    DIGIT   FINISH
        /* START */     {   0,      -1,     3,      -1,     -1,     -1 },
        /* BLANK */     {   0,      -1,     -1,     -1,     -1,     -1 },
        /* COMMA */     {   0,      -1,     3,      -1,     -1,     3  },
        /* SIGN  */     {   0,       4,     6,      5,      -1,     6  },
        /* DIGIT */     {   0,      -1,     -1,     1,      -1,     -1 }
    };

    int sign_factor = 1;

    bool number_found = false;
    int number = 0;

    static const std::string err_msg[] = {
        /* 0 */     "Parse error",
        /* 1 */     "Illegal symbol",
        /* 2 */     "Number out of range",
        /* 3 */     "Missing number",
        /* 4 */     "Blank symbol inside number",
        /* 5 */     "Multiple signs",
        /* 6 */     "Orphan sign"
    };
    int error_index = -1;

    while (in_process) {

        if (*ptr == ' ' || *ptr == '\t')
            state_next = BLANK;
        else if (*ptr == '+' || *ptr == '-')
            state_next = SIGN;
        else if (*ptr == ',')
            state_next = COMMA;
        else if (*ptr >= '0' && *ptr <= '9')
            state_next = DIGIT;
        else if (*ptr == '\0')
            state_next = FINISH;
        else {
            state_cur = ERROR;
            error_index = 1;
        }

        if (permit[state_cur][state_next] != -1 || state_cur == ERROR) {
            std::string e_msg;
            if (error_index != -1) {
                e_msg = err_msg[error_index];
            }
            else {
                e_msg = err_msg[permit[state_cur][state_next]];
            }
            throw std::invalid_argument("*** " + e_msg + " at pos " + std::to_string(size_t(ptr - str) + 1));
        }

        switch (state_next) {

            case BLANK:
                ++ptr;
                break;

            case COMMA:
                if (number_found) {
                    vec.push_back(number * sign_factor);
                    sign_factor = 1;
                    number_found = false;
                    ++ptr;
                }
                else {
                    error_index = 3;
                    state_next = ERROR;
                }
                break;

            case SIGN:
                if (*ptr == '-')
                    sign_factor = -1;
                ++ptr;
                break;

            case DIGIT:
                if (number_found) {
                    error_index = 4;
                    state_next = ERROR;
                }
                else {
                    number = std::strtol(ptr, &ptr, 10);
                    if (errno != 0) {
                        error_index = 2;
                        state_next = ERROR;
                        _set_errno(0);
                    }
                    else {
                        number_found = true;
                    }
                }
                break;

            case FINISH:
                if (number_found) {
                    vec.push_back(number * sign_factor);
                }
                in_process = false;
                break;
        }
        state_cur = state_next;
    }

    return vec;
}



int main() {

    std::string str;
    std::vector<int> vec;
    while (!std::cin.eof()) {
        std::getline(std::cin, str);
        std::cout << "input  [" << str << "]" << std::endl;

        try {
            vec = parse(str.c_str());
            std::cout << "output ";
            if (vec.empty())
                std::cout << "vector is empty";
            for (auto it = vec.begin(); it != vec.end(); it++) {
                std::cout << "[" << *it << "] ";
            }
            std::cout << std::endl;
        }
        catch (std::invalid_argument &e) {
            std::cout << e.what() << std::endl;
        }

    }

    return 0;
}

Комментариев во коду нет, грешен, поэтому пару слов здесь. Табличка permit содержит значения для состояния. Первый индекс — текущее состояние, второй индекс — следующее состояние. Значение -1 показывает, что следующее состояние возможно. Значение => 0 — это индекс сообщения об ошибке в массиве err_msg. Остальное вроде достаточно прозрачно.

Инетерсное решение.
А я почему то и не думал, что конечные автоматы могут применятся на практике :\

Croessmah, выкатывай свой вариант.

Недавно мне как раз пришлось выполнить эту задачу. [skip] без объяснений ушло бы минут 10-20. Конечно же, я использовал прелести стандартной библиотеки :)

Я STL знаю не очень хорошо, поэтому весьма любопытно.

У меня ещё была мысль использовать регулярные выражения. Если бы я писал на Perl, то скорее всего я бы использовал их. Но для C++ мне кажется, это стрельба из пушки по воробьям. Хотя может я и ошибаюсь.

выкатывай свой вариант.

Чуть позже, сейчас до него не добраться )))

А я почему то и не думал, что конечные автоматы могут применятся на практике :\

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

Чуть позже, сейчас до него не добраться )))

Ну 10-20 минут-то можно выкроить что бы повторить решение ;)

Ну 10-20 минут-то можно выкроить что бы повторить решение ;)

Если те самые 10-20 минут есть в наличии :)
Да и зачем повторять?
Вот, выдрал из проекта (вроде бы всё выдрал),
немного переделал под наши условия (там немного другие были).
Шаблон удалил, ибо только загромождать будет.
Тексты ошибок смешные )))

#include <string>
#include <cctype>
#include <iostream>
#include <stdexcept>
#include <vector>
#include <algorithm>


namespace
{
    void trimLeft(std::string &str)
    {
        auto strIt = std::find_if_not(str.begin(), str.end(), isspace);
        str.erase(str.begin(), strIt);
    }


    void trimRight(std::string &str)
    {
        auto strIt = std::find_if_not(str.rbegin(), str.rend(), isspace);
        str.erase(strIt.base(), str.end());
    }


    void trimString(std::string &str)
    {
        trimRight(str);
        trimLeft(str);
    }

}



std::vector<int> parse_string(const std::string &inputString)
{
    std::vector<int> values;

    if(std::find_if_not(inputString.begin(), inputString.end(), isspace) == inputString.end()){
        return values;
    }

    size_t posBegin = 0;    
    while (posBegin != inputString.size())
    {
        using namespace std::string_literals;
        size_t commaPos = inputString.find(',', posBegin);

        if (commaPos == std::string::npos)
        {
            commaPos = inputString.size();
        }
        std::string valueString = inputString.substr(posBegin, commaPos - posBegin);
        trimString(valueString);

        if (valueString.empty())
        {
            throw std::invalid_argument(
                    "Empty value (" + std::to_string(posBegin) + ", " + std::to_string(commaPos) + ")");
        }

        size_t readEndPos = 0;
        try
        {            
            int value = std::stoi(valueString, &readEndPos);
            values.push_back(value);
        }
        catch (const std::invalid_argument &e)
        {
            throw std::invalid_argument("Value \"" + valueString + "\" not a number");
        }
        catch (const std::out_of_range &e)
        {
            throw std::invalid_argument("Value \"" + valueString + "\" is overflow");
        }
        if (readEndPos != valueString.size())
        {
            throw std::invalid_argument("Value \"" + valueString + "\" not only comprises digits");
        }


        if (commaPos != inputString.size())
        {
            posBegin = commaPos + 1;
            if(posBegin == inputString.size())
            {
                throw std::invalid_argument(
                        "Empty value (" + std::to_string(posBegin) + ", " + std::to_string(inputString.size()) + ")");
            }
        }
        else
        {
            posBegin = commaPos;
        }

    }

    return values;
}




int main()
{
    std::string str;
    while(std::getline(std::cin, str))
    {
        try
        {
            std::cout << " parse_string(\"" << str << "\")\n\t: ";
            auto vec = parse_string(str);
            for(auto e: vec){
                std::cout << e << "; ";
            }
            std::cout << std::endl;
        }
        catch(const std::invalid_argument &e)
        {
            std::cout << "parse_error: " << e.what() << std::endl;
        }
    }
}

http://rextester.com/OSJO74949

Зашел к вам на огонек :)

#include <iostream>
#include <iterator>
#include <vector>
#include <regex>

std::vector<int> parse(const std::string &iStr) {
  std::vector<int> Ret;
  std::vector<std::string> Tmp; 
  std::string Work(iStr);
  Work.erase(0,Work.find_first_not_of(' '));
  Work.erase(Work.find_last_not_of(' ')+1); 
  std::cout << "\"" << iStr << "\": ";    
  try {  
    if (Work.length() == 0) throw std::invalid_argument("Пустая строка");
    if (Work[0] == ',') throw std::invalid_argument("В первой позиции не число");
    if (Work[Work.length()-1] == ',') throw std::invalid_argument("В последней позиции не число");  
    std::regex Rx("\\s*,\\s*");
    std::sregex_token_iterator Begin(Work.begin(), Work.end(), Rx, -1);
    std::sregex_token_iterator End;
    while (Begin != End) Tmp.push_back((Begin++)->str());
    Rx = "^\\s*((\\+|-)?[0-9]+)\\s*,?\\s*$";
    int Pos = 0;  
    for(const auto &i:Tmp) {  
      std::smatch Match;  
      std::regex_search(i, Match, Rx);
      if (Match.size() == 3) 
        Ret.push_back(std::stoi(Match.str(1),nullptr,10)); 
      else 
        throw std::invalid_argument("В позиции "+std::to_string(Pos)+" не число");
      Pos++;                
    }  
    std::cout << "Ok";  
  } catch (std::invalid_argument &E) {
    std::cout << E.what();
  }
  std::cout << std:: endl;
  return Ret;
}

int main() {
  parse("1, 4, 5, -6, -8 , 3, 1");
  parse("       5 , 6, 57, +68 , 18, 32, 4   ");
  parse("77");
  parse("");
  parse("    ");
  parse("1, 4, 5, 6, 8, 3, 1,");
  parse(" , 6, 57, 68 , 18, 32, 4");
  parse("5, 6, , 68, 18, 32, 4");
  parse("5, 6,, 68, 18, 32, 4");
  parse("5, 6, T, 68, 18, 32, 4");
  parse("5, 6, 34T, 68, 18, 32, 4");
  parse("5, 6, 34 55, 68, 18, 32, 4");
  parse(",");
  parse(",,");
  parse(",, ,, ,,,");
  return 0;
}

http://ideone.com/gDLYpb

Majestio, экспресс-анализ показал, что твой код валится на больших числах. std::stoi() в этом случае выбрасывает исключение, которое ты не обрабатываешь.

Ты немного невнимательно прочитал условие задания:

Если исходная строка имеет ошибки, то необходимо бросить исключение std::invalid_argument(message),

т.е. имелось ввиду, что исключение выбрасывается внутри функции, а ловится в вызывающем коде.

К сожалению не могу сейчас покопаться в коде — инструментов нет под рукой.

Согласен. Исправил. Но не суть — просто хотел показать, что парсить текст не просто удобно, а естественно, используя регулярки.

#include <iostream>
#include <iterator>
#include <vector>
#include <regex>

std::vector<int> parse(const std::string &iStr) {
  std::vector<int> Ret;
  std::vector<std::string> Tmp; 
  std::string Work(iStr);
  Work.erase(0,Work.find_first_not_of(' '));
  Work.erase(Work.find_last_not_of(' ')+1); 
  if (Work.length() == 0) throw std::invalid_argument("Пустая строка");
  if (Work[0] == ',') throw std::invalid_argument("В первой позиции не число");
  if (Work[Work.length()-1] == ',') throw std::invalid_argument("В последней позиции не число");  
  std::regex Rx("\\s*,\\s*");
  std::sregex_token_iterator Begin(Work.begin(), Work.end(), Rx, -1);
  std::sregex_token_iterator End;
  while (Begin != End) Tmp.push_back((Begin++)->str());
  Rx = "^\\s*((\\+|-)?[0-9]+)\\s*,?\\s*$";
  int Pos = 0;  
  for(const auto &i:Tmp) {  
    std::smatch Match;  
    std::regex_search(i, Match, Rx);
    if (Match.size() == 3) 
      try { 
        Ret.push_back(std::stoi(Match.str(1),nullptr,10)); 
      } catch(...) {
        throw std::invalid_argument("В позиции "+std::to_string(Pos)+" слишком длинное число");
      } 
    else throw std::invalid_argument("В позиции "+std::to_string(Pos)+" не число");
    Pos++;                
  }  
  return Ret;
}

int main() {
  for(const auto &i: {  
    "1, 4, 5, -6, -8 , 3, 1",
    "1, 3333333333333333333333333334, 5, -6, -8 , 3, 1",        
    "       5 , 6, 57, +68 , 18, 32, 4   ",
    "77",
    "",
    "    ",
    "1, 4, 5, 6, 8, 3, 1,",
    " , 6, 57, 68 , 18, 32, 4",
    "5, 6, , 68, 18, 32, 4",
    "5, 6,, 68, 18, 32, 4",
    "5, 6, T, 68, 18, 32, 4",
    "5, 6, 34T, 68, 18, 32, 4",
    "5, 6, 34 55, 68, 18, 32, 4",
    ",",
    ",,",
    ",, ,, ,,,"}) { 
    try {
      std::cout << "\"" << i << "\": ";
      parse(i);
      std::cout << "Ok";
    } catch (std::invalid_argument &E) {
      std::cout << E.what();
    }  
    std::cout << std::endl;
  }  
  return 0;
}

http://ideone.com/n14j5U

Зашел к вам на огонек

Четвертый! Всё, бригада )))

Осмысленно в обсуждении примут участие три человека

маэстро ошибся )))

Внимание! Это довольно старый топик, посты в него не попадут в новые, и их никто не увидит. Пишите пост, если хотите просто дополнить топик, а чтобы задать новый вопрос — начните новый.

Ответить

Вы можете использовать разметку markdown для оформления комментариев и постов. Используйте функцию предпросмотра для проверки корректности разметки.

Пожалуйста, оформляйте исходный код в соответствии с правилами разметки. Для того, чтобы вставить код в комментарий, скопируйте его в текстовое поле ниже, после чего выделите то, что скопировали и нажмите кнопку «код» в панели инструментов. Иначе ваш код может принять нечитаемый вид.

Либо производите оформление кода вручную, следующим образом:

``` #include <iostream> using namespace std; int main() { // ... } ```

Предпросмотр сообщения

Ваше сообщение пусто.