Analisar uma string em C ++

Question

Eu estou tentando fazer um construtor para uma classe gráfico que aceita uma cadeia como um parâmetro e usa-lo para construir o gráfico.

A cadeia está formatado como segue: |vertex list|Edges list| por exemplo. |1,2,3,4,15|(1->2),(3->2),(4->15)|

A idéia é que o construtor terá os valores da seqüência e, em seguida, saber para executar as seguintes acções (inserindo os vértices para a lista de vértice e, em seguida, inserindo as bordas para a lista bordas):

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

Eu teria feito apenas um par de "para" loops para digitalizar a corda, mas eu não sei o que fazer com números de dois (ou mais) dígitos. Estou começando a imaginar todos os tipos de sério complicado para loops e eu estou querendo saber se alguém aqui poderia compartilhar comigo todas as maneiras mais inteligentes para extrair e utilizar esses dados.

Answer 1

Você pode usar um stringstream e usar o operador de extração de fluxo para obter seus números inteiros.

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

Uma vez que esta é a lição de casa, exorto-vos a explorar as possibilidades e descobrir a completa código para si mesmo.

Answer 2

Você parece ser ficar sobrecarregado olhando para a coisa toda. Quebrá-lo em pedaços ... tarefas. O que você está tentando fazer parece ser funcionalidades separadas aqui.

1. tokenizing
2. Análise Vértices
3. Análise Bordas
4. Execution nos vértices
5. Execução nas bordas

Isso é 5 funções mais ou menos.

Você está querendo tokenizar baseado no pipe (|). Então dê uma substring baseada no tubo e passar cada lado para o analisador apropriado, parse nas vírgulas e assim por diante

Não vai fazer isso por você, mas espero que eu possa começar a pensar na direção certa. Aprender a programar não é tanto sobre qualquer linguagem particular, mas sobre como alterar a maneira como você pensa.

Answer 3

Eu nunca usei isso antes, mas há um impulso tokenizer classe. Você poderia tê-lo facilmente quebrar a coisa em componentes para você sem toda a for-loop.

Answer 4

Sem fazer sua lição de casa para você, isso vai lhe dar um bom ponto de partida. Eu dei-lhe o fluxo de trabalho básico para a lista vértice de análise, você deve ser capaz de fazer a lista de borda si mesmo. Deixo também a verificação de erros para você, por exemplo, em parseVertex () você pode querer dar um erro quando se deparar com caracteres invá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

Analisando esse tipo de coisa é bastante simples (embora tediosa) com técnicas de descida recursiva. A idéia é separar a linguagem que está sendo analisado em unidades lógicas, em seguida, escrever uma função para analisar cada uma dessas unidades.

Se nós figuramos no exemplo "| 1,2,3,4,15 | (1-> 2), (3> 2), (4> 15) |" que toda a string é um "polígono", que iria escrever parsePolygon (), que seria algo parecido com isto:

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

Vamos supor tampão é uma classe que corre em suas cordas. Você vai precisar de duas operações básicas:. Espiada no próximo caractere sem consumi-lo, e consumir o próximo caractere

parseVertices pode ter esta aparência:

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

Você gostaria de erros alça muito melhor, obviamente. Se o fluxo encontra qualquer erro que precisa para passar o código de erro se a pilha de chamadas ou lançar uma exceção.

Dois mais exemplos ... parseVertexList e parseNumber pode ter esta aparência:

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

Isso tudo é muito rápido e sujo, mas espero que lhe dá uma idéia de como as obras técnica. Você pode misturar o seu manuseamento com a sua análise, como mostrado acima, em que a função parseVertexList realmente faz as chamadas addVertex para você.

Eu penso que este é realmente um dos métodos mais simples de análise manual. Idealmente nós sempre ser capaz de usar os analisadores gerados como impulso espírito ou pyparsing ou lex / yacc, mas a vida nem sempre é tão bom, especialmente para trabalhos de casa.

Além disso Acho que é importante notar que a técnica acima pode ser um monte de exagero para algumas situações de análise.

Answer 6

Use a stringstream . Observe o exemplo nessa página para leitura em números com um istringstream.

Answer 7

Eu certamente utilizar este problema como um pretexto para jogar com boost espírito! Escrevendo um pouco de gramática para esta pequena linguagem deve ser muito divertido.