C++ use stack to store sign, O(n) time


  • 0
    L

    I use a stack (signs) to store the sign before the "(", after encounter a ")" the latest sign will be popped out.
    When encounter a sign, the result will immediately calculate the current state.
    The idea is to remove the "( )" one layer by one layer and change the sign inside the "( )" .

    class Solution {

    public:

    int calculate(string s) {

    vector<int> signs;
    int result = 0; 
    int sign = 1;
    int num = 0;
    signs.push_back(1);
    for (int iter = 0; iter< s.length(); iter++){
    	if (s[iter] == ' '){
    		continue;
    	}
    	if (s[iter]>='0' && s[iter]<='9'){
    	    num = num*10+s[iter]-'0';
    	    continue;
    	}
    	if (s[iter] == ')'){
    		result = result+num*sign*signs.back();
    		num=0;
    		signs.pop_back();
    		continue;
    		}
        if (s[iter] == '+'){
            result = result+num*sign*signs.back();
            sign = 1;
            num = 0;
            continue;
    		}
    	if (s[iter] == '-'){
            result = result+num*sign*signs.back();
            sign = -1;
            num = 0;
            continue;
    	}
    	if (s[iter] == '('){
    	   result = result+num*sign*signs.back();
    	   signs.push_back(sign*signs.back());
    	   sign = 1;
    	   num = 0;
    	   continue;
    	}
    
    }
    result = result+num*sign*signs.back();
    return result;
    }
    

    };


Log in to reply
 

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