iterative and no need to store previous result in stack


  • 1
    Z

    I used two variables to determine sign, one is universal sign and the other one is temporary sign before number or parenthesis. And then used a stack to store universal sign out of current parenthesis.
    Here is C++ code:

    int calculate(string s) {
            int sign = 1;
            int temp = 1;
            stack<int> stk;
            int result = 0;
            int index = 0;
            while(index < s.size())
            {
                while(index < s.size() && s[index]  == ' ') index++;
                if(index >= s.size())
                    break;
                if(s[index] == '-')
                    temp = -1;
                else if(s[index] == '(')
                {
                    stk.push(sign);
                    sign *= temp;
                    temp = 1;
                }
                else if(s[index] == ')')
                {
                    sign = stk.top();
                    temp =1;
                    stk.pop();
                }
                else if(s[index] >= '0' && s[index] <= '9')
                {
                    int cur = 0;
                    while(index < s.size() && s[index] >= '0' && s[index] <= '9')
                        cur = 10*cur + (s[index++]-'0');
                    result += sign*temp*cur;
                    temp = 1;
                    index--;
                }
                index++;
            }
            return result;
        }
    

Log in to reply
 

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