Analizando una cadena en C ++

Question

Estoy tratando de hacer un constructor para una clase de gráfico que acepte una cadena como parámetro y lo usa para construir el gráfico.

La cadena tiene el siguiente formato: | lista de vértices | Lista de bordes | p.ej. |1,2,3,4,15|(1->2),(3->2),(4->15)|

La idea es que el constructor tomará los valores de la cadena y luego saber realizar las siguientes acciones (insertar los vértices en la lista de vértices y luego insertando los bordes en la lista de bordes):

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

Hubiera hecho un par de " para " bucles para escanear la cadena, pero no sé qué hacer con los números de dos dígitos (o más). Estoy empezando a imaginar todo tipo seriamente complicado para los bucles y me pregunto si alguien aquí podría compartir conmigo más formas inteligentes de extraer y usar estos datos.

Answer 1

Puede usar un stringstream y usar el operador de extracción de flujo para obtener sus enteros.

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

Dado que esta es la tarea, le insto a explorar las posibilidades y descubrir la completa código para ti mismo.

Answer 2

Parece que te estás abrumando mirando todo el asunto. Romperlo en pedazos ... tareas. Lo que estás tratando de hacer parece ser funcionalidades separadas aquí.

1. Tokenizing
2. Analizando vértices
3. Analizando bordes
4. Ejecución en vértices
5. Ejecución en bordes

Son 5 funciones más o menos.

Desea crear un token en función de la tubería (|), por lo tanto, tome una subcadena basada en la tubería y pase cada lado al analizador apropiado, analice las comas, etc.

No voy a hacerlo por ti, pero espero que pueda hacerte pensar en la dirección correcta. Aprender a programar no se trata tanto de un idioma en particular, sino de cambiar tu forma de pensar.

Answer 3

Nunca lo he usado antes, pero hay un Boost tokenizer clase. Podrías dividirlo fácilmente en componentes para ti sin todo el bucle for.

Answer 4

Sin hacer la tarea por usted, esto le dará una buena ventaja. Te he dado el flujo de trabajo básico para analizar la lista de vértices, deberías poder hacer la lista de borde tú mismo. También le dejo el error comprobando, por ejemplo, en parseVertex (), es posible que desee dar un error cuando encuentre caracteres no válidos.

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 5

Analizar este tipo de cosas es bastante sencillo (aunque tedioso) con técnicas de descenso recursivo. La idea es separar el lenguaje que se analiza en unidades lógicas, luego escribir una función para analizar cada una de esas unidades.

Si figuramos en el ejemplo " | 1,2,3,4,15 | (1- > 2), (3- > 2), (4- > 15) | " que toda la cadena es un "polígono", escribiríamos parsePolygon (), que se vería así:

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

Supongamos que Buffer es una clase que se ejecuta a través de su cadena. Necesitará dos operaciones básicas: echar un vistazo al siguiente personaje sin consumirlo y consumir el siguiente personaje.

parseVertices podría verse así:

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

Desearía manejar los errores mucho mejor, obviamente. Si la transmisión encuentra algún error, debe pasar el código de error a la pila de llamadas o lanzar una excepción.

Dos ejemplos más ... parseVertexList y parseNumber podrían verse así:

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);
}

Todo esto es muy rápido y sucio, pero espero que te dé una idea de cómo funciona la técnica. Puede mezclar su manejo con su análisis como se muestra arriba, donde la función parseVertexList realmente hace las llamadas addVertex por usted.

Creo que este es realmente uno de los métodos más simples de análisis manual. Idealmente, siempre podríamos usar analizadores generados como boost spirit o pyparsing o lex / yacc, pero la vida no siempre es tan buena, especialmente para la tarea.

También supongo que vale la pena señalar que la técnica anterior puede ser demasiado exagerada para algunas situaciones de análisis.

Answer 6

Utilice un stringstream . Tenga en cuenta el ejemplo en esa página para leer en números con un istringstream .

Answer 7

Sin duda utilizaría este problema como pretexto para jugar con boost espíritu ! Escribir una pequeña gramática para este pequeño idioma debería ser muy divertido.