24-line C++ O(n) Recursive Solution, 20ms and Intuitive


  • 19
    L

    Each invocation of evaluate() evaluates whatever inside a pair of parenthese. Nested parenthese will be handled by recursive calls.

    So "(1+(4+5+2)-3)+(6+8)"

    ->

    (1+(9+2)-3)+(6+8)

    ->

    (1+11-3)+(6+8)

    ->

    (12-3)+(6+8)

    ->

    9+(6+8)

    ->

    9+14

    ->

    23

    class Solution {
    public:
        int calculate(string s) {
            int pos=0;
            return evaluate(s,pos);
        }
        
        int evaluate(string& s, int& i) {
            int res = 0;
            bool negFlag=false;
            while(i<s.size()&&s[i]!=')') {
                if(s[i]=='+'||s[i]==' ') 
                    i++;
                else if(s[i]=='-') {
                    i++;
                    negFlag=true;
                }
                else if(s[i]=='(') {
                    i++;
                    res+=negFlag?-evaluate(s,i):evaluate(s,i);
                    negFlag=false;
                }
                else {// numeric chars
                    int num=0;
                    while(i<s.size()&&isdigit(s[i]))
                        num = num*10 + s[i++]-'0';
                    res+=negFlag?-num:num;
                    negFlag=false;
                }
            }
            i++; // skip the current ')'
            return res;
        }
    };

  • 0
    D

    brilliant solution!


  • 0

    Great solution! Recursion is always easier to code.
    Here's an alternative version.

    #include <cctype>
    class Solution {
    public:
        int calculate(string s) {
            int i = 0, N = s.size();
            return dfs(s, i, N);
        }
        
        int dfs(const string& s, int& i, const int& N){
            int res = 0, sign = 1, num = 0;
            while(i < N && s[i] != ')'){
                if(isdigit(s[i]))
                    num = num * 10 + (s[i] - '0');
                else{
                    res += sign * num;
                    num = 0;
                    if(s[i] == '+') sign = 1;
                    else if(s[i] == '-') sign = -1;
                    else if(s[i] == '('){
                        i++;
                        res = res + sign * dfs(s, i, N);
                    }
                }
                i++;
            }
            return res + sign * num;
        }
    };
    

Log in to reply
 

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