Analisi di una stringa in C ++

Question

Sto cercando di creare un costruttore per una classe di grafici che accetta una stringa come e lo utilizza per creare il grafico.

La stringa è formattata come segue: | elenco vertici | Elenco bordi | per esempio. | 1,2,3,4,15 | (1- > 2), (3 > 2), (4- > 15) |

L'idea è che il costruttore prenderà i valori dalla stringa e quindi sapere di eseguire le seguenti azioni (inserendo i vertici nell'elenco dei vertici e quindi inserendo i bordi nell'elenco dei bordi):

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

Avrei appena fatto un paio di " per " esegue un ciclo per scansionare la stringa, ma non lo so cosa fare con numeri a doppia (o più) cifre. Sto iniziando a immaginare ogni sorta di seriamente complicato per i loop e mi chiedo se qualcuno qui potrebbe condividere con me altri modi più intelligenti per estrarre e utilizzare questi dati.

Answer 1

Puoi usare un stringstream e usare l'operatore di estrazione del flusso per ottenere i tuoi numeri interi.

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

Dato che si tratta di compiti a casa, ti esorto ad esplorare le possibilità e capire il completo codice per te.

Answer 2

Sembri essere sopraffatto dall'intera cosa. Dividilo in pezzi ... compiti. Quello che stai cercando di fare sembra essere funzionalità separate qui.

1. creazione di token
2. Analisi dei vertici
3. Bordi di analisi
4. Esecuzione su vertici
5. Esecuzione sui bordi

Sono 5 le funzioni più o meno.

Desideri tokenizzare in base alla pipe (|), quindi prendi una sottostringa in base alla pipe e passa ogni lato al parser appropriato, analizza le virgole e così via.

Non lo farò per te, ma spero di riuscire a farti pensare nella giusta direzione. Imparare a programmare non dipende tanto da una lingua particolare, ma dal cambiare il modo di pensare.

Answer 3

Non l'ho mai usato prima, ma c'è un Boost tokenizer classe. Potresti averlo facilmente suddiviso in componenti per te senza tutto il for-loop.

Answer 4

Senza fare i compiti per te, questo ti darà un buon vantaggio. Ti ho dato il flusso di lavoro di base per analizzare l'elenco dei vertici, dovresti essere in grado di fare da solo l'elenco dei bordi. Lascio anche il controllo dell'errore a te, ad esempio in parseVertex () potresti voler dare un errore quando incontri caratteri non validi.

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

Analizzare questo tipo di cose è abbastanza semplice (anche se noioso) con tecniche di discesa ricorsive. L'idea è di separare la lingua analizzata in unità logiche, quindi scrivere una funzione per analizzare ciascuna di quelle unità.

Se figuriamo nell'esempio " | 1,2,3,4,15 | (1- > 2), (3- > 2), (4- > 15) | " che l'intera stringa è un "poligono", scriveremo parsePolygon (), che assomiglierebbe a questo:

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

Supponiamo che Buffer sia una classe che attraversa la tua stringa. Avrai bisogno di due operazioni di base: sbirciare il personaggio successivo senza consumarlo e consumare il personaggio successivo.

parseVertices potrebbe assomigliare a questo:

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

Dovresti gestire gli errori molto meglio, ovviamente. Se lo stream rileva errori, è necessario passare il codice di errore nel callstack o generare un'eccezione.

Altri due esempi ... parseVertexList e parseNumber potrebbero apparire così:

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

Questo è tutto molto veloce e sporco, ma speriamo che ti dia un'idea di come funziona la tecnica. Puoi mescolare la tua gestione con l'analisi come mostrato sopra, dove la funzione parseVertexList esegue effettivamente le chiamate addVertex per te.

Penso che questo sia davvero uno dei metodi più semplici di analisi manuale. Idealmente saremmo sempre in grado di usare parser generati come boost spirit o pyparsing o lex / yacc, ma la vita non è sempre così buona, specialmente per i compiti a casa.

Suppongo anche che valga la pena notare che la tecnica sopra può essere eccessiva per alcune situazioni di analisi.

Answer 6

Utilizza un stringstream . Nota l'esempio su quella pagina per la lettura in numeri con un istringstream .

Answer 7

Sicuramente userò questo problema come pretesto per giocare con boost spirito ! Scrivere un po 'di grammatica per questa piccola lingua dovrebbe essere molto divertente.