题目描述
实现一个简易的计算器,只包含正整数和+ - * / 和空格” “,不包含括号,输入一个字符串,计算它的值。
样例
输入:"3+2*2"
输出:7
算法1
(两个栈:字符栈和数字栈) $O(n)$
这道题是用了两个栈去做的:运算符号(+-/)栈和数字栈,是雪菜哥代码的一点小修改,已通过leetcode测试用例。
时间复杂度是O(n),就是遍历字符串的时间,栈的弹入弹出操作时间不计。
遍历每个字符时,如果是数字,就压入数字栈,如果是运算符号,就压入运算符号栈,并且接下来就判断运算符号栈的栈顶是‘’、‘/’这种运算级高的还是’+’、‘-’这种运算符号低的。如果运算符号栈顶是’‘或者‘/’,就直接将数字栈的栈顶的两个数字弹栈计算;如果是‘+’或者’-‘,就先压入栈中。考虑到会爆栈的隐患,每次当运算符号栈的元素大于等于2时,就进行弹栈计算(原因:不管’‘或者’/’只要出现过,就会立即被弹栈计算掉,符号栈的高度不会超过2,当是2时符号栈中没有’*’或者是’/’符号,只有’+’或者’-‘)。这样子计算直到最后,符号栈中只剩一个运算符时,那只能是’+’或者’-‘,但是这种情况需要特殊地判断一下,计算完毕后再将结果返回。(如果有考虑的疏漏或者错误请大家指出来)。
参考文献
雪菜哥视频代码修改
C++ 代码
class Solution {
public:
int calculate(string s) {
//维护一个符号栈和数栈,符号栈中最多只存两个元素。当时* /法时,就弹出计算;
//当是+-法时,最多累积到2进行计算
stack<char> op;
stack<int> num;
cout<<"s="<<s<<endl;
for(int i=0;i<s.size();i++){
if(s[i] ==' ') continue;
if(s[i]=='*' || s[i]=='/' || s[i] == '+' || s[i] =='-') op.push(s[i]);
else {
int j=i;
while(j<s.size() && s[j]>='0' && s[j]<='9') j++;
num.push(atoi(s.substr(i,j-i).c_str()));
i =j-1;
if(!op.empty()) {
if(op.top() == '*' || op.top() =='/'){
int y = num.top();
cout<<"y="<<y<<endl;
num.pop();
int x = num.top();
cout<<"x="<<x<<endl;
num.pop();
if(op.top() =='*'){
num.push(x*y);
}
else num.push(x/y);
op.pop();
}
else if(op.size() >=2){
int z = num.top();num.pop();
int y = num.top();num.pop();
int x = num.top();num.pop();
char op2 = op.top();op.pop();
char op1 = op.top();op.pop();
if(op1 == '+') num.push(x+y),num.push(z);
else num.push(x-y),num.push(z);
op.push(op2);
}
}
}
}
//考虑到op栈中最后一个运算是‘+’或者‘-’,所以需要单独判断一下。
//这种情况对应于算到最后只剩一个运算符号的时候,
if(op.size() ==1){
int x = num.top();num.pop();
int y = num.top();num.pop();
char op1 = op.top();op.pop();
if(op1 == '+') num.push(x+y);
else num.push(y-x);
}
return num.top();
}
};