Roman Numeral to Decimal Conversion

Question

I'm mostly looking to get feedback on how well I've implemented the C++ language. But I would also like feedback on my algorithm. Did I make it more complex than it needs to be? Is there anything I could have done better?

Things my algorithm prevents:

• IIII <- "too many multiples," better represented as IV
• IIIV <- "cannot add the same digit to a subtraction," better represented as VI
• IVI <- "addition cannot follow subtraction," better represented as V
• IXX <- "cannot subtract from a multiple," better represented as XIX

Things it does not prevent (that I'm aware of):

• XICV <- "bad format," better represented as CXIV
• IXIX <- "repeated subtraction," better represented as XVIII
• VV <- "multiple is value of existing digit," better represented as X

Note: This uses the rules of roman numerals I was taught, and I realize that there isn't really a an accepted standard of rules for representing numbers using roman numerals.

#include <string>
#include <stack>
#include <iostream>
#include <ctype.h> // required for tolower()

using namespace std;

int get_roman_value( char );
int roman_to_decimal( string& );

int main( int argc, char* argv[] )
{

    if( argc > 1 )
    {
        string roman(argv[1]);
        try {
            cout << roman_to_decimal(roman) << endl;
        } catch( const char* e ) {
            cerr << e << endl;
        }

    }

    return 0;
}

int get_roman_value( char digit )
{
    switch( tolower(digit) )
    {
        case 'i': return    1; break;
        case 'v': return    5; break;
        case 'x': return   10; break;
        case 'l': return   50; break;
        case 'c': return  100; break;
        case 'd': return  500; break;
        case 'm': return 1000; break;
        default: throw "bad digit";
    }   
    return 0;
}

int roman_to_decimal( string& roman )
{

    int decimal = 0;    // the final result
    int multiple = 0;   // keeps track of multiples, eg. In XXV, X would be a multiple
    int current = 0;    // the digit currently being processed
    int last_add = 0;   // the last digit that wasn't a multiple, or subtraction operation
    int last_sub = 0;
    stack<int> digits;  // queue of the digits
    string::iterator i; // iterator to loop through the roman string


    for( i = roman.begin(); i < roman.end(); i++ )
        digits.push( get_roman_value(*i) );

    do
    {

        // get the current digit
        current=digits.top(), digits.pop();

        // if there are too many multiples, then throw up
        if( multiple > 2 )
            throw "too many multiples";

        // check for a substraction operation
        if( !digits.empty() && current > digits.top() )
        {
            if( multiple > 0 )
                throw "cannot subtract from a multiple";
            if( last_add == digits.top() )
                throw "addition cannot follow subtraction";
            decimal+=(current-digits.top()), last_sub=digits.top(), digits.pop();
        }
        // check for multiples
        else if( !digits.empty() && current == digits.top() )
            decimal += current, multiple++;
        // regular addition operation
        else
            if( last_sub == current )
                throw "cannot add the same digit to a subtraction";
            else
                decimal+=current, multiple=0, last_add=current;

    } while( !digits.empty() );

    return decimal;

}

Answer 1

Well, first of all you should probably declare variables closer to usage. Not only this will compress your code a bit, it will also save you the trouble of assigning random things to them. For example int current = 0 declaration can be omitted.

You normally want to use != operator when dealing with iterators, so that you can switch containers, implementations, etc; and you'd generally want to increase the iterator without making an extra copy of same. So for example the following

for( i = roman.begin(); i < roman.end(); i++ )
    digits.push( get_roman_value(*i) );

is better written as

for( i = begin(roman); i != end(roman); ++i )
    digits.push( get_roman_value(*i) );

also, there are some obscure reasons to write begin(container) and end(container) instead of invoking member functions, but most would say it's a matter of taste.

Depending on how serious your are, you shouldn't throw strings, instead throw something that derives from exception, which is a part of STL which lives in "<exception>" header.

Then there's some redundancy in your switch, for example

case 'i': return    1; break;

the break statement is not necessary, and most programmers are very familiar with case -> return pattern. Ultimately it's a matter of taste, I guess.

EDIT Answer to comment

I would prefer to remove the declaration of int current = 0, and instead use:

// get the current digit
int current = digits.top();
digits.pop();

Although I personally like your use of comma operator, most people emphatically do not; and encourage to separate statements on separate lines.

I also noticed you are a bit inconsistent with spaces, it's advisable to always have same rules everywhere. For example there are places where you surround the assignment operator with spaces, and then there are cases when you don't.

Answer 2

Your code doesn't handle an empty input (./rom2dec "") well, it tries to call top and pop on an empty stack. I'd simply move the while to the beginning of the loop, since I consider the empty roman numeral to have a value of zero, but you might want to throw an error instead.

roman_to_decimal does not modify its argument and is probably not intended to ever do so, so it should take a const reference.

As Gleno said, throwing strings is not really a great habit. If you exit the program after an error, it's best to return an error code, so your caller can react to the error situation. I.e., don't return 0 if an error happened. return 1 is the most common choice for generic errors; if you want to distinguish between different types of errors, returning different non-zero numbers is the common way.

Another thing Gleno already pointed out, I just thought I'd point out a different example: Since you're not using i after the loop through the string, it's probably a good idea to scope it accordingly:

for (string::const_iterator i = begin(roman); i != end(roman); ++i) {
  digits.push(get_roman_value(*i));
}

Note that there is no reason to document what i is: The code already says it all. (Too bad there is no push_iterator for stacks.) In C++11, write auto in lieu of string::const_iterator.

(Note the ++i: Whenever you're not using the return value of an increment, it's a good habit to use pre-increment. Makes no real difference 99% of the time, but sometimes, it does.)

I have over time moved towards always using braces for for, if, else etc. It makes working on the code much safer and is something I now also find easier to read. Like many things with code styles, that is mostly personal preference, of course. Just like I dislike the space distribution you are using – for, if, and switch are not function calls and in my opinion should not look like one; instead, I always put one space between the keyword and its (. For cohesion, I never put spaces after an opening parenthesis or before a closing one, with the obvious exception of indenting. As Gleno said, pick any style and then stay consistent.

Answer 3

A few things:

1. I would have probably used the std::string containing the Roman numeral rather than converting it to a stack.

2. I avoid the using std in CPPs preferring to prefix Standard Lib methods with std::.

3. The initial test for argc > 1 could be made more flexible by looping over all the inputs rather than the first one, e.g.

   while (*++argv != NULL) std::cout << *argv << std::endl;
   

4. By re-ordering the methods to be:

   roman_to_decimal
   get_roman_value
   main
   

   the forward declarations of the functions at the top are not needed. Currently the declaration for roman_to_decimal() is superfluous as the definition is before get_roman_value() which uses it.

5. The function parameters could be const.

6. The comment regarding using begin() and end() is better than it seems. Rather than using these for obscure reasons the C++11 standard encourages this use.