Share my C++ solution using Stack


  • 4
    D
    public:
        int romanToInt(string s) 
    	{
    		// Init result var
    		int result = 0;
    		// Record prev value -- this stack will getting poped when meeting the largest value and then decrease
    		stack<int> prevResults;
    
    		// Iterate every element in s
    		for(size_t i=0; i<s.length(); i++)
    		{
    			// If queue is empty
    			if(prevResults.empty())
    				prevResults.push(this->getCurrentNum(s[i]));
    			else
    			{
    				if(this->getCurrentNum(s[i]) <= prevResults.top())
    				{
    					// Process first element
    					result += prevResults.top();
    					// Pop element
    					prevResults.pop();
    
    					while(! prevResults.empty())
    					{
    						result -= prevResults.top();
    						prevResults.pop();
    					}
    					// Push to the results
    					prevResults.push(this->getCurrentNum(s[i]));
    				}
    				else
    				{
    					result += this->getCurrentNum(s[i]);
    
    					// Poping elements
    					while(! prevResults.empty())
    					{
    						result -= prevResults.top();
    						prevResults.pop();
    					}
    				}
    			}
    		}
    
    		// Finally pop all elements and add to the number
    		while(! prevResults.empty())
    		{
    			result += prevResults.top();
    			prevResults.pop();
    		}
    
    		return result;
        }
    private:
    	int getCurrentNum(char ch)
    	{
    		switch(ch)
    		{
    			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;
    		}
    
    		return 0;
    	}

  • 0
    C
    This post is deleted!

  • 0
    S

    Thanks for your post. However it would be better to share solution with correct code format and elaborated thoughts. Please read the Discuss FAQ for more info. Take a look at good sharing example

    Pay attention to "Writing code? Select all code then click on the {} button to preserve code formatting.” above text editor.


  • 2
    T

    It is much cleaner code using stack. I really enjoy your method and thanks for sharing. Post my python code as well.

    def romanToInt(self, s):
        m={'M':1000, 'D':500, 'C':100, 'L':50, 'X':10, 'V':5, 'I':1}
        stack=[0]
        for c in s[::-1]:
            if m[c]>=stack[-1]:
                stack.append(m[c])
            else:
                v=stack.pop()
                stack.append(v-m[c])
        return sum(stack)

  • 0
    D

    Great! Thanks for sharing.


  • 0
    D

    My 2nd revision of C++ solution. I used a lookup table to enumerate all smallest and valid patterns. They are either 1 letter or 2 letters.

    Then iterate through the string, try to match with 2 letters, then 1 letter. It will also skip invalid letters.

    class Solution {
    public:
        int romanToInt(string s) {
            
            std::map<string, int> values = {        
                                                {"I",1},
                                                {"IV", 4},
                                                {"IX", 9},
                                                {"V",5},
                                                {"X",10},
                                                {"XL",40},
                                                {"XC",90},
                                                {"L",50},
                                                {"C",100},
                                                {"CD",400},
                                                {"CM",900},
                                                {"D",500},
                                                {"M",1000},
                                           };
            
            int result = 0;
            
            //parse the string
            for( int i = 0; i < s.size(); i++)
            {
                // match from two letter patterns
                if (values.count(s.substr(i, 2)))
                        {result += values[s.substr(i, 2)];
                            i = i + 1;
                        }
                // then match from one letter pattern
                else if (values.count(s.substr(i, 1)))
                        result += values[s.substr(i, 1)];
            } 
    
            
            return result;
            
        }
    };
    

  • 1
    W

    I think you can use a variable to store the temperate max bit, then the stack can be omitted. Here is my code in C++.

    int romanToInt(string s) {
    	int m[26]={0,0,100,500,0,0,0,0,1,0,0,50,1000,0,0,0,0,0,0,0,0,5,0,10,0,0};
    
    	int result = 0, vmax = 0;
    	for (int i=s.size()-1;i>=0;i--){
    		int t = m[s[i]-'A'];
    		if (t >= vmax){
    			result += t;
    			vmax = t;
    		}else{
    			result -= t;
    		}
    	}
    	return result;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.