36 ms C++ solution


  • 0
    int calculate(string s)  //"+-" should paired with integer, 3->'+3'; 1-2->'+1' + '-2'; 1-(2+3)->'+1' + '- ( '+2' + '+3' )'
    {
    	if (!s.size())
    		return 0;
    	int sz = s.size();
    	stack<int> st; //create a stack to record integer. 
    	stack<char> op; //record "+-("
    	op.push('+'); //3 -> '+3'
    	int i, sign, num = 0;
    	int n, sum;
    	for (i = 0; i < sz; ++i)
    	{
    		if (' ' == s[i])
    			continue;
    		else if (s[i] >= '0' && s[i] <= '9')
    		{
    			num = 10 * num + s[i] - '0'; //calculate the integer
    			if (i + 1 >= sz || s[i + 1] < '0' || s[i + 1] > '9')
    			{
    				st.push(num);
    				num = 0;
    			}
    		}
    		else if ('+' == s[i] || '-' == s[i])
    			op.push(s[i]);
    		else if ('(' == s[i])
    		{
    			op.push('(');
    			op.push('+'); //2 - (3) -> '2' + '- ('+3')'
    		}
    		else if (')' == s[i]) //pop and calculate the integer which in the ranger of "( )"
    		{
    			sum = 0;
    			while ('(' != op.top())
    			{
    				n = st.top();
    				st.pop();
    				if ('+' == op.top())
    					sign = 1;
    				else if ('-' == op.top())
    					sign = -1;
    				op.pop();
    				sum += sign*n;
    			}
    			op.pop(); //pop '('
    			st.push(sum);
    		}
    	}
    	// step 2
    	sum = 0;
    	while (!st.empty())
    	{
    		n = st.top();
    		st.pop();
    		if ('+' == op.top())
    			sign = 1;
    		else if ('-' == op.top())
    			sign = -1;
    		op.pop();
    		sum += n*sign;
    	}
    	return sum;
    }

  • 0
    C

    what will happen if the input string is (-1-1)


  • 0

    The problem has cleared 'non-negative integers and empty spaces', that means you can not start the string with '-'


Log in to reply
 

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