10

英数字の文字列は、人間が並べ替えるのと同じように並べ替えたいと思います。つまり、「A2」は「A10」の前にあり、「a」は確かに「Z」の前にあります。ミニパーサーを作成せずに処理する方法はありますか？理想的には、「A1B10」の前に「A1B1」も配置します。「MicrosoftSQL2005での自然な（人間の英数字）並べ替え」という質問に答えられる可能性がありますが、 「IComparerを使用した人間の文字列の並べ替え」と同様に、さまざまなライブラリ関数を使用しています。

以下は、現在失敗しているテストケースです。

#include <set>
#include <iterator>
#include <iostream>
#include <vector>
#include <cassert>

template <typename T>
struct LexicographicSort {
  inline bool operator() (const T& lhs, const T& rhs) const{
    std::ostringstream s1,s2;
    s1 << toLower(lhs); s2 << toLower(rhs);
    bool less = s1.str() < s2.str();
    //Answer: bool less = doj::alphanum_less<std::string>()(s1.str(), s2.str());
    std::cout<<s1.str()<<" "<<s2.str()<<" "<<less<<"\n";
    return less;
  }

  inline std::string toLower(const std::string& str) const {
    std::string newString("");
    for (std::string::const_iterator charIt = str.begin();
         charIt!=str.end();++charIt) {
          newString.push_back(std::tolower(*charIt));
        }
        return newString;
      }
};


int main(void) {
  const std::string reference[5] = {"ab","B","c1","c2","c10"};
  std::vector<std::string> referenceStrings(&(reference[0]), &(reference[5]));

  //Insert in reverse order so we know they get sorted
  std::set<std::string,LexicographicSort<std::string> > strings(referenceStrings.rbegin(), referenceStrings.rend());

  std::cout<<"Items:\n";
  std::copy(strings.begin(), strings.end(), std::ostream_iterator<std::string>(std::cout, "\n"));
  std::vector<std::string> sortedStrings(strings.begin(), strings.end());
  assert(sortedStrings == referenceStrings);
}
4

4 に答える 4

5

ミニパーサーを作成せずに処理する方法はありますか？

他の誰かにそれをさせますか？

私はこの実装を使用しています：http ： //www.davekoelle.com/alphanum.html、wchar_tもサポートするように変更しました。

于 2010-05-06T20:19:50.097 に答える
2

それは本当に「パーサー」の意味によって異なります。パーサーの作成を避けたい場合は、ライブラリー関数を利用する必要があると思います。

  • 文字列を、一律にアルファベット、数字、または「その他」のサブシーケンスのシーケンスとして扱います。
  • を使用して各文字列の次の英数字シーケンスを取得し、それが数値であるかどうかisalnumをバックトラックチェックします。インプレースを使用して、数値サブシーケンスの終わりを見つけます。+-strtold
  • 1つが数値で、もう1つがアルファベットの場合、数値のサブシーケンスを持つ文字列が最初に来ます。
  • 1つの文字列の文字数が不足している場合は、最初に表示されます。
  • strcoll現在のロケール内のアルファベットのサブシーケンスを比較するために使用します。
  • strtold現在のロケール内の数値サブシーケンスを比較するために使用します。
  • 一方または両方の文字列で終了するまで繰り返します。
  • との関係を断ち切るstrcmp。

このアルゴリズムには、の精度を超える数値文字列を比較する際に多少の弱点がありますlong double。

于 2010-05-06T20:30:49.323 に答える
0

ミニパーサーを書かずにそれを行う方法はありますか？答えはノーだと思います。しかし、パーサーを書くことはそれほど難しいことではありません。しばらく前に会社の在庫数を並べ替える必要がありました。基本的には、数値をスキャンして配列に変換するだけです。すべての文字の「タイプ」を確認してください：アルファ、数字、多分あなたはあなたが特別に扱う必要がある他のものを持っています。ABCをAB-Aの前にソートしたかったので、ハイフンを特別に処理する必要があったように。次に、キャラクターの剥がしを開始します。それらが最初の文字と同じタイプである限り、それらは同じバケットに入ります。タイプが変更されたら、それらを別のバケットに入れ始めます。次に、バケットごとに比較する比較関数も必要です。両方のバケットがアルファの場合、通常のアルファ比較を行うだけです。両方が数字の場合、両方を整数に変換し、整数比較を行います。または、短い方を長い方の長さまたは同等の長さにパディングします。それらが異なるタイプである場合、AAがA-1の前または後に来るように、それらを比較する方法のルールが必要になりますか？

それは簡単な仕事ではなく、発生する可能性のあるすべての奇妙なケースのルールを考え出す必要がありますが、数時間の作業でそれをまとめることができると思います。

于 2010-05-06T19:51:45.537 に答える
0

構文解析なしでは、人間が書いた数字（最初に高い値で先行ゼロが削除されたもの）と通常の文字を同じ文字列の一部として比較する方法はありません。

ただし、解析はそれほど複雑である必要はありません。大文字と小文字の区別や特殊文字の削除などを処理するための単純なハッシュテーブル（'A' ='a' = 1、'B' ='b' = '2、...または' A'= 1、' a ' = 2、'B' = 3、...、'-' = 0（strip））、文字列をハッシュ値の配列に再マップしてから、数値のケースを切り捨てます（数値が検出され、最後の文字が数値、最後の数値に10を掛けて、現在の値を加算します）。

そこから、通常どおりに並べ替えます。

于 2010-05-06T20:15:07.950 に答える