20ms, O(n) time, O(1) space, one scan C++ solution


  • 17
    X

    O(n) time, O(1) space, one scan C++ solution, code maybe optimized though. Every time I got a number, I will aggregate it into the temp result. when I met '+' or '-", temp result will be aggregated into the final result sum.

     int calculate(string s) {
        int sum = 0; 
        if(s.size() < 1) return sum; 
        int i = 0; 
        int last = 0, last_result = 1;  
        char last_operator = '+'; //remember the last operator
        int sign = 1; 
        while(i < s.size()){
            if(s[i] == ' '){++i; continue;}
            if(s[i] == '+' || s[i] == '-'){
                sum += last_result * sign;
                sign = s[i++] == '+' ? 1 : -1; 
                last_result = 1;
                last_operator = '+'; 
            }
            else if(s[i] == '/' || s[i] == '*'){
                last_operator = s[i];
                ++i; 
            }
            if(isdigit(s[i])){
                last = 0; 
                while(i < s.size() && isdigit(s[i])){
                    last =  last * 10 + s[i++] - '0'; 
                }
                
                if(last_operator == '*') last_result *= last;
                else if(last_operator == '/') last_result /= last;
                else  last_result = last; 
            }
        }
        sum += last_result * sign;
        return sum; 
    }

  • 0

    Nice idea to give an O(1)-space solution.


  • 0
    B

    great idea to compute each subexpression with the last_result, and then add last_result to sum when we meet + and -.


  • 0
    Z

    Very nice idea and implementation. Add my understanding as comments in the code. Also delete the line "sum += last_result * sign;" after the while loop by appending '+' to the end of s. But the string push back increases the worst-case space complexity to O(n).

    class Solution 
    {
    public:
        int calculate(string s) 
        {
            // Append '+' to the end of the input string so that we don't need 
            // take an extra step after the while loop, e.g., s = "1 + 2 * 3". Note 
            // that depending on the current capacity of the string s, this push 
            // back may allocate a new string with the original length plus 1 and 
            // thus increases the space complexity to O(n).
            s.push_back('+');
            
            // This is the final result.
            int res = 0;
            // This is the partial result previous to the current '+' or '-' 
            // operator. It is the result of the subexpression which doesn't 
            // contain any '+' or '-' operators. In particular, if the previous 
            // operator is '+' or '-', it is just the previous number.
            int prevRes = 0;
            int currNum = 0;
            char prevOperator = '+';
            // This is the sign of the most recent '+' or '-' operator.
            int prevOperatorSign = 1;
            
            int i = 0;
            while (i < s.length())
            {
                if (s[i] == ' ')
                {
                    // Ignore the space.
                    i++;
                }
                else if ((s[i] == '+') || (s[i] == '-'))
                {
                    // Add or substract prevRes to/from res, depending on 
                    // prevOperatorSign.
                    res += (prevOperatorSign*prevRes);
                    
                    // Update prevOperator and prevOperatorSign.
                    prevOperator = s[i];
                    prevOperatorSign = (s[i] == '+') ? 1 : -1;
                    i++;
                }
                else if ((s[i] == '*') || (s[i] == '/'))
                {
                    // Update prevOperator only.
                    prevOperator = s[i];
                    i++;
                }
                else
                {
                    // Get the current number.
                    currNum = s[i] - '0';
                    i++;
                    while ((s[i] >= '0') && (s[i] <= '9'))
                    {
                        currNum = 10*currNum + (s[i] - '0');
                        i++;
                    }
                    
                    // If the operator before the current number is '*' or 
                    // '/', continue calculating the result of the subexpression 
                    // which doesn't contain any '+' or '-' operators. Otherwise, 
                    // reset prevRes to currNum.
                    if (prevOperator == '*')
                    {
                        prevRes *= currNum;
                    }
                    else if (prevOperator == '/')
                    {
                        prevRes /= currNum;
                    }
                    else
                    {
                        prevRes = currNum;
                    }
                }
            }
            
            return res;
        }
    };

  • 0

    I think that the s.push_back('+'); makes it an O(n) space algorithm, though.


  • 0
    Z

    I am not sure. string::push_back only increases the string length by 1. May I ask why it will introduce an extra O(n) space?


  • 1
    X

    Thanks zhukov. I think you don't need to add extra '+'. Just modify the code a bit by extending the boarder checking.

    int calculate(string s) {
        int sum = 0; 
        if(s.size() < 1) return sum; 
        int i = 0; 
        int last = 0, last_result = 1;  
        char last_operator = '+'; //remember the last operator
        int sign = 1; 
        while(i <= s.size()){
            if(s[i] == ' '){++i; continue;}
            if(s[i] == '+' || s[i] == '-' || !s[i]){ //Check the end of the string
                sum += last_result * sign;
                sign = s[i++] == '+' ? 1 : -1; 
                last_result = 1;
                last_operator = '+'; 
            }
            else if(s[i] == '/' || s[i] == '*'){
                last_operator = s[i];
                ++i; 
            }
            if(isdigit(s[i])){
                last = 0; 
                while(i < s.size() && isdigit(s[i])){
                    last =  last * 10 + s[i++] - '0'; 
                }
    
                if(last_operator == '*') last_result *= last;
                else if(last_operator == '/') last_result /= last;
                else  last_result = last; 
            }
        }
        return sum; 
    }

  • 1

    I think strings are, at least typically, stored in consecutive memory places. So you can't just always extend the string in place. The string object might have allocated extra capacity in addition to the original string length, but at some point even that capacity is fully used and then to extend the string, it'll have to allocate new memory somewhere else to hold the entire extended string. See this, for example.


  • 0
    Z

    Nice! The worst-case space complexity of your implementation will be O(1). Thank you for sharing it.


  • 0
    Z

    Makes sense. Thank you very much for the detailed explanation. I have updated my post.


  • 0
    Q

    Nice solution.


  • 0
    Y

    nice solution, though last_result = 1 is not necessary.


Log in to reply
 

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