7
\$\begingroup\$

I am working on a Roman numerals calculator. For an input validity test I'm using this function:

bool isValidRomanNumeral(string& roman){
    // no test for one-digit Roman numeral  
    if (roman.size() == 1) return true;
    for(size_t i=0; i<roman.size()-1; i++){
        // each more significant digit is either >= previous digit (II, VI, etc)
        if(toArab(to_string(roman[i])) >= toArab(to_string(roman[i+1])) ||
           // or 5 times smaller than previous digit (IV, XL, CD, etc)
           5*toArab(to_string(roman[i])) == toArab(to_string(roman[i+1])) ||
           // or 10 times smaller than previous digit (IX, XC, CM, etc)
           10*toArab(to_string(roman[i])) == toArab(to_string(roman[i+1])));
        else return false;
    }
    return true;}

Function: int toArab(string roman)

int toArab(string s){ 
 map<char, int> roman;
 roman['M'] = 1000;
 roman['D'] = 500;
 roman['C'] = 100;
 roman['L'] = 50;
 roman['X'] = 10;
 roman['V'] = 5;
 roman['I'] = 1;
 int res = 0;
 for(int i=0; i<s.size()-1; ++i){
    if(roman[s[i]] < roman[s[i+1]]) res -= roman[s[i]];
    else res += roman[s[i]];
 }
 res += roman[s[s.size()-1]];
 return res;}

Is there something else that can be done for optimization? Is there a better way to check for Roman numeral validity?

\$\endgroup\$
8
\$\begingroup\$

Bugs

This function will accept invalid strings as valid Roman numerals, e.g. IXC, XCX, IIIII, DD, VL, or A.

You always advance by one character. If you're going to do that, you should use a state machine so that you know what you expect next. Then you'd be able to check that D can't follow D and other invalid entries. Part of the problem is that you can't compare just adjacent characters, e.g. IX and XC are valid substrings but IXC is not.

Repeated initialization

You initialize your roman map each time. It would be better to initialize it once. Consider a pattern like

static map<char, int> value_of;
if ( 0 == value_of.size() ) {
    initialize_digits_map(value_of);
}

Note that I used snake_case for the function name, as that's the standard for C++. I also prefer it in general as it's easier to tell where each word ends and begins for people who may not use the English alphabet natively.

Even better would be to create a conversion class. Your toArab function could then use the conversion class. As could your isValidRomanNumeral function. That would get rid of the unnecessary conversion to string.

Don't repeatedly process an expression with a static value

    for(size_t i=0; i<roman.size()-1; i++){

It's not a big difference, but it can be slightly more efficient to say

    for (size_t i = 0, n = roman.size() - 1; i < n; i++) {

That way you only call the function once and only perform the subtraction once. In this case, the function call will likely get inlined, but the subtraction might not be.

It's generally easier for humans to read if you add more spaces. This won't matter to the compiler but can help people read your code more quickly.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Snake case is not standard for C++ (but it is common). \$\endgroup\$ – Martin York May 3 '15 at 16:15
  • 1
    \$\begingroup\$ Note that to avoid re-initializing the map every call of the function, the variable has to be declared as static. \$\endgroup\$ – glampert May 3 '15 at 18:02
  • \$\begingroup\$ @mdfst13 Considering the comment: "You always advance by one character. If you're going to do that, you should use a state machine so that you know what you expect next.", I agree that this is rather rudimentary validity check, only for two adjacent digits and finite state machine is a better way for pattern recognition. Actually I was thinking to use set or tree with nodes populated with all possible Roman numerals, but it will be an overkill for the purposes of my code. \$\endgroup\$ – Ziezi May 3 '15 at 20:36
  • \$\begingroup\$ @LokiAstari I'm curious: what is the naming standard for C++, then? (I myself have always used snake case). \$\endgroup\$ – SirPython May 3 '15 at 23:15
  • \$\begingroup\$ @SirPython as far as I'm informed either: first_second_third or firstSecondThird are acceptable. \$\endgroup\$ – Ziezi May 4 '15 at 8:59
5
\$\begingroup\$

At first there was code that needed massive comments.

Then came modularization and long, descriptive function names:

bool each_digit_bigger_than_next(string& roman) {
    for(size_t i=0; i<roman.size()-1; i++) {
        if not (toArab(to_string(roman[i])) >= toArab(to_string(roman[i+1]))) {
            return False;
        }
    }
    return True
}

bool each_digit_x_times_smaller_than_previous(string& roman, int times) {
    for(size_t i=0; i<roman.size()-1; i++) {
        if not (times*toArab(to_string(roman[i])) == toArab(to_string(roman[i+1]))) {
            return False;
        }
    }
    return True
}

bool isValidRomanNumeral(string& roman) {
    return roman.length() == 1                                 ||
           each_digit_bigger_than_next(roman)                  ||
           each_digit_x_times_smaller_than_previous(roman, 5)  ||
           each_digit_x_times_smaller_than_previous(roman, 10) ||
}
\$\endgroup\$
  • 1
    \$\begingroup\$ This will produce false for values like XIV which the original code would have correctly marked as true. I is not bigger than V, so the second check fails. X is not (five times nor ten times) smaller than I, so the third and fourth checks fail. XIV has length 3, so the first check fails. Yet the number as a whole is valid. Note that I agree with your point -- it's just the implementation that's flawed. \$\endgroup\$ – mdfst13 May 2 '15 at 20:16
  • \$\begingroup\$ @mdfst13 I tried my best but I never programmed in C++, I made it community Wiki so that an expert C++ developer can come and fix \$\endgroup\$ – Caridorc May 2 '15 at 20:18
3
\$\begingroup\$

Repeated initialization:

int toArab(string s){ 
 map<char, int> roman;
 roman['M'] = 1000;
 roman['D'] = 500;
 roman['C'] = 100;
 roman['L'] = 50;
 roman['X'] = 10;
 roman['V'] = 5;
 roman['I'] = 1;

You only need to do this once (so use static). It is also imutable so make it a const value. If you have C++11 you can use initializer list (otherwise you can wrap it in a function).

// C++ 11
int toArab(string s){ 
 static const map<char, int> roman {
 {'M', 1000},
 {'D', 500},
 {'C', 100},
 {'L', 50},
 {'X', 10},
 {'V', 5},
 {'I', 1}};

// Using map when const can sometime be a pain:
// as you need to use `find()` rather than `operator[]`
// So you could wrap it in a class to take care of that.
class Checker
{ 
     std::map<char, int> roman;
     Checker()
       : roman {
           {'M', 1000},
           {'D', 500},
           {'C', 100},
           {'L', 50},
           {'X', 10},
           {'V', 5},
           {'I', 1}}
     {
         // If you have C++03 initialize in here
     }
     // Assumes 'x' is valid
     int operator[](char x) const {
         std::map<char, int>::const_iterator f = roman.find(x);
         return f->second;
     }
};
int toArab(string s){ 
  static const Checker roman;
| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.