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 .

You may assume that the given expression is always valid.

Some examples:

``````"1 + 1" = 2
" 2-1 + 2 " = 3
"(1+(4+5+2)-3)+(6+8)" = 23
``````

Note: Do not use the `eval` built-in library function.

1. 空格：直接跳过
2. ‘(‘: 直接push入符号栈
3. ‘+’ or ‘-‘ : 如果符号栈顶不是运算符，则push此符号入栈，否则取出数字栈顶两个数字进行符号栈顶符号的运算，然后再push回符号栈，最后讲栈顶运算符换成当前运算符
4. ’)’: pop符号栈，如果遇到运算符就进行3中类似的运算，直到遇到‘(‘

C++ solution (20ms)

``````

class Solution {
public:
int numStack[10000];
char expStack[10000];
int numPtr = -1, expPtr = -1;

int strToInt(string s)
{
int num = 0;
for(int i = s.length() - 1; i >= 0; --i)
num += (s[i] - '0') * pow(10, s.length() - 1 - i);
return num;
}

int calculate(string s) {
int ptr = 0;
while(ptr < s.length())
{
if(s[ptr] == ' ') ++ptr;
else if(s[ptr] >= '0' && s[ptr] <= '9')
{
int num = 0;
do
{
num = num * 10 + (s[ptr++] - '0');
}while(ptr < s.length() && (s[ptr] >= '0' && s[ptr] <= '9'));
numStack[++numPtr] = num;
}
else
{
if(s[ptr] == '(') expStack[++expPtr] = s[ptr];
else if(s[ptr] == '+' || s[ptr] == '-')
{
if(expPtr == -1 || (expStack[expPtr] != '+' && expStack[expPtr] != '-')) expStack[++expPtr] = s[ptr];
else
{
if(expStack[expPtr] == '+') numStack[numPtr - 1] = numStack[numPtr - 1] + numStack[numPtr--];
else numStack[numPtr - 1] = numStack[numPtr - 1] - numStack[numPtr--];
expStack[expPtr] = s[ptr];
}
}
else
{
while(expStack[expPtr] != '(')
{
if(expStack[expPtr] == '+') numStack[numPtr - 1] = numStack[numPtr - 1] + numStack[numPtr--];
else numStack[numPtr - 1] = numStack[numPtr - 1] - numStack[numPtr--];
--expPtr;
}
--expPtr;
}
++ptr;
}
}
int res = numStack[0];
for(int i = 0; i <= expPtr; ++i)
{
if(expStack[i] == '+') res += numStack[i + 1];
if(expStack[i] == '-') res -= numStack[i + 1];
}
return res;
}
};

``````