class Solution {
public:
    enum Roman{
        I, V, X, L, C, D, M
    };
    
    int romanToInt(Roman n) {
        switch (n) {
            case I: return 1;
            case V: return 5;
            case X: return 10;
            case L: return 50;
            case C: return 100;
            case D: return 500;
            case M: return 1000;
            default: return 0;
        }
    }
    
    vector<Roman> strToRoman(string s) {
        vector<Roman> v;
        
        for (int i = 0; i < s.length(); i++) {
            switch(s[i]) {
                case 'I': v.push_back(I); break;
                case 'V': v.push_back(V); break;
                case 'X': v.push_back(X); break;
                case 'L': v.push_back(L); break;
                case 'C': v.push_back(C); break;
                case 'D': v.push_back(D); break;
                case 'M': v.push_back(M); break;
                default: break;
            }
        }
        
        return v;
    }
    
    int romanToInt(string s) {
        if (s.empty()) return 0;
        
        vector<Roman> num = strToRoman(s);
        
        int res = 0;
        int left = 0, right = 0;
        while (left < num.size() && right < num.size()) {
            while (right < num.size() && num[right] < num[right + 1]) ++right;
            
            int part_res = romanToInt(num[right]);
            for (int i = right - 1; i >= left; i--) {
                part_res -= romanToInt(num[i]);
            }
            
            res += part_res;
            left = right + 1;
            ++right;
        }
        
        return res;
    }
};