Строковый вид C++ как человек?
Я хотел бы отсортировать алфавитно-цифровые строки путем, человек отсортирует их. Т.е. "A2" прибывает перед "A10", и "a", конечно, прибывает прежде "Z"! Там какой-либо путь состоит в том, чтобы сделать с, не пишущий мини-синтаксический анализатор? Идеально это также поместило бы "A1B1" перед "A1B10". Я вижу вопрос, "Естественный (алфавитно-цифровой человек) вид в Microsoft SQL 2005" с возможным ответом, но это использует различные библиотечные функции, как делает "Строки сортировки для Людей с IComparer".
Ниже тестовый сценарий, который в настоящее время перестал работать:
#include
#include
#include
#include
#include
template
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()(s1.str(), s2.str());
std::cout< referenceStrings(&(reference[0]), &(reference[5]));
//Insert in reverse order so we know they get sorted
std::set > strings(referenceStrings.rbegin(), referenceStrings.rend());
std::cout<<"Items:\n";
std::copy(strings.begin(), strings.end(), std::ostream_iterator(std::cout, "\n"));
std::vector sortedStrings(strings.begin(), strings.end());
assert(sortedStrings == referenceStrings);
}
4 ответа
Есть ли способ обойтись без написания мини-парсера?
Пусть это сделает кто-нибудь другой?
Я использую эту реализацию : http://www.davekoelle.com/alphanum.html , я также изменил его для поддержки wchar_t.
Без парсинга нет способа сравнить написанные человеком числа (старшие значения первыми с вычеркнутыми ведущими нулями) и обычные символы как часть одной и той же строки.
Однако парсинг не должен быть очень сложным. Простая хэш-таблица для работы с такими вещами, как чувствительность к регистру и удаление специальных символов ('A'='a'=1,'B'='b'='2,... или 'A'=1,'a'=2,'B'=3,..., '-'=0(strip)), переназначение вашей строки в массив хэшированных значений, затем усечение случаев чисел (если встречается число и последний символ был числом, умножьте последнее число на десять и добавьте к нему текущее значение).
После этого выполните обычную сортировку.
Это действительно зависит от того, что вы подразумеваете под "синтаксическим анализатором". Если вы не хотите писать синтаксический анализатор, я думаю, вам следует воспользоваться библиотечными функциями.
- Рассматривать строку как последовательность подпоследовательностей, которые имеют единообразный алфавитный, числовой или «другой характер».
- Получить следующую буквенно-цифровую последовательность каждой строки, используя
isalnumи проверку с возвратом для+или-, если это число. Используйте на местеstrtold, чтобы найти конец числовой подпоследовательности. - Если один числовой, а другой буквенный, сначала идет строка с числовой подпоследовательностью.
- Если в одной строке закончились символы, она идет первой.
- Используйте
strcollдля сравнения алфавитных подпоследовательностей в текущей локали. - Используйте
strtoldдля сравнения числовых подпоследовательностей в текущей локали. - Повторяйте, пока не закончите с одной или обеими струнами.
- Прервать связь с
strcmp.
Этот алгоритм имеет слабую сторону при сравнении числовых строк, точность которых превышает точность long double .
Есть ли способ сделать это без написания мини-парсера? Я думаю, что ответ отрицательный. Но написать парсер не так уж и сложно. Мне пришлось сделать это некоторое время назад, чтобы отсортировать номера акций нашей компании. В основном просто сканируйте число и превращайте его в массив. Проверьте «тип» каждого символа: альфа, число, возможно, у вас есть другие, с которыми вам нужно иметь дело. Например, мне пришлось относиться к дефисам специально, потому что мы хотели, чтобы A-B-C сортируется перед AB-A. Затем начните отклеивать персонажей. Пока они того же типа, что и первый персонаж, они попадают в одно и то же ведро. Как только тип изменится, вы начнете помещать их в другую корзину. Тогда вам также понадобится функция сравнения, которая сравнивает корзину за корзиной. Когда оба сегмента являются альфа-версиями, вы просто делаете обычное альфа-сравнение. Если оба являются цифрами,преобразовать оба в целое число и сделать целое сравнение, или наполнить более короткую длину длиной или что-то эквивалентное. Когда они разные типы, вам понадобится правило того, как они сравниваются, например, A-A приходит до или после A-1?
Это не тривиальная работа, и вы должны придумать правила для всех странных случаев, которые могут возникнуть, но я думаю, что вы могли бы собрать это вместе за несколько часов работы.