C++, O(n) with two bool signs and one stack


  • 3
    D

    Use one bool "sign" to get the operator before current number;
    use another bool "presign" to trace the actual operator of the nearest "(" before current number;
    (actual operator means transfer operator inside "( )" into global by virtually "removing" outer parenthesis)

    If sign and presign are the same, means "+" and "+", or "-" and "-", so add it to result
    else reduce it from result.

    For multiple layers parenthesis, use a stack as a buffer to recognize corresponding layer.

    class Solution {
    public:
    	int calculate(string s)
    	{
        	int len = s.length();
        	int sum = 0;
        	bool presign = true, sign = true;
        	stack<int> stk;
        	
        	for(int ii=0; ii<len; ++ii)
        	{
        		char cc = s[ii];
        		
        		if(' ' == cc)
        			continue;
        		if('+' == cc)
        			sign = true;
        		else if('-' == cc)
        			sign = false;
        		else if('(' == cc)
        		{
        			stk.push(presign);
        			presign = (true == sign)?presign:(!presign);
        			sign = true;
        		}
        		else if(')' == cc)
        		{
        			presign = stk.top();
        			stk.pop();
        			sign = true;
        		}
        		else
        		{
        			int num = s[ii] - '0';
        			while(isdigit(s[++ii]))
        				num = 10*num + s[ii] - '0';
        			ii--;	
    
        			sum += (sign==presign)? num : (0-num);
        		}
        	}
    		return sum;
    	}
    };

Log in to reply
 

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