64 ms c++ easy solution


  • 21
    V
    class Solution {
    public:
        int calculate(string s) {
            int n = s.size();
            stack<int> s1;
            stack<char> s2;
            string v;
            for(int i = n - 1; i >= 0; i--){
                if(s[i] == ')' || s[i] == '+' || s[i] == '-') s2.push(s[i]);
                else if(s[i] >= '0' && s[i] <= '9'){
                    v = s[i] + v;
                    if(i == 0 || s[i - 1] < '0' || s[i - 1] > '9'){
                        s1.push(stoi(v)); 
                        v = "";
                    }
                } else if(s[i] == '('){
                    while(s2.top() != ')') cal(s1, s2);
                    s2.pop();
                }
            }
            while(!s2.empty()) cal(s1, s2);
            return s1.top();
        }
    
        void cal(stack<int> &s1, stack<char> &s2){
            int v1 = s1.top(); s1.pop();
            int v2 = s1.top(); s1.pop();
            char c = s2.top(); s2.pop();
            if(c == '+') s1.push(v1 + v2);
            if(c == '-') s1.push(v1 - v2);
        }
    };

  • 3

    Nice handling of the parentheses! I have understood your code. It is really helpful.

    Your code is nice and I have reorganized it a little bit for better readability. Hope it is OK :)

    int calculate(string s) {
        stack<int> operands;
        stack<char> operations;
        string operand;
        for (int i = (int)s.length() - 1; i >= 0; i--) {
            if (s[i] == ')' || s[i] == '+' || s[i] == '-')
                operations.push(s[i]);
            else if (isdigit(s[i])) {
                operand = s[i] + operand;
                if (!i || !isdigit(s[i - 1])) {
                    operands.push(stoi(operand));
                    operand.clear();
                }
            }
            else if (s[i] == '(') {
                while (operations.top() != ')')
                    compute(operands, operations);
                operations.pop();
            }
        }
        while (!operations.empty())
            compute(operands, operations);
        return operands.top();
    }
    
    void compute(stack<int>& operands, stack<char>& operations) {
        int left = operands.top();
        operands.pop();
        int right = operands.top();
        operands.pop();
        int op = operations.top();
        operations.pop();
        if (op == '+') operands.push(left + right);
        if (op == '-') operands.push(left - right);
    } 
    

  • 0
    V

    Thank you ! :-)


  • 0
    A

    Nice code. Easy for understand. reverse loading is important.


  • -2
    A

    Follow your code to write a java version 500 ms

       public static int calculate(String s) {
            int n = s.length();
            Stack<Integer> s1 = new Stack();
            Stack<Character> s2 = new Stack();
            StringBuilder v = new StringBuilder();
            for(int i = n - 1; i >= 0; i--){
            	char tempChar = s.charAt(i);
                if(tempChar == ')' || tempChar == '+' ||tempChar == '-') s2.push(tempChar); // treat three opt
                else if(tempChar >= '0' && tempChar <= '9'){
                	v = v.insert(0, tempChar);
                	if(i == 0 || s.charAt(i-1) < '0' || s.charAt(i-1) > '9'){
                		s1.push(Integer.parseInt(v.toString())); 
                		v =  new StringBuilder();
                    }
                }
                else if(tempChar == '('){
                    while(s2.peek() != ')') cal(s1, s2);
                    s2.pop();
                }
            }
            while(!s2.isEmpty()) cal(s1, s2);
            return s1.pop();
        }
        
        static void cal(Stack<Integer> s1, Stack<Character> s2){
        	int v1 = s1.pop();
        	int v2 = s1.pop();
        	char c = s2.pop();
        	if(c == '+') s1.push(v1 + v2);
        	if(c == '-') s1.push(v1 - v2);
        }

  • 0

    I have reformatted your code so it is easier to read. The code looks nice, could you add one or two sentences about the thoughts that lead you to this elegant solution?


  • 0
    V

    very nice!!!!


  • 0
    C

    Nice solution, but I don't get why you have to run from right to left. It is exactly the same with running from left to right (but you push to s2 '(' instead of ')' ). In fact, in running from right to left the step v = s[i] + v is even more expensive than v = v + s[i] if you run from left to right.


  • 0
    E

    Nice solution with stack. Here is my solution without station, 20ms. Could be better written though... recursively call a function return a solid result after evaluating what is inside a parenthesis.

    // Here is the code

    int calInsideParen(string& s, int& idx) {
    
        idx++;
        
        int ans = 0;
        int sign = 1;
        int tmp = 0;
        
        while( idx != s.length() ) {
            if( s[idx] == ' ' ) { idx++; continue; }
            if( s[idx] == '(' ) {
                ans += sign*calInsideParen( s, idx );
            }
            if( s[idx] == ')' ) { idx++; ans += sign * tmp; return ans; }
            if( s[idx] == '+' ) { ans += sign * tmp; tmp = 0; sign = 1; idx++; continue; }
            if( s[idx] == '-' ) { ans += sign * tmp; tmp = 0; sign = -1; idx++; continue; }
            if( s[idx]-'0' >= 0 && s[idx]-'0' <= 9 ) {
                if( idx == 0 ) {
                    tmp = (int)(s[idx]-'0');
                }
                else {
                    if( s[idx-1]-'0' >=0 && s[idx-1]-'9' <=9 ) {
                        tmp = tmp*10;
                        tmp += (int)(s[idx]-'0');
                    }
                    else {
                        tmp = (int)(s[idx]-'0');
                    }
                }
                
                idx++;
            }
        }
        
        
        abort();
    }
    
    int calculate(string s) {
        int ans = 0;
        int idx = 0;
        int sign = 1;
        
        int tmp = 0;
        
        while( idx != s.length() ) {
            if( s[idx] == ' ' ) { idx++; continue; }
            if( s[idx] == '(' ) {
                ans += sign*calInsideParen( s, idx );
            }
            if( s[idx] == ')' ) { abort(); }
            if( s[idx] == '+' ) { ans += sign * tmp; tmp = 0; sign = 1; idx++; continue; }
            if( s[idx] == '-' ) { ans += sign * tmp; tmp = 0; sign = -1; idx++; continue; }
            if( s[idx]-'0' >= 0 && s[idx]-'0' <= 9 ) {
                if( idx == 0 ) {
                    tmp = (int)(s[idx]-'0');
                }
                else {
                    if( s[idx-1]-'0' >=0 && s[idx-1]-'9' <=9 ) {
                        tmp = tmp*10;
                        tmp += (int)(s[idx]-'0');
                    }
                    else {
                        tmp = (int)(s[idx]-'0');
                    }
                }
                
                idx++;
            }
        }
        ans += sign * tmp;
        
        return ans;
    }

  • 0
    Q

    Hello, I have similar style using two stacks but easy to understand( I think...)

    But without reverse the input, that is run from left to right.

    A little bit long..

    class Solution {
    public:
    	int calculate(string s) {
    		stack<int> operands;
    		stack<char> operators;
    		for (int i = 0, len = s.size(); i<len; i++){
    			if (s[i] == ' ')  continue;
    			if (s[i] >= '0' && s[i] <= '9'){
    				int val = s[i]-'0';
    				while (i + 1 < len && s[i+1] >= '0' && s[i+1] <= '9'){
    					val = val * 10 + s[i + 1]-'0';
    					i++;
    				}
    				operands.push(val);
    			}
    			else{
    				if (operators.empty() || s[i] == '(')
    					operators.push(s[i]);
    				else{
    					if (operators.top() != '(')
    						calcUtil(operands, operators);
    					if (s[i] == ')')
    						operators.pop();
    					else
    						operators.push(s[i]);
    				}
    			}
    		}
    
    		while (operands.size()>1)
    			calcUtil(operands, operators);
    		return operands.top();
    	}
    	void calcUtil(stack<int> &operands, stack<char> &operators){
    		int operand2 = operands.top();
    		operands.pop();
    		int operand1 = operands.top();
    		operands.pop();
    		int tmp = (operators.top() == '+') ? operand1 + operand2 : operand1 - operand2;
    		operands.push(tmp);
    		operators.pop();
    	}
    };

Log in to reply
 

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