Разбор строки в C ++

Question

Я пытаюсь создать конструктор для класса графа, который принимает строку как параметр и использует его для построения графика.

Строка отформатирована следующим образом: |vertex list|Edges list| например |1,2,3,4,15|(1->2),(3->2),(4->15)|

Идея состоит в том, что конструктор будет принимать значения из строки, а затем знать, чтобы выполнить следующие действия (вставка вершин в список вершин и затем вставляем ребра в список ребер):

addVertex(1)  
addVertex(2)  
addVertex(3)  
addVertex(4)  
addVertex(15)  
addEdge(1,2)  
addEdge(3,2)  
addEdge(4,15)  

Я бы просто сделал пару циклов "for" для сканирования строки, но я не знаю, что делать с двузначными (или более) цифрами. Я начинаю представлять все виды серьезно сложно для петель, и мне интересно, если кто-нибудь здесь мог бы поделиться У меня есть более разумные способы извлечения и использования этих данных.

Answer 1

Вы, кажется, ошеломлены, глядя на все это. Разбейте его на куски ... задачи. То, что вы пытаетесь сделать, кажется, здесь отдельные функции.

1. Tokenizing
2. Разбор вершин
3. Разбор краев
4. Исполнение на вершинах
5. Исполнение по краям

Это более или менее 5 функций.

Вы хотите использовать токены на основе канала (|), поэтому возьмите подстроку на основе канала и передайте каждую сторону соответствующему анализатору, выполните синтаксический анализ запятых и т. Д.

Не собираюсь делать это для вас, но, надеюсь, я смогу заставить вас думать в правильном направлении. Обучение программированию не столько о каком-то конкретном языке, сколько об изменении вашего мышления.

Answer 2

Вы можете использовать stringstream и использовать оператор извлечения потока, чтобы получить целые числа.

string s("12 34");
istringstream ss(s);
int x, y;
ss >> x >> y;

Так как это домашнее задание, я призываю вас изучить возможности и выяснить полный код для себя.

Answer 3

Я никогда не использовал его раньше, но есть класс Boost tokenizer . Вы можете легко разбить его на составляющие без всяких циклов.

Answer 4

Разбор такого рода вещей довольно прост (хотя и утомителен) с техникой рекурсивного спуска. Идея состоит в том, чтобы разделить анализируемый язык на логические единицы, а затем написать функцию для анализа каждой из этих единиц.

Если мы приведем пример "| 1,2,3,4,15 | (1-> 2), (3-> 2), (4-> 15) |" что вся строка является «полигоном», мы бы написали parsePolygon (), который бы выглядел примерно так:

void parsePolygon (Buffer& b)
{
  parseVertices (b);
  parseEdges (b);
}

Давайте предположим, что Buffer - это класс, который проходит через вашу строку. Вам понадобятся две основные операции: взглянуть на следующий символ без его использования и использовать следующий символ.

parseVertices может выглядеть так:

void parseVertices (Buffer& b)
{
  if (b.peek() != '|') { /* error */ }
  b.consume (); // burn the '|'
  parseVertexList (b);
  if (b.peek() != '|') { /* error */ }
  b.consume (); // burn the '|'
}

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

Еще два примера ... parseVertexList и parseNumber могут выглядеть следующим образом:

void parseVertexList (Buffer& b)
{
  addVertex (parseNumber (b));
  while (b.peek() == ',')
  {
     b.consume (); // eat the comma
     addVertex (parseNumber (b));
  }
}

int parseNumber (Buffer& b)
{
  char accum[80] = { '0' };  // sensible default in case of failure
  int accumPos = 0;
  while (isDigit (b.peek())
  {
    accum[accumPos++] = b.consume();
  }
  return atoi(accum);
}

Это все очень быстро и грязно, но, надеюсь, это даст вам представление о том, как работает техника. Вы можете смешивать вашу обработку с вашим анализом, как показано выше, где функция parseVertexList фактически выполняет вызовы addVertex для вас.

Я думаю, что это действительно один из самых простых методов ручного разбора. В идеале мы всегда сможем использовать сгенерированные парсеры, такие как boost spirit или pyparsing или lex / yacc, но жизнь не всегда так хороша, особенно для домашней работы.

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

Answer 5

Без выполнения домашней работы это даст вам хороший старт. Я дал вам основной рабочий процесс для разбора списка вершин, вы должны быть в состоянии сделать список ребер самостоятельно. Я также оставляю вам проверку ошибок, например, в parseVertex () вы можете выдавать ошибку, когда встречаете недопустимые символы.

void skipWhiteSpace(const char*& first , const char* last) {
    // do whatever need to be done to skip white space
}

// parse integer only, no error checking is performed
bool parseVertex(const char*& first , const char* last) {
    skipWhiteSpace(first, last);
    const char* numBegin = first;
    for (; first != last && ::isdigit(static_cast<unsigned char>(*first)); 
        ++first) {}
    if (numBegin != first) {
        std::cout << "addVertex(" << std::string(numBegin, first) << ")" << std::endl;
        return true;
    }

    return false;
}

bool parseComma(const char*& first , const char* last) {
    skipWhiteSpace(first, last);
    if (first != last && ',' == *first) {
        ++first;
        return true;
    }

    return false;
}

// VL := V (, VL)
// a vertex list (VL) is a vertex (V) followed by a comma than another vertex list
bool parseVertexList(const char*& first, const char* last) {
    if (parseVertex(first, last)) {
        parseComma(first, last) && parseVertexList(first, last);
        return true;
    }

    return false;
}
}

void test() {
    const char* str = "1,2,3,4,15";
    parseVertexList(str, str + sizeof("1,2,3,4,15"));
}

Answer 6

Я бы, конечно, использовал эту проблему как предлог для игры с boost spirit ! Написание небольшой грамматики для этого крошечного языка должно быть очень забавным.

Answer 7

Используйте stringstream. Обратите внимание на пример на этой странице для чтения чисел с istringstream.