Analyser une chaîne en C ++

Question

J'essaie de créer un constructeur pour une classe de graphes qui accepte une chaîne en tant que paramètre et l'utilise pour construire le graphique.

La chaîne est formatée comme suit: | liste de sommets | liste de bords | par exemple. | 1,2,3,4,15 | (1-> 2), (3-> 2), (4-> 15) |

L’idée est que le constructeur prendra les valeurs de la chaîne puis savoir effectuer les actions suivantes (insertion des sommets dans la liste des sommets) puis en insérant les bords dans la liste des bords):

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

Je viens de faire un couple de "pour" boucles pour scanner la chaîne, mais je ne sais pas que faire à propos des nombres à deux chiffres (ou plus). Je commence à imaginer toutes sortes de sérieusement compliqué pour les boucles et je me demande si quelqu'un ici pourrait partager avec moi des moyens plus intelligents d'extraire et d'utiliser ces données.

Answer 1

Vous pouvez utiliser un stringstream et utiliser l'opérateur d'extraction de flux pour obtenir vos entiers.

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

Comme c’est un devoir, je vous exhorte à explorer les possibilités et à comprendre la complète code pour vous-même.

Answer 2

Vous semblez être submergé par tout. Le casser en morceaux ... tâches. Ce que vous essayez de faire semble être des fonctionnalités séparées ici.

1. Tokenizing
2. Analyse des sommets
3. Analyse des bords
4. Exécution sur les sommets
5. Exécution sur les bords

C'est 5 fonctions plus ou moins.

Vous souhaitez créer un jeton basé sur le tube (|), prenez donc une sous-chaîne basée sur le tube et transmettez chaque côté à l'analyseur approprié, analysez les virgules, etc.

.

Je ne vais pas le faire pour vous, mais j'espère pouvoir vous aider à penser dans la bonne direction. Apprendre à programmer ne concerne pas une langue en particulier, mais un changement de mentalité.

Answer 3

Je ne l'ai jamais utilisé auparavant, mais il existe un Boost tokenizer classe. Vous pourriez le diviser facilement en composants pour vous sans tout ce que vous voulez en boucle.

Answer 4

Sans faire vos devoirs à votre place, cela vous donnera une bonne longueur d’avance. Je vous ai donné le flux de travail de base pour analyser la liste des sommets, vous devriez pouvoir faire la liste des arêtes vous-même. Je vous laisse également la vérification des erreurs. Par exemple, dans parseVertex (), vous pouvez indiquer une erreur lorsque vous rencontrez des caractères non valides.

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

L'analyse de ce genre de chose est assez simple (bien que fastidieuse) avec des techniques de descente récursive. L’idée est de séparer le langage analysé en unités logiques, puis d’écrire une fonction pour analyser chacune de ces unités.

Si nous figurons dans l'exemple "1,2,3,4,15 | (1- <2), (3-> 2), (4-> 15) |" que la chaîne entière est un "polygone", nous écririons parsePolygon (), qui ressemblerait à ceci:

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

Supposons que Buffer est une classe qui traverse votre chaîne. Vous aurez besoin de deux opérations de base: examiner le caractère suivant sans le consommer et utiliser le caractère suivant.

parseVertices pourrait ressembler à ceci:

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

Évidemment, vous voudriez mieux gérer les erreurs. Si le flux rencontre une erreur, il doit transmettre le code d'erreur au relais d'appel ou émettre une exception.

Deux autres exemples ... parseVertexList et parseNumber pourraient ressembler à ceci:

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

Tout cela est très rapide et sale, mais espérons que cela vous donne une idée du fonctionnement de la technique. Vous pouvez mélanger votre traitement à votre analyse, comme indiqué ci-dessus, où la fonction parseVertexList effectue les appels addVertex à votre place.

Je pense que c'est vraiment l'une des méthodes les plus simples d'analyse manuelle. Dans l’idéal, nous serions toujours en mesure d’utiliser des analyseurs syntaxiques générés tels que boost spirit, pyparsing ou lex / yacc, mais la vie n’est pas toujours aussi agréable, surtout pour les devoirs.

Je suppose également que cela vaut la peine de noter que la technique ci-dessus peut être très lourde pour certaines situations d'analyse syntaxique.

Answer 6

Utilisez un stringstream . Notez l'exemple sur cette page pour lire des nombres avec un istringstream .

Answer 7

Je voudrais certainement utiliser ce problème comme prétexte pour jouer avec boost esprit ! Écrire un peu de grammaire pour cette langue minuscule devrait être très amusant.