How to add commas to a string using recursion

Question

I'm a beginner on programming. I'm coding a school assignment and its asking me to add commas to a string using recursion. I have most of it done but when I input a number greater than a million it doesn't add a comma before the first digit. This is what i have so far:

// commas - Convert a number (n) into a string, with commas
string commas(int n) {

    ostringstream converted;
    converted << n;

    string number = converted.str();

    int size = number.length();

    if (size < 4 )
    {
    return number;
    }
    if (size >= 4 )
    {
        return number.substr(0, number.size() - 3) + "," + number.substr(number.size() - 3, number.length());
    }
}

Any help would be greatly appreciated!

How is your function named? Where is the recursive call? Show more code. And the second `if` could simply be an `else` — Basile Starynkevitch, Feb 28 '14 at 07:44
You're not adding a special case for `1000000`, so it looks like `1000,000`. — , Feb 28 '14 at 07:47

score 2 · Answer 1 · 2014-02-28T08:21:03.577

The algorithm is fairly simple. It is very similar to your solution except I added the part necessary for recursion. To understand how it works, remove tack_on. Here is example output:

1
10
100

These are the first groups that are returned when the terminating condition is reached (s.size() < 4). Then the rest of the groups are prefixed with a comma and "tacked on". The entire string is built using recursion. This is important because if you left number.substr(0, number.size() - 3) in, your output would look like this:

11,000
1010,000
100100,000
11,0001000,000

I use std::to_string which is C++11:

#include <iostream>

std::string addCommas(int n)
{
    std::string s = std::to_string(n);
    if (s.size() < 4) return s;
    else
    {
        std::string tack_on = "," + s.substr(s.size() - 3, s.size());
        return addCommas(n / 1000) + tack_on;
    }
}

You only need to make minimal changes for the C++03/stringstream version:

#include <sstream>

std::ostringstream oss;

std::string addCommas(int n)
{
    oss.str(""); // to avoid std::bad_alloc
    oss << n;
    std::string s = oss.str();
    // etc
}

Testing:

int main()
{
    std::cout << addCommas(1) << "\n";
    std::cout << addCommas(10) << "\n";
    std::cout << addCommas(100) << "\n";
    std::cout << addCommas(1000) << "\n";
    std::cout << addCommas(10000) << "\n";
    std::cout << addCommas(100000) << "\n";
    std::cout << addCommas(1000000) << "\n";
    return 0;
}

Output:

Considering this is a beginners assigment I think the s.substr(s.size() - 3, s.size()) is a bit to clever ;) — uncletall, Feb 28 '14 at 08:38
@uncletall It's from his code. `size` and `length` are identical. — , Feb 28 '14 at 08:39
You are right... guess that's why I didn't quite understand what he was up to (+1) — uncletall, Feb 28 '14 at 08:42

score 1 · Answer 2 · answered Feb 28 '14 at 08:33

I think this one is a bit simpler and easier to follow:

std::string commas(int n)
{
    std::string s = std::to_string(n%1000);
    if ((n/1000) == 0) return s;
    else
    {
        // Add zeros if required
        while(s.size() < 3)
        {
            s = "0" + s;
        }
        return commas(n / 1000) + "," + s;
    }
}

cpp-progger · Answer 3 · 2014-02-28T08:47:52.113

0

an alternative approach without recursion:

class Grouping3 : public std::numpunct< char >
{
protected:
    std::string do_grouping() const { return "\003"; }
};

std::string commas( int n )
{
    std::ostringstream converted;
    converted.imbue( std::locale( converted.getloc(), new Grouping3 ) );
    converted << n;
    return converted.str();
}

will need #include <locale> in some environments

A possible solution for the assignment could be:

std::string commas( std::string&& str )
{
    return str.length() > 3?
        commas( str.substr( 0, str.length()-3 ) ) + "," + str.substr( str.length()-3 ):
        str;
}
std::string commas( int n )
{
    std::ostringstream converted;
    converted << n;
    return commas( converted.str() );
}

edited Feb 28 '14 at 08:47

answered Feb 28 '14 at 08:34

cpp-progger

406
3
6

The assignment was to use recursion, not to use locale – uncletall Feb 28 '14 at 08:36
It should not be a solution of the assignment, it should be an alternative approach without recursion ;-) – cpp-progger Feb 28 '14 at 08:38
I add a possible solution for the assignment in my answer – cpp-progger Feb 28 '14 at 08:48

How to add commas to a string using recursion

3 Answers3