How to Convert Roman to Integer in C/C++ and Python?

Convert a Roman numeral value (ranged from 1 to 3999) to Arabic integer.

Letter by Letter Conversion from Roman to Arabic

The first few Roman numbers are: I, II, III, IV, V, VI, VII, VIII, IX, X. And we have the following:

roman['I'] = 1;
roman['V'] = 5;
roman['X'] = 10;
roman['L'] = 50;
roman['C'] = 100;
roman['D'] = 500;
roman['M'] = 1000;

So, the Roman number LXXIX equals 50 + 10 + 10 – 1 + 10 = 79. I is before X and I is smaller than X, so we deduct it from the final value. Otherwise, we add the value. So the idea is as easy as its implementation. O(n) complexity.

class Solution {
public:
    int romanToInt(string s) {
        int r = 0;
        unordered_map<char, int> roman({ // we could also use vector with pair, or map.
            {'I', 1} ,
            {'V', 5},
            {'X', 10},
            {'L', 50},
            {'C', 100},
            {'D', 500},
            {'M', 1000}
        });
        for (int i = 0; i < s.length() - 1; i ++) {
            int cur = roman[s[i]];
            int next = roman[s[i + 1]];
            if (cur >= next) {
                r += cur;
            } else {
                r -= cur;
            }
        }
        return r + roman[s[s.length() - 1]]; // don't forget the last character
    }
};

Another example: XLVI in Roman equals -10 + 50 + 5 + 1 = 46. The first X equals minus 10 because the next character is L.
Another example: LVII in Roman equals 50 + 5 + 1 + 1 = 57. Any character is no less than its next character, we simply add all values.
This implementation runs at complexity O(N) – scanning the Roman string character by character – if next character is larger, we need to deduct the corresponding value.

Python algorithm to Convert the Roman Numerals to Arabic Integers:

class Solution:
    def convertRomanToArabic(self, numeral):
        mapping = {
            'M': 1000,
            'D': 500,
            'C': 100,
            'L': 50,
            'X': 10,
            'V': 5,
            'I': 1
        }      
        ans = 0  
        for i in range(len(numeral) - 1):
            if mapping[numeral[i]] >= mapping[numeral[i + 1]]:
                ans += mapping[numeral[i]]
            else:
                ans -= mapping[numeral[i]]
        return ans + mapping[numeral[-1]]

Prefix Method to Convert Roman Numbers to Arabic

We can expand the mapping table to include “IV”, “IX”, “XC”, “CD” and “CM” where the minus arithmetic is involved. Then, we can scan the Roman string to jump over any prefix string found and accumulate the corresponding value.

class Solution {
public:
    int romanToInt(string s) {
        vector<pair<string, int>> romans({
            {"M", 1000},
            {"CM", 900},
            {"D", 500},
            {"CD", 400},
            {"C", 100},
            {"XC", 90},
            {"L", 50},
            {"XL", 40},
            {"X", 10},
            {"IX", 9},
            {"V", 5},
            {"IV", 4},
            {"I", 1}        
        });
        auto r = 0;
        while (s.size() > 0) {
            for (auto i = romans.begin(); i != romans.end(); ++ i) {
                auto find = s.find(i->first);
                if (find == 0) { // starts with
                    r += i->second;
                    s = s.substr(find + i->first.size()); // jump over the prefix
                    break;
                }
            }
        }
        return r;
    }
};

However, this approach is slower than the first one, as the string::find method in C++ has complexity of O(NM) where N and M are the sizes of two strings respectively.

To convert the Arabic Integers to Roman Numerals, we can use: How to Convert Arabic Integers to Roman Numerals?

Here is an online Romans to Arabic Converter with API: Roman Numerals to Arabic Integers Converter with API

–EOF (The Ultimate Computing & Technology Blog) —