class Solution {
public:
int calculate(string s) {
stack <int> nums, ops;
int num = 0;
int rst = 0;
int sign = 1;
for (char c : s) {
if (isdigit(c)) {
num = num * 10 + c  '0';
}
else {
rst += sign * num;
num = 0;
if (c == '+') sign = 1;
if (c == '') sign = 1;
if (c == '(') {
nums.push(rst);
ops.push(sign);
rst = 0;
sign = 1;
}
if (c == ')' && ops.size()) {
rst = ops.top() * rst + nums.top();
ops.pop(); nums.pop();
}
}
}
rst += sign * num;
return rst;
}
};
16 ms solution in C++ with stacks


I took long time to figure it out and here is my explanation on some steps. Hope it is helpful.
class Solution { public: int calculate(string s) { int result=0; int num=0, sign=1; stack<int> nums, ops; for(int i=0; i<s.size(); ++i){ char c=s[i]; if(c>='0' && c<='9'){ num=10*num + c'0'; /// For case: "23" }else if(c=='+'){ result+=num*sign; /// everytime meets an operator, sum up previous number num=0; sign=1; /// sign is the sign of next number }else if(c==''){ result+=num*sign; /// everytime meets an operator, sum up previous number num=0; sign=1; }else if(c=='('){ nums.push(result); /// ...(1+3+(..xx..)+...)... before go into cur (..xx..), record the forefront result (in this case it is 1+3 ) into nums array ops.push(sign); // record cur (..xx..) sign result=0; // result is to record the total value in the cur (..xx..) sign=1; }else if(c==')' && ops.size()){ result+=num*sign; /// For case: 1(5) num=0; result = result*ops.top() + nums.top(); // ...(1+3+(..xx..)+...)... sum up cur (..xx..) and the forefront result (in this case it is 1+3 ) nums.pop(); ops.pop(); } } result+=num*sign; /// For the last one operation. consider the case: 1+2+3 return result; } };