2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Сортировка вектора строк C++.
Сообщение14.02.2017, 17:12 
Аватара пользователя


05/08/11
36
Калининград
Здравствуйте. Подскажите, пожалуйста, как можно реализовать функцию. Суть такова: у меня есть вектор строк, строки представляют из себя название чисел на английском языке. Для примера:
Используется синтаксис C++
vector<string> numbers;

numbers.push_back("three");
numbers.push_back("ten thousand twenty four");
numbers.push_back("forty two");
...............................
...............................
...............................
numbers.push_back("one hundred five");
 

Могут использоваться любые числа до миллиона (это не принципиально, главное чтобы работала для сколь угодно большого наперед заданного числа) . Необходимо отсортировать вектор, так чтобы при выводе его на экран числа/строки шли в порядке возрастания. Если строка состоит из двух или менее слов, то задача простая, но при большем их количестве получается спагетти с кучей вложенных циклов и условных операторов. Может кто-нибудь знает элегантное решение для этой задачи?

 Профиль  
                  
 
 Re: Сортировка вектора строк C++.
Сообщение14.02.2017, 17:27 
Заслуженный участник


06/07/11
5627
кран.набрать.грамота
Преобразовать слова в числа и отсортировать числа?

 Профиль  
                  
 
 Re: Сортировка вектора строк C++.
Сообщение14.02.2017, 17:50 
Заслуженный участник


04/05/09
4582
Я так понял, проблема как раз в преобразовании.
Думаю, гораздо легче будет если решить, что числа уже записаны правильно, и рассчитывая на это написать достаточно простой автомат.

 Профиль  
                  
 
 Re: Сортировка вектора строк C++.
Сообщение14.02.2017, 18:00 
Аватара пользователя


05/08/11
36
Калининград
Как раз таки преобразование и выходит громоздким. Необходимо определять массивы, которые состоят из всех возможных слов.
Используется синтаксис C++
vector<string> singleDigits = { "zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine" };
vector<string> twoDigits = { "ten", "eleven", "twelve", "thirteen", "fourteen", "fifteen", "sixteen", "seventeen", "eighteen", "nineteen" };
vector<string> tenMultiple = {"", "", "twenty", "thirty", "forty", "fifty", "sixty", "seventy", "eighty", "ninety" };
vector<string> tenPower = { "hundred", "thousand" };
 

Затем смотреть из скольки слов пришла строка, перебирать все массивы, чтобы найти совпадение и так для каждого слова.

 Профиль  
                  
 
 Re: Сортировка вектора строк C++.
Сообщение14.02.2017, 18:09 
Заслуженный участник


27/04/09
28128
(Дополняя имеющиеся советы.) Раз у вас там «куча вложенных циклов и условных операторов», значит, вы как минимум не выделили достаточно мелкие функции. Посмотрите, что делают для разбора кода. Даже простой top-down парсер может оказаться достаточным. Может немного подчистить код и выделение отдельной функции-итератора слов в строке, берущей на себя реакцию на неправильное слово или выдающей что-то особенное (например, банально "") в конце строки для упрощения сравнений.

-- Вт фев 14, 2017 20:10:44 --

Alex Fox в сообщении #1192673 писал(а):
Необходимо определять массивы, которые состоят из всех возможных слов.
Ну, их ведь в любом случае вам где-то придётся держать, разумеется. Хотя лучше было бы какой-нибудь map устроить из слов в числа, чтобы преобразовывать проще.

 Профиль  
                  
 
 Re: Сортировка вектора строк C++.
Сообщение14.02.2017, 18:11 
Заслуженный участник


02/08/11
6874
Alex Fox в сообщении #1192673 писал(а):
перебирать все массивы
Ну сделайте для начала функции типа isSingleDigit, isTwoDigit и т. д. Потом посмотреть, нельзя ли ещё какие-нибудь куски кода выделить в функции (ксати, полезное эмпирическое правило: если вы можете дать функции ясное название, описывающее что она делает, то функция выделена правильно).

 Профиль  
                  
 
 Re: Сортировка вектора строк C++.
Сообщение14.02.2017, 18:18 
Аватара пользователя


05/08/11
36
Калининград
Спасибо, сейчас буду разбираться с вашими советами, завтра выложу, что получится. Пока что проблема в том, что число зависит от порядка слов, из которых оно состоит, в итоге для одного случая код работает, но для другого нужно менять порядок сравнения с массивами слов.

 Профиль  
                  
 
 Re: Сортировка вектора строк C++.
Сообщение14.02.2017, 18:22 
Заслуженный участник


02/08/11
6874
Ну, возможно действительно оптимальным решением будет простейший сканер, который делит сроку на слова (и заодно может приписывать каждому слову его тип и числовое значение - такие слова с приписанной к ним допинформацией называются токенами) + простейший LL(1) парсер.

 Профиль  
                  
 
 Re: Сортировка вектора строк C++.
Сообщение14.02.2017, 18:50 
Заслуженный участник


06/07/11
5627
кран.набрать.грамота
Alex Fox
У вас в строке есть слова-разделители: thousand, million, billion и так далее. Сначала бьете строку по этим разделителям. Потом у вас получаются группы слов, каждая из которых обозначает тройку чисел. Каждую тройку, независимо от того, тысячи это, миллионы, миллиарды или что-то еще, вы обрабатываете одним и тем же способом (отбрасывая слова-разделители). То есть задача сводится к парсингу трехзначного числа. А потом просто домножаете результат каждой тройки на $10^{3n}$, где $n$ - порядковый номер тройки чисел.

 Профиль  
                  
 
 Re: Сортировка вектора строк C++.
Сообщение14.02.2017, 19:22 


10/04/12
704
До миллиона у меня получилось так:

код: [ скачать ] [ спрятать ]
Используется синтаксис C
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct numeral {
    const char * name;
    int factor;
    int summand;
};

struct numeral words[] =
{
    { "zero",            1,  0 },
    { "one",             1,  1 },
    { "two",             1,  2 },
    { "three",           1,  3 },
    { "four",            1,  4 },
    { "five",            1,  5 },
    { "six",             1,  6 },
    { "seven",           1,  7 },
    { "eight",           1,  8 },
    { "nine",            1,  9 },
    { "ten",             1, 10 },
    { "eleven",          1, 11 },
    { "twelve",          1, 12 },
    { "thirteen",        1, 13 },
    { "fourteen",        1, 14 },
    { "fiveteen",        1, 15 },
    { "sixteen",         1, 16 },
    { "seventeen",       1, 17 },
    { "eightteen",       1, 18 },
    { "nineteen",        1, 19 },
    { "twenty",          1, 20 },
    { "thirty",          1, 30 },
    { "fourty",          1, 40 },
    { "fifty",           1, 50 },
    { "sixty",           1, 60 },
    { "seventy",         1, 70 },
    { "eighty",          1, 80 },
    { "ninety",          1, 90 },
    { "hundred",        -1, -1 },
    { "thousand",     1000,  0 },
    { NULL, 0, 0}
};

static int cmp(const void * const ptr_a, const void * const ptr_b)
{
    const struct numeral * const a = ptr_a;
    const struct numeral * const b = ptr_b;
    return strcmp(a->name, b->name);
}

void sort_numeral(void)
{
    const size_t words_sz = sizeof(words);
    const size_t element_sz = sizeof(words[0]);
    const size_t words_len = (words_sz / element_sz) - 1;
    qsort(words, words_len, element_sz, cmp);
}

const struct numeral * find_numeral(const char * const str)
{
    const int words_sz = sizeof(words);
    const int element_sz = sizeof(words[0]);

    int start = 0;
    int len = (words_sz / element_sz) - 1;

    while (len > 0) {
        const int step = len / 2;
        const int middle = start + step;
        const int is_less = strcmp(words[middle].name, str) < 0;
        if (is_less) {
            start = middle + 1;
            len -= step + 1;
        } else {
            len = step;
        }
    }

    return words + start;
}

void print_num(const char * line)
{
    int64_t value = 0;

    for (;;) {
        char * str = NULL;
        int pos;
        const int len = sscanf(line, "%ms%n", &str, &pos);

        if (len == EOF || str == NULL) break;

        line += pos;

        const struct numeral * const numeral = find_numeral(str);
        const int is_ok = numeral->name && strcmp(numeral->name, str) == 0;
        if (str != NULL) free(str);

        if (!is_ok) {
            printf("Illegal!\n");
            return;
        }

        if (numeral->factor != -1) {
            value = value * numeral->factor + numeral->summand;
        } else {
            const int digit = value % 10;
            value -= digit;
            value += 100 * digit;
        }
    }

    printf("%ld\n", value);
}

int main()
{
    sort_numeral();

    char * line = NULL;
    size_t line_sz = 0;
    for (;;) {
        ssize_t len = getline(&line, &line_sz, stdin);
        if (len == -1 || strcmp(line, "quit\n") == 0) break;
        print_num(line);
    }

    if (line != NULL) free(line);
}


На самом деле для тысяч и миллионов надо придумать что-то отличное от множителя по аналогии с обработкой сотен. Сотня — берём последнюю цифру, умножаем на 100, тысяча — берём последние три цифры, умножаем на 1000, миллион — последние три цифры умножаем на миллион, аналогично биллион, ...

 Профиль  
                  
 
 Re: Сортировка вектора строк C++.
Сообщение14.02.2017, 19:34 
Заслуженный участник
Аватара пользователя


16/07/14
8348
Цюрих
Можно хранить текущие значения и буфер. hundred увеличивает буфер в 100 раз, thousand/million/billion увеличивают текущее значение на буфер, умноженный на соответствующее число, и обнуляют буфер, всё остальное добавляется к буферу (который в конце прибавляется к значению).

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 11 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group