# C++, O(n) with two bool signs and one stack

• Use one bool "sign" to get the operator before current number;
use another bool "presign" to trace the actual operator of the nearest "(" before current number;
(actual operator means transfer operator inside "( )" into global by virtually "removing" outer parenthesis)

If sign and presign are the same, means "+" and "+", or "-" and "-", so add it to result
else reduce it from result.

For multiple layers parenthesis, use a stack as a buffer to recognize corresponding layer.

``````class Solution {
public:
int calculate(string s)
{
int len = s.length();
int sum = 0;
bool presign = true, sign = true;
stack<int> stk;

for(int ii=0; ii<len; ++ii)
{
char cc = s[ii];

if(' ' == cc)
continue;
if('+' == cc)
sign = true;
else if('-' == cc)
sign = false;
else if('(' == cc)
{
stk.push(presign);
presign = (true == sign)?presign:(!presign);
sign = true;
}
else if(')' == cc)
{
presign = stk.top();
stk.pop();
sign = true;
}
else
{
int num = s[ii] - '0';
while(isdigit(s[++ii]))
num = 10*num + s[ii] - '0';
ii--;

sum += (sign==presign)? num : (0-num);
}
}
return sum;
}
};``````

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