16 ms solution in C++ with stacks


  • 67
    D
    class Solution {
    public:
        int calculate(string s) {
            stack <int> nums, ops;
            int num = 0;
            int rst = 0;
            int sign = 1;
            for (char c : s) { 
                if (isdigit(c)) {
                    num = num * 10 + c - '0';
                }
                else {
                    rst += sign * num;
                    num = 0;
                    if (c == '+') sign = 1;
                    if (c == '-') sign = -1;
                    if (c == '(') {
                        nums.push(rst);
                        ops.push(sign);
                        rst = 0;
                        sign = 1;
                    }
                    if (c == ')' && ops.size()) {
                        rst = ops.top() * rst + nums.top();
                        ops.pop(); nums.pop();
                    }
                }
            }
            rst += sign * num;
            return rst;
        }
    };

  • 0
    W

    I think the if-condition "(c == ')' && ops.size())" can be rewritten as "if (c == ')')". If the input string is legal expression, then we can always see the '(' before meeting the ')', thus the stack is impossibly empty.


  • 0
    F

    yes, it says "You may assume that the given expression is always valid."


  • 5
    B

    I took long time to figure it out and here is my explanation on some steps. Hope it is helpful.

    class Solution {
    public:
        int calculate(string s) {
            int result=0; 
            int num=0, sign=1; 
            stack<int> nums, ops; 
            
            for(int i=0; i<s.size(); ++i){
                char c=s[i];
                if(c>='0' && c<='9'){
                    num=10*num + c-'0'; /// For case: "23" 
                }else if(c=='+'){
                    result+=num*sign; /// everytime meets an operator, sum up previous number
                    num=0;
                    sign=1;    /// sign is the sign of next number
                }else if(c=='-'){
                    result+=num*sign; /// everytime meets an operator, sum up previous number
                    num=0; 
                    sign=-1; 
                }else if(c=='('){
                    nums.push(result); /// ...(1+3+(..xx..)+...)... before go into cur (..xx..), record the forefront result (in this case it is 1+3 ) into nums array    
                    ops.push(sign);  // record cur (..xx..) sign
                    result=0;  // result is to record the total value in the cur (..xx..)
                    sign=1;
                }else if(c==')' && ops.size()){ 
                    result+=num*sign; /// For case: 1-(5)
                    num=0;
                    
                    result = result*ops.top() + nums.top();  // ...(1+3+(..xx..)+...)... sum up cur (..xx..)  and the forefront result (in this case it is 1+3 )
                    nums.pop();
                    ops.pop();
                }
            }
            result+=num*sign; /// For the last one operation. consider the case:  1+2+3 
            return result; 
        }
    };
    

  • 0
    R

    It may not work for the case 5 + ((6))
    i.e., in the case of double brackets ???


Log in to reply
 

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