Simple c++ in 24 ms


  • 39
    I
    class Solution {
    public:
        int calculate(string s) {
            // the given expression is always valid!!!
            // only + and - !!!
            // every + and - can be flipped base on it's depth in ().
            stack<int> signs;
            int sign = 1;
            int num = 0;
            int ans = 0;
            
            // always transform s into ( s )
            signs.push(1);
            
            for (auto c : s) {
                if (c >= '0' && c <= '9') {
                    num = 10 * num + c - '0';
                } else if (c == '+' || c == '-') {
                    ans = ans + signs.top() * sign * num;
                    num = 0;
                    sign = (c == '+' ? 1 : -1);
                } else if (c == '(') {
                    signs.push(sign * signs.top());
                    sign = 1;
                } else if (c == ')') {
                    ans = ans + signs.top() * sign * num;
                    num = 0;
                    signs.pop();
                    sign = 1;
                }
            }
            
            if (num) {
                ans = ans + signs.top() * sign * num;
            }
            
            return ans;
        }
    };

  • -1
    N
    This post is deleted!

  • 0
    K
    This post is deleted!

  • 0
    Z
    This post is deleted!

  • 0

    Please use only English in Discuss, thanks.


  • 0

    Please use only English in Discuss, thanks.


  • 0
    C

    Thanks for sharing! A little shorter one.

    class Solution {
    public:
        int calculate(string s) {
            stack<int> calcst;
            calcst.push(1);
            s += ')';
            int sign = 1, num = 0, i = 0, ans = 0;
            for (i = 0; i < s.size(); i++){
                if (s[i] >= '0' && s[i] <= '9'){
                    num = num * 10 + s[i] - '0';
                }else if (s[i] == '+' || s[i] == '-' || s[i] == ')'){
                    ans += calcst.top() * sign * num;
                    if (s[i] == ')') calcst.pop();
                    sign = s[i] == '-' ? -1 : 1;
                    num = 0;
                }else if (s[i] == '('){
                    calcst.push(calcst.top() * sign);
                    sign = 1;
                }
            }
            return ans;
        }
    };

  • 0
    J

    Hi Chuang, this is wizardry algorithm! Could you enlighten us how did you reach this solution?


  • 24
    M

    Thanks for chuang's answer. Make a version which is easy to understand.
    Example: 7 - ( 6 - 5 - ( 4 - 3 ) - 2 ) - ( 1 )
    Result: + 7 - 6 + 5 + 4 - 3 + 2 - 1
    The + - are signs just before '('. They are dealt with previous stack sign. Then they are saved in the stack to help decide the signs in the following "(..)" .

    class Solution {
    public:
        int calculate(string s) {
            stack<int> t;  //previous sign just before the '('
            t.push(1);  //for all the signs those are not in the parentheses
            int sum=0, temp=0, lastSign=1;
            for(auto c: s)
            {
                if(c=='(') t.push(lastSign); //save the sign just before the '('
                else if(c==')') t.pop();
                
                if(c>='0' && c<='9'){  
                    temp=temp*10+c-'0';
                }
                
                if(c=='-'||c=='+'){
                    sum+=lastSign*temp; //calculate the number before current sign
                    temp=0;
                    lastSign=(c=='-'?-1:1)*t.top();  //deal with the stack influencing sign
                }
            }
            sum+=lastSign*temp; //calculate the last number
            return sum;
        }
    };
    

  • 0
    E

    If the given expression is always valid:

    I: sign = 1 in c == '(' condition is redundant.

    II: in the last if statement:
    ans = ans + signs.top() * sign * num, the signs.top() here is redundant.

    Am I right?


Log in to reply
 

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