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.
题目说模仿一个计算器，做加减法，不过要注意括弧跟空格，空格就直接跳吧然后其他的保存下来，用栈分别存储数字括弧跟运算符，每遇到一个”）“就弹栈运算，数字跟括弧放一起，不过其实这样不太好，因为得为括弧设定一个特定的数，因为这个WA了一次。
class Solution {
public:
stack<int> s_num;
stack<char> fuhao;
int count_f=0;
void cal_sub(){
if(s_num.size()<2)
return;
stack<int> nums;
stack<char> cal;
int b=s_num.top();
s_num.pop();
nums.push(b);
int a=s_num.top();
s_num.pop();
char c;
while(a!=-11111111){
c=fuhao.top();
fuhao.pop();
nums.push(a);
cal.push(c);
if(s_num.size()>0){
a=s_num.top();
s_num.pop();
}
else
a=-11111111;
}
count_f--;
a=nums.top();
nums.pop();
while(nums.size()>0){
b=nums.top();
nums.pop();
c=cal.top();
cal.pop();
if(c=='+')
a=a+b;
if(c=='-')
a=a-b;
}
s_num.push(a);
}
int string2num(string s){
string c_num;
for(int i=0;i<s.size();i++){
if(s[i]=='('){
s_num.push(-11111111);
count_f++;
}
if(s[i]>='' && s[i]<='')
c_num+=s[i];
if(s[i]==')') {
if(c_num!="")
s_num.push(atoi(c_num.c_str()));
c_num="";
cal_sub();
}
if(s[i]=='+' || s[i]=='-') {
if(c_num!="")
s_num.push(atoi(c_num.c_str()));
c_num="";
fuhao.push(s[i]);
}
}
if(c_num!="")
s_num.push(atoi(c_num.c_str()));
cal_sub();
return s_num.top();
}
int calculate(string s) {
return string2num(s);
}
};