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```
就是把这个字符串解析成一个式子然后算出结果。运算只有加减法，也没有负数，优先级比较好搞。有括号先算括号里面的。C语言书里头讲过可以用栈。这里的括号，我自然地想到了递归。“）”是递归的终止条件。遇到右括号就相当于括号里的东西处理完返回括号里头的结果。为了方便处理，把输入的字符串最后加上了一个“）”，这样递归的终止条件就不用再加一个判断字符串结束了。
从头开始读字符串，边读边解析。分几情况：
1，正负号，整形op表示符号。减法乘以-1也转化为加法。
2，数字，解析出来压到存运算数的vector里去。
3，左括号，开始递归调用这个函数，表示要先算括号里面的。
括号里的运算出结果就把它压到运算数的向量里头。（运算数的来源就三种，从字符串解析出来，和括号里的值算出来，运算数的vector进行运算的结果。）
4，右括号，说明函数该就结束了。
只要现在存这两个运算数，就可以做运算了。
代码如下：(递归)
```cpp
class Solution {
public:
int calculate(string s) {
//递归
int index = 0;
s += ')';
int res = calucateBrackets(s,index);
return res;
}
private:
//计算括号里面的值
int calucateBrackets(string &s,int &index)
{
vector<int> num; //数
int op = 0; //运算符 +1 -1
for(index; s[index] != ')'; index++)
{
if(s[index] == ' ')//空格，跳过
continue;
if(s[index] == '+')//正负号
{
op = 1;
continue;
}
else if(s[index] == '-')
{
op = -1;
continue;
}
if(s[index] >= '0' && s[index] <= '9')//数字
{
int value = parseInt(s,index);
num.push_back(value);//把这数放进去
}
else if(s[index] == '(')//如果是左括号，递归算括号里面的
{
index++;
int res = calucateBrackets(s,index);
num.push_back(res);
}
if(num.size() == 2)
{
int a = num[0];
int b = num[1];
num.clear();
num.push_back(a + op*b);
}
}
return num[0];
}
//连读一个数
int parseInt(string &s, int &index)
{
int res = 0;
while(s[index] >= '0' && s[index] <= '9')
{
res*= 10;
res+= (s[index] - '0');
index++;
}
index--;
return res;
}
};
也可以不用递归算这个。
if else 大法好。。。
两个栈，一个存运算符，一个存运算数。“+”存1，“-”存-1，“（”存0，当个分界符。遇到“）”就弹栈，算，算到运算符栈有个0相当于算完一个括号。用栈的话是从后往前算。要是前头有负号就会出错了。（就像1-2+3，从后往前算相当于1-（2+3）所以，遇到负号就把它算掉。。）
代码如下：（非递归）
class Solution {
public:
int calculate(string s) {
int index = 0;
if(s.size() == 0)
return 0;
vector<int> num; //数
vector<int> op;
op.push_back(0);
//操作符 + 1 - -1 （ 2
//stack<int> num; //数
//stack<int> op; //操作符 + 1 - -1 （ 2
for(index ; index < s.size(); index++)
{
if(s[index] == '+')
{
op.push_back(1);
}
else if(s[index] == '-')
{
op.push_back(-1);
}
else if(s[index] >= '0' && s[index] <= '9')//数字
{
int value = parseInt(s,index);
num.push_back(value);//
if(num.size() >= 2 && op[op.size()-1] != 0)
{
int b = num[num.size()-1];
num.pop_back();
int a = num[num.size()-1];
num.pop_back();
int c = op[op.size()-1];
op.pop_back();
num.push_back(a+b*c);
//calc(num, op);
}
}
else if(s[index] == '(')//左括号压栈
{
op.push_back(0);
}
else if(s[index] == ')')//右括号，一直算啊算，知道算到左括号位置
{
while(op[op.size()-1] != 0)
{
int b = num[num.size()-1];
num.pop_back();
int a = num[num.size()-1];
num.pop_back();
int c = op[op.size()-1];
op.pop_back();
num.push_back(a+b*c);
//calc(num, op);
}
op.pop_back();
if(num.size() >= 2 && op[op.size()-1] != 0)
{
int b = num[num.size()-1];
num.pop_back();
int a = num[num.size()-1];
num.pop_back();
int c = op[op.size()-1];
op.pop_back();
num.push_back(a+b*c);
//calc(num, op);
}
}
}
while(num.size() != 1)
{
int b = num[num.size()-1];
num.pop_back();
int a = num[num.size()-1];
num.pop_back();
int c = op[op.size()-1];
op.pop_back();
num.push_back(a+b*c);
//calc(num, op);
}
return num[0];
}
private:
//连读一个数
int parseInt(string &s, int &index)
{
int res = 0;
while(s[index] >= '0' && s[index] <= '9')
{
res*= 10;
res+= (s[index] - '0');
index++;
}
index--;
return res;
}
};
还有个坑一点的地方。就是解析数字这个我弄成了一个函数，最开始传参传的是string，每次传参相当于复制，所以遇到一个特别长的测试用例时候就特别慢，超时了。改成引用传参就跑过去了。
网友评论