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;
}
};
Simple c++ in 24 ms


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

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 helpdecide 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; } };