Why my method c++ got Time Limit Exceeded


  • 0

    i think the string only include "+-()" so the "()" do nothing. when calculator can can ignore the "()"
    but why my method got Time Limit Exceeded

    int findNum(string s, int index, int* pos)
    {
    	int num = 0;
    
    	while (!('0' <= s[index] && s[index] <= '9'))
    	{
    		index++;
    	}
    
    	for (; index < s.size(); ++index)
    	{
    		if (!('0' <= s[index] && s[index] <= '9'))
    			break;
    
    		num = num * 10 + (s[index] - '0');
    	}
    
    	*pos = index;
    
    	return num;
    }
    
    int calculate(string s) 
    {
    	int size  = s.size();
    	int index = 0;
    	int res   = findNum(s, 0, &index);
    
    	int pos;
    	int num;
    
    	while (index < size)
    	{
    		if (' ' == s[index] || '(' == s[index] || ')' == s[index])
    		{
    			index++;
    			continue;
    		}
    
    		num = findNum(s, index + 1, &pos);
    
    		if ('+' == s[index])
    		{
    			res += num;
    		}
    		else if ('-' == s[index])
    		{
    			res -= num;
    		}
    
    		index = pos;
    	}
    
    	return res;
    }

  • 0

    my bad the "()" can change the sign, like:4-(5-6) equals 4-5+6 not the same as 4--5-6
    so my method:

    int calculate(string s) 
    {
    	stack<int> sta;
    	sta.push(1);
    
    	int sign = 1;
    	int res  = 0;
    	int num  = 0;
    	char c;
    
    	int size = s.size();
    	int index = 0;
    	
    	while (index < size)
    	{
    		c = s[index++];
    
    		if ('(' == c)
    		{
    			sta.push(sta.top() * sign);
    			sign = 1;
    		}
    		else if (')' == c)
    		{
    			res += sta.top() * sign * num;
    			num = 0;
    
    			sta.pop();
    		}
    		else if ('+' == c || '-' == c)
    		{
    			res += sta.top() * sign * num;
    			num = 0;
    
    			sign = ('+' == c) ? 1 : -1;
    		}
    		else if ('0' <= c && c <= '9')
    		{
    			num = num * 10 + c - '0';
    		}
    	}
    
    	res += sta.top() * sign * num;
    
    	return res;
    }

Log in to reply
 

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