patterncppMinor
Checking for Roman numeral validity
Viewed 0 times
romancheckingvaliditynumeralfor
Problem
I am working on a Roman numerals calculator. For an input validity test I'm using this function:
Function:
Is there something else that can be done for optimization? Is there a better way to check for Roman numeral validity?
bool isValidRomanNumeral(string& roman){
// no test for one-digit Roman numeral
if (roman.size() == 1) return true;
for(size_t i=0; i= 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 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?
Solution
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
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
Don't repeatedly process an expression with a static value
It's not a big difference, but it can be slightly more efficient to say
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.
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 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.
Code Snippets
static map<char, int> value_of;
if ( 0 == value_of.size() ) {
initialize_digits_map(value_of);
}for(size_t i=0; i<roman.size()-1; i++){for (size_t i = 0, n = roman.size() - 1; i < n; i++) {Context
StackExchange Code Review Q#88644, answer score: 9
Revisions (0)
No revisions yet.