# 16 ms solution in C++ with stacks

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

• I think the if-condition "(c == ')' && ops.size())" can be rewritten as "if (c == ')')". If the input string is legal expression, then we can always see the '(' before meeting the ')', thus the stack is impossibly empty.

• yes, it says "You may assume that the given expression is always valid."

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

• It may not work for the case 5 + ((6))
i.e., in the case of double brackets ???

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