Since the input string is always valid, so what we truly need to concern about is that handling process and in this process only the sign is the essence; here so we are about to use a stack to store the signs before opening bracket which can change the signs inside brackets. Our rule is as follows:

- encountering digits, just collect them for calculation;
- encountering '+' or '-', check the stack for its sign before opening bracket and calculate and update the sign for next number;
- encountering '(', aha, its opening bracket, so we need to store the sign to stack and reset the current sign to '+' since we consider both sign and sign in stack to determine the sign and then calculate; still confused? okay, suppose "1-(5+3)" the minus will be converted to plus if we don't reset sign to plus here;
- encountering ')', delete the top sign in stack and then calculate;
- at last, after we traversing the string there might be some number left un-calculated, so we need to check it and calculate&&.

Done! End of story!

- Space cost O(n)
- Time cost O(n)

```
//AC - 4ms;
int calculate(char* s)
{
int* signs = (int*)malloc(sizeof(int)); //used to store the signs before opening bracket;
int top = -1;
signs[++top] = 1;
int sign = 1;
int num = 0;
int ret = 0; //used to store the result;
while(*s)
{
if(*s>='0' && *s<='9') //collect the number between non-digits;
{
num = 10*num + *s - '0';
}
else if(*s=='+' || *s=='-') //add the previous number and reset sign;
{
ret += signs[top]*sign*num;
num = 0;
sign = (*s=='+'? 1 : -1);
}
else if(*s == '(') //store the sign before opening bracket;
{
signs = (int*)realloc(signs, sizeof(int)*(top+2));
signs[top+1] = sign*signs[top]; //to avoid evaluation sequence problem, moving top++ to another statement;
top++;
sign = 1;
}
else if(*s == ')') //add the previous number and delete a sign for this pair of brackets;
{
ret += signs[top--]*sign*num;
num = 0;
}
s++;
}
if(num) //if there is still number left;
ret += signs[top]*sign*num;
return ret;
}
```