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

• 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;
}
};``````

• brilliant solution!

• 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;
}
};
``````

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