Сортировка вектора строк C++.

[Alex Fox]

Здравствуйте. Подскажите, пожалуйста, как можно реализовать функцию. Суть такова: у меня есть вектор строк, строки представляют из себя название чисел на английском языке. Для примера:

Используется синтаксис 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");
 

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

[rockclimber]

Преобразовать слова в числа и отсортировать числа?

[venco]

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

[Alex Fox]

Как раз таки преобразование и выходит громоздким. Необходимо определять массивы, которые состоят из всех возможных слов.

Используется синтаксис 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" };
 

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

[arseniiv]

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

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

Alex Fox в сообщении #1192673 писал(а):

Необходимо определять массивы, которые состоят из всех возможных слов.

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

[warlock66613]

Alex Fox в сообщении #1192673 писал(а):

перебирать все массивы

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

[Alex Fox]

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

[warlock66613]

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

[rockclimber]

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

[mustitz]

До миллиона у меня получилось так:

Используется синтаксис 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, миллион — последние три цифры умножаем на миллион, аналогично биллион, ...

[mihaild]

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