# Simple c++ in 24 ms

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

• This post is deleted!

• This post is deleted!

• This post is deleted!

• Please use only English in Discuss, thanks.

• Please use only English in Discuss, thanks.

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

• Hi Chuang, this is wizardry algorithm! Could you enlighten us how did you reach this solution?

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

• If the given expression is always valid:

I: sign = 1 in c == '(' condition is redundant.

II: in the last if statement:
ans = ans + signs.top() * sign * num, the signs.top() here is redundant.

Am I right?

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