题目：
Implement a basic calculator to evaluate a simple expression string.
The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces .
Example 1:
Input: "1 + 1" Output: 2
Example 2:
Input: " 2-1 + 2 " Output: 3
Example 3:
Input: "(1+(4+5+2)-3)+(6+8)" Output: 23
Note:
- You may assume that the given expression is always valid.
-
Do not use the
evalbuilt-in library function.
思路：
看到括号处理，第一时间想到的stack，能够做到括号之间的对应。首先因为无法判断括号内是否还有括号，所以每次遇到括号，我们需要把当前的结果和括号前的符号给存到stack里(如果第一个即使括号，则符号为正，因此我们初始化时默认符号是正号)，等到这个括号结束以后再进行运算。除了一个总答案ans，一个当前值cur，另一个变量是符号sign，这里我们用1表示正，-1表示负。显然对于string中的每一个字母，会有四种情况，因此我们分开讨论。
当前值为数字：因为数字可能是二位数或者三位数，所以首先把cur*10+当前数字大小。
当前值为字母即符号：首先如果遇到符号，说明前面肯定有ans，cur和sign需要完成一次计算，如"2-1+2"，读到'+'时，ans为2，sign为-1，cur为1，那么应该先进行2-1的操作再读取这个'+'，然后同时清空cur和sign，sign的值取决于符号的正负。这是一般情况，再回头看读到'-'时，ans为0，sign为1，默认初始的，cur为2，则先进行0+2然后读取'-'，同样更新cur和sign。
当前值为'('时，将当前ans和sign压入栈，顺序是先压ans，再压sign，因为到时候出栈时要把目前的数值cur先乘'('外的那个sign，再加上之前的ans。然后更新sign为1，因为'('之前的sign已经被压入栈了，所以这里sign又变成默认的1，cur为0。
当前值为')'时，一个括号结束，首先处理手中的值，将sign*cur加到ans上，然后从栈中拿出当前括号前压入的sign，乘当前的ans，即括号内的值，结果就是整个括号加上括号前的符号，然后再把栈上之前的值(ans)拿出来，与现在的ans相加即可。
最后需要ans再次加上当前的cur*sign，因为循环内我们设置的是遇到')'或者符号更新，如果结尾不是符号， 是自然的加减，那么就要加或减当前的值。
代码：
class Solution {
public:
int calculate(string s) {
stack<int> nums;
int sign = 1, cur = 0, ans = 0;
for (auto c : s)
{
if (c >= '0')
cur = cur * 10 + (c - '0');
else if (c == '+' || c == '-')
{
ans += sign * cur;
cur = 0;
sign = c == '+' ? 1 : -1;
}
else if (c == '(')
{
nums.push(ans);
nums.push(sign);
sign = 1;
ans = 0;
}
else if (c == ')')
{
ans += sign * cur;
cur = 0;
ans *= nums.top();
nums.pop();
ans += nums.top();
nums.pop();
}
}
ans += cur * sign;
return ans;
}
};