Alphabetize string with words and numbers

Question

I'm trying to figure out how to alphabetize a single string that contains both words and numbers. As you can see below, I've tried using isdigit but some of the numbers are negative so my code is always wrong. Also, my code splits the string into substrings which alphabetize separately, but I don't know how to alphabetize all of the words separately, put them back into their spots in the vector and then alphabetize all of the numbers separately, and put them back into their spots. Could someone help?

EDIT:

Sample input #1:

4 dog 1 -3 0 cat 3

Sample output #1:

-3 cat 0 1 3 dog 4

Sample input #2:

tom 4 0 9 kid pie 1

Sample output #2:

kid 0 1 4 pie tom 9

So far my code looks like this:

vector<string> numbers; 
string str;
string x;                   
getline (cin, str);
stringstream ss(str);
while (ss >> x){
   numbers.push_back(x);
}

if (numbers.size()==1){
    cout << numbers[0] << endl;
    return 0;
}

vector<int> results(numbers.size());
for (int i=0;i<numbers.size();i++){
    char *a=new char[numbers[i].size()+1];
    a[numbers[i].size()]=0;
    memcpy(a,numbers[i].c_str(),numbers[i].size());
    if(isdigit(*a)==0)
    {
        results[i]=1;
    } else{
        results[i]=0;
    }
}

int j=0;
while (j<numbers.size()){
    int k=j+1;
    while (k<numbers.size()){
        while (results[j]==results[k]){
            sort(numbers.begin()+j,numbers.begin()+k+1);
            k++;
        }
        j=k;
        k=numbers.size();
    }
    if(j==numbers.size()){
        for (int i=0; i<numbers.size();i++){
            cout << numbers[i] << " ";
        }
        j++;
    }
}

Answer 1

First you need a function that determines, whether a string is a number or not. Use strtol for this:

#include <stdlib.h> // strtol

bool is_number( const std::string &str, long &num )
{
    char *p;
    num = strtol( str.c_str(), &p, 10 );
    return *p == '\0';
}

Use this function in a second function, which determines whether string a is less than string b.

#include <tuple>

bool sortFunc( const std::string &a, const std::string &b )
{ 
    long numA;
    long numB;
    bool is_a_num = is_number( a, numA );
    bool is_b_num = is_number( b, numB );
    return std::make_tuple( !is_a_num, numA, a ) < std::make_tuple( !is_b_num, numB, b );                                      
}

Use std::sort, to sort the strings int the std::vector

// include <algorithm> // sort

std::vector< std::string > numbers;
.... 
std::sort( numbers.begin(), numbers.end(), sortFunc );

An other solution would be to split the vector in two separate vectors. One for strings and one for numbers and to sort them separately:

std::vector< std::string > numbers;
....
std::vector< std::string > vStr;
std::vector< long > vNum;
for ( std::string &str: numbers )
{
    long num;
    if ( is_number( str, num )
        vNum.push_back( num );
    else
        vStr.push_back( str);
}
std::sort( vNum.begin(), vNum.end() );
std::sort( vStr.begin(), vStr.end() );

Use a std::map if you want to know the position of each string or number in the original vector.

#include <map>

std::vector< std::string > numbers;
....
std::map< std::string, size_t > mapStr; // map string to index of string in vector numbers
std::map< long, size_t > mapNum;        // map number to index of number in vector numbers
for ( size_t index = 0; index < numbers.size(); index ++ )
{
    long num;
    if ( is_number( numbers[index], num ) )
        mapNum.emplace( num, index );
    else
        mapStr.emplace( numbers[index], index );
}

for ( auto & pa : mapNum )
    std::cout << pa.first << " pos " << pa.second << std::endl;
for ( auto & pa : mapStr )
    std::cout << pa.first.c_str() << " pos " << pa.second << std::endl;

Of course you can use a single std::map with a comparator function too:

std::vector< std::string > numbers;
....
std::map< std::string, size_t, bool(*)(const std::string &a, const std::string &b) > mapN( sortFunc );
for ( size_t index = 0; index < numbers.size(); index ++ )
    mapN.emplace( numbers[index], index );

for ( auto & pa : mapN )
    std::cout << pa.first << " pos " << pa.second << std::endl;

You can use std::tuple as key for the std::map too:

std::vector< std::string > numbers;
....
std::map< std::tuple< bool, long, std::string>, size_t > mapTupleN;
for ( size_t index = 0; index < numbers.size(); index ++ )
{
    long num;
    bool is_num = is_number( numbers[index], num );
    mapTupleN.emplace( std::make_tuple( !is_num, num, numbers[index] ), index );
}
for ( auto & pa : mapTupleN )
{
    if ( !std::get<0>(pa.first) )
        std::cout << std::get<1>(pa.first) << " is number at position " << pa.second << std::endl;
    else
        std::cout << std::get<2>(pa.first).c_str() << " is string at position " << pa.second << std::endl;
}

Answer 2

How about this?

#include "iostream"
#include "algorithm"
#include "string"
#include "vector"
#include "cctype"
#include "unordered_map"
using namespace std;

int main()
{
    vector <string> all, s;
    vector <int> n;
    unordered_map <int, bool> number;
    string x;
    getline(cin, x);
    int prev=0;
    for (int i=0; i<x.length(); i++)
    {
        if (x[i]==' ')
        {
            all.push_back(x.substr(prev, i-prev+1));
            prev=i+1;
        }
    }
    all.push_back(x.substr(prev));
    for (int i=0; i<all.size(); i++)
    {
        if (isdigit(all[i].c_str()[0]) || isdigit(all[i].c_str()[1]))
        {
            n.push_back(atoi(all[i].c_str()));
            number[i]=1;
        }
        else s.push_back(all[i]);
    }
    sort(s.begin(), s.end());
    sort(n.begin(), n.end());
    for (int i=0, j=0, k=0; i<all.size(); i++)
    {
        if (number[i]) cout << n[j++] << ' ';
        else cout << s[k++] << ' ';
    }
}

Answer 3

My 2p.

std::string alphabetize(const std::string& s)
{
    // string parts here
    std::vector<std::string> a;

    // integer parts here
    std::vector<int> n;

    // remember the order of the input types (true = integer, false = string)
    std::vector<bool> type_is_int_list;

    // wrap input in a stream for easy parsing
    std::istringstream iss(s);

    // somewhere to read each part into
    std::string item;

    // extract one space-separated part at a time
    while(iss >> item)
    {
        int i;
        if(std::istringstream(item) >> i) // is item an integer?
        {
            n.push_back(i);
            type_is_int_list.push_back(true);
        }
        else
        {
            a.push_back(item);
            type_is_int_list.push_back(false);
        }
    }

    // sort both string and integer vectors
    std::sort(a.begin(), a.end());
    std::sort(n.begin(), n.end());

    // a place to rebuild the output from the input
    std::ostringstream oss;

    // keep track of where we are in each vector
    auto a_iter = a.begin();
    auto n_iter = n.begin();

    // element separator
    std::string sep;

    // scan originally-ordered list of types to rebuild positions
    for(bool type_is_int: type_is_int_list)
    {
        if(type_is_int)
            oss << sep << *n_iter++; // add next sorted number to output
        else
            oss << sep << *a_iter++; // add next sorted string to output

        sep = " "; // after first item need space separator
    }

    return oss.str(); // return the reconstructed string
}

Answer 4

It's probably easier to sort the elements as you read them in.

std::string input;
std::getline(std::cin, input);
std::stringstream ss(input);
std::vector<std::string> sorted;

while (ss >> input)
{
    bool alpha = 0 < std::isalpha(input[0]); //if it is a word
    for (std::size_t i = 0, e = sorted.size(); i != e; ++i)
    {
        if ((!!std::isalpha(sorted[i][0]) == alpha) && (alpha ? (input < sorted[i]) : (std::stoi(input) < std::stoi(sorted[i])))) //if input is <
            std::swap(sorted[i], input); //exchange places
    }
    sorted.emplace_back(std::move(input)); //insert input at end
}

Each iteration of the while loop, it checks the first character to see if it is a letter. If it is a letter, it must be a word, otherwise it is a number. Then, for each previously scanned element, it checks if they are both the same type (letter/letter, number/number). In the case they are both words, it just compares them. If they are numbers, it uses stoi to convert them to integers and compares the result. If the comparison yields that input is less than the element, it swaps the element with input. By the end of the for loop, input is the greatest element of that type, and it is inserted in the back.

It lives!

Case matters in this comparison ('a' != 'A') but if it shouldn't matter, adding a fix for that is easy.