任意の区切り文字/エスケープ文字処理に最適なアルゴリズムは何ですか？

Question

ウェブ上にこれに関する情報がないことに少し驚きました。私は、問題が私が思っていたより少し固いと感じています。

ここでのルールです：あなたは、区切られて始めている

1. /配列に分割したデータを脱出しました。
2. 区切り文字は、エスケープ文字は任意の1文字で1つの任意の文字
3. ある
4. 区切りと
5. 正規表現が細かいデータに発生する可能性がエスケープ文字が、良いパフォーマンスのソリューションは、
最善である両
6. 編集：（先頭または末尾の区切り文字を含む）を空の要素は
   （C＃で基本的に、あろう）コード署名

を無視することができ

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

問題の最も厄介な部分は、エスケープされた連続エスケープ文字の場合です（もちろん、エスケープ文字と区切り文字を呼び出す）////////、= ////、

これはWebや他のSOの質問で扱われていますか？もしそうでなければ、あなたの大きな頭脳を働かせてください...私はこの問題が公共の利益のためにSOにあることはいいと思っています。私はそれに取り組んでいますが、まだ良い解決策はありません。

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

あなたは「文字列トークナイザ」のようなものを探しています。 versionがあります。私はすぐに似たようなことがわかりました。またはgetoptをご覧ください。

Answer 3

FSMの観点からのこの種のトークナイザの実装はかなり簡単です。

あなたはいくつかの決定を下します（先頭の区切り文字ではどうすればよいですか？NULLトークンを取り除くか放出します）。ここで

---

は、先頭と、複数の区切り文字を無視抽象的なバージョンで、改行をエスケープことはできません：

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; 

実装のこの種のは当然の連続excapesを扱うの利点があり、より多くのエスケープシーケンス（すなわち、ESC(t) token.appeand(TAB)のようなルールを追加する）に特別な意味を与えるように簡単に拡張することができます。

Answer 4

通常、単純な状態マシンが最も簡単で最速の方法です。 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

ここでは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()); 
     } 
    } 

ホープの私の移植機能は、これは将来的に誰かを助けます。私を正しい方向に向けるKenEのおかげです。これは、空の要素を削除しないことを

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

注：

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

は、ここでそれを行うには、より慣用的で読みやすい方法です。私はそれがパーサの責任であるとは思わない。削除する場合は、結果にWhere(item => item.Any())と電話するだけです。

これは、1つの方法ではあまりにも多くのロジックだと思います。それは続くことが難しくなる。誰かが時間を持っているなら、私はそれを複数の方法とそれ自身のクラスに分割するほうがよいと思います。