¿Cuál es el mejor algoritmo para el delimitador arbitrario/procesamiento de caracteres de escape?

Question

Estoy un poco sorprendido de que no haya información sobre esto en la web, y sigo encontrando que el problema es un poco más complicado de lo que pensaba.

Aquí son las reglas:

1. Usted está comenzando con delimitada/escapó de datos a dividirse en una matriz.
2. El delimitador es un carácter arbitrario
3. El carácter de escape es arbitraria carácter
4. Tanto el delimitador y el carácter de escape podría ocurrir en los datos
5. expresión regular está bien, pero una buena solución de rendimiento es mejor
6. Editar: Vaciar elementos (incluyendo al principio o al terminar delimitadores) pueden ser ignorados

La firma de código (en C# sería, básicamente)

public static string[] smartSplit(
         string delimitedData, 
         char delimiter, 
         char escape) {} 

La parte más pegajosa del problema es el caso de escape de caracteres consecutivos, por supuesto, desde (llamar/el carácter de escape y, el delimitador): ////////, = ////,

¿Me falta algo de esto se maneja en la web o en otra pregunta de SO? Si no, pon tus grandes cerebros a trabajar ... Creo que este problema es algo que sería bueno tener en SO para el bien público. Estoy trabajando en eso, pero aún no tengo una buena solución.

Answer 1

void smartSplit(string const& text, char delim, char esc, vector<string>& tokens) 
{ 
    enum State { NORMAL, IN_ESC }; 
    State state = NORMAL; 
    string frag; 

    for (size_t i = 0; i<text.length(); ++i) 
    { 
     char c = text[i]; 
     switch (state) 
     { 
     case NORMAL: 
      if (c == delim) 
      { 
       if (!frag.empty()) 
        tokens.push_back(frag); 
       frag.clear(); 
      } 
      else if (c == esc) 
       state = IN_ESC; 
      else 
       frag.append(1, c); 
      break; 
     case IN_ESC: 
      frag.append(1, c); 
      state = NORMAL; 
      break; 
     } 
    } 
    if (!frag.empty()) 
     tokens.push_back(frag); 
} 

Answer 2

Usted está buscando algo así como un "tokenizador de cuerda". Hay un version que encontré rápidamente que es similar. O mira getopt.

Answer 3

La implementación de este tipo de tokenizador en términos de FSM es bastante sencilla.

Tiene que tomar algunas decisiones (por ejemplo, ¿qué debo hacer con los delimitadores principales? Eliminar o emitir tokens NULL).

---

Aquí es una versión abstracta que ignora líder y múltiples delimitadores, y no permite que se escape el salto de línea:

state(input)  action 
======================== 
BEGIN(*):   token.clear(); state=START; 
END(*):   return; 
*(\n\0):   token.emit(); state=END; 
START(DELIMITER): ; // NB: the input is *not* added to the token! 
START(ESCAPE): state=ESC; // NB: the input is *not* added to the token! 
START(*):   token.append(input); state=NORM; 
NORM(DELIMITER): token.emit(); token.clear(); state=START; 
NORM(ESCAPE):  state=ESC; // NB: the input is *not* added to the token! 
NORM(*):   token.append(input); 
ESC(*):   token.append(input); state=NORM; 

Este tipo de aplicación tiene la ventaja de tratar con excapes consecutivos de forma natural, y se puede extender fácilmente para dar un significado especial a más secuencias de escape (es decir, agregar una regla como ESC(t) token.appeand(TAB)).

Answer 4

Una máquina de estado simple es generalmente la forma más fácil y rápida. Ejemplo en Python:

def extract(input, delim, escape): 
    # states 
    parsing = 0 
    escaped = 1 

    state = parsing 
    found = [] 
    parsed = "" 

    for c in input: 
    if state == parsing: 
     if c == delim: 
     found.append(parsed) 
     parsed = "" 
     elif c == escape: 
     state = escaped 
     else: 
     parsed += c 
    else: # state == escaped 
     parsed += c 
     state = parsing 

    if parsed: 
    found.append(parsed) 

    return found 

Answer 5

Aquí está mi función portado en C#

public static void smartSplit(string text, char delim, char esc, ref List<string> listToBuild) 
    { 
     bool currentlyEscaped = false; 
     StringBuilder fragment = new StringBuilder(); 

     for (int i = 0; i < text.Length; i++) 
     { 
      char c = text[i]; 
      if (currentlyEscaped) 
      { 
       fragment.Append(c); 
       currentlyEscaped = false; 
      } 
      else 
      { 
       if (c == delim) 
       { 
        if (fragment.Length > 0) 
        { 
         listToBuild.Add(fragment.ToString()); 
         fragment.Remove(0, fragment.Length); 
        } 

       } 
       else if (c == esc) 
        currentlyEscaped = true; 
       else 
        fragment.Append(c); 
      } 
     } 

     if (fragment.Length > 0) 
     { 
      listToBuild.Add(fragment.ToString()); 
     } 
    } 

Esperamos que esto ayude a alguien en el futuro. Gracias a KenE por señalarme en la dirección correcta.

Answer 6

private static string[] Split(string input, char delimiter, char escapeChar, bool removeEmpty) 
    { 
     if (input == null) 
     { 
      return new string[0]; 
     } 

     char[] specialChars = new char[]{delimiter, escapeChar}; 

     var tokens = new List<string>(); 
     var token = new StringBuilder(); 

     for (int i = 0; i < input.Length; i++) 
     { 
      var c = input[i]; 

      if (c.Equals(escapeChar)) 
      { 
       if (i >= input.Length - 1) 
       { 
        throw new ArgumentException("Uncompleted escape sequence has been encountered at the end of the input"); 
       } 

       var nextChar = input[i + 1]; 

       if (nextChar != escapeChar && nextChar != delimiter) 
       { 
        throw new ArgumentException("Unknown escape sequence has been encountered: " + c + nextChar); 
       } 

       token.Append(nextChar); 
       i++; 
      } 
      else if (c.Equals(delimiter)) 
      { 
       if (!removeEmpty || token.Length > 0) 
       { 
        tokens.Add(token.ToString()); 
        token.Length = 0; 
       } 
      } 
      else 
      { 
       var index = input.IndexOfAny(specialChars, i); 

       if (index < 0) 
       { 
        token.Append(c); 
       } 
       else 
       { 
        token.Append(input.Substring(i, index - i)); 
        i = index - 1; 
       } 
      } 
     } 

     if (!removeEmpty || token.Length > 0) 
     { 
      tokens.Add(token.ToString()); 
     } 

     return tokens.ToArray(); 
    } 

Answer 7

Aquí está una manera más idiomática y legible para hacerlo:

public IEnumerable<string> SplitAndUnescape(
    string encodedString, 
    char separator, 
    char escape) 
{ 
    var inEscapeSequence = false; 
    var currentToken = new StringBuilder(); 

    foreach (var currentCharacter in encodedString) 
     if (inEscapeSequence) 
     { 
      currentToken.Append(currentCharacter); 
      inEscapeSequence = false; 
     } 
     else 
      if (currentCharacter == escape) 
       inEscapeSequence = true; 
      else 
       if (currentCharacter == separator) 
       { 
        yield return currentToken.ToString(); 
        currentToken.Clear(); 
       } 
       else 
        currentToken.Append(currentCharacter); 

    yield return currentToken.ToString(); 
} 

Tenga en cuenta que esto no elimina los elementos vacíos. No creo que eso deba ser responsabilidad del analizador. Si desea eliminarlos, simplemente llame al Where(item => item.Any()) en el resultado.

Creo que esto es demasiado lógico para un solo método; se vuelve difícil de seguir. Si alguien tiene tiempo, creo que sería mejor dividirlo en múltiples métodos y tal vez en su propia clase.