计算器问题lc224
[toc]
计算器 lc224
题目描述
给定一个包含正整数、加(+)、减(-)、乘(*)、除(/)的算数表达式(括号除外)，计算其结果。
表达式仅包含非负整数，+， - ，*，/ 四种运算符和空格 。 整数除法仅保留整数部分。
示例 1:
输入: "3+2*2"
输出: 7
示例 2:
输入: " 3/2 "
输出: 1
示例 3:
输入: " 3+5 / 2 "
输出: 5
说明：
你可以假设所给定的表达式都是有效的。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/calculator-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
前中后缀表达式。研究。
解决方法
1.分级运算
利用1个栈
4个队列：因为只有两种运算，乘除和加减，所以先算乘除再算加减。
执行用时：20 ms, 在所有 C++ 提交中击败了53.67%的用户
内存消耗：10.2 MB, 在所有 C++ 提交中击败了19.18%的用户
notice:给的案例有
" 3+5 / 2 "
所以遇到空格应该跳过去
stack<int> tmpnum;//存数字，将字符串数字转成数字
queue<int> num; //乘除的数字和符号
queue<int> fuhao;
queue<int> fnum;//存加减的数字和符号
queue<int> ffuhao;
class Solution {
public:
int calculate(string s) {
stack<int> tmpnum;
queue<int> num;
queue<int> fuhao;
queue<int> fnum;
queue<int> ffuhao;
// res = 0;
int extnum=0;
s = s+"+";
for(int i=0;i<s.length();i++){
extnum=0;
if (s[i]>='0' && s[i]<='9'){
tmpnum.push(s[i]);
}else if(s[i]==' '){
continue;
}
else{
int j=0;
while(!tmpnum.empty()){
extnum+=(tmpnum.top()-'0')*(pow(10,j));
j+=1;
tmpnum.pop();
}
// cout<<extnum<<endl;
if (s[i]=='*' || s[i]=='/'){
num.push(extnum);
fuhao.push(s[i]);
}else{//如果是+or-且之前不为空
int s1num = extnum;
if(!fuhao.empty()){
num.push(s1num);
s1num=num.front();
num.pop();
while(!fuhao.empty()){
int a = num.front();
char b=fuhao.front();
if(b=='*'){
s1num*=a;
}else{
s1num/=a;
}
num.pop();
fuhao.pop();
}
}
// cout<<s1num<<endl;
fnum.push(s1num);
ffuhao.push(s[i]);
}
}
}
int res = fnum.front();
fnum.pop();
// cout<<extnum<<endl;
while(!fnum.empty()){
int a = fnum.front();
char b=ffuhao.front();
if(b=='+'){
res+=a;
}else{
res-=a;
}
fnum.pop();
ffuhao.pop();
}
// cout<<"sda"<<endl;
// cout<<res<<endl;
return res;
}
};
2. 知识点-字符串转整数
1）atoi和stoi
头文件都是#include<cstring>
atoi()的参数是 const char* ,因此对于一个字符串str我们必须调用 c_str()的方法把这个string转换成 const char*类型的,而stoi()的参数是const string*,不需要转化为 const char*；
stoi()会做范围检查，默认范围是在int的范围内的，如果超出范围的话则会runtime error！atoi()不会做范围检查，如果超出范围的话，超出上界，则输出上界，超出下界，则输出下界；
2)用栈,直接确定每一位
while(!tmpnum.empty()){
extnum+=(tmpnum.top()-'0')*(pow(10,j));
j+=1;
tmpnum.pop();
}
3）从头开始计算
string s = "458";
int n = 0;
for (int i = 0; i < s.size(); i++) {
char c = s[i];
n = 10 * n + (c - '0');
}
// n 现在就等于 458
作者：labuladong
链接：https://leetcode-cn.com/problems/basic-calculator-ii/solution/chai-jie-fu-za-wen-ti-shi-xian-yi-ge-wan-zheng-ji-/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
这个还是很简单的吧，老套路了。但是即便这么简单，依然有坑：(c - '0')的这个括号不能省略，否则可能造成整型溢出。
因为变量c是一个 ASCII 码，如果不加括号就会先加后减，想象一下s如果接近 INT_MAX，就会溢出。所以用括号保证先减后加才行。
作者：labuladong
链接：https://leetcode-cn.com/problems/basic-calculator-ii/solution/chai-jie-fu-za-wen-ti-shi-xian-yi-ge-wan-zheng-ji-/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
新思路
1.加减法，可以通过都是加法，转换减法为负数实现。（c++ INT_MIN 忽略符号表示成正数好像会溢出）
2.乘除法思路，乘除取出栈中前一个数字运算再放进去。
3.处理空格。
4.括号。【遇到‘（’开始递归，遇到‘）’结束递归。】
本文借实现计算器的问题，主要想表达的是一种处理复杂问题的思路。
我们首先从字符串转数字这个简单问题开始，进而处理只包含加减法的算式，进而处理包含加减乘除四则运算的算式，进而处理空格字符，进而处理包含括号的算式。
可见，对于一些比较困难的问题，其解法并不是一蹴而就的，而是步步推进，螺旋上升的。如果一开始给你原题，你不会做，甚至看不懂答案，都很正常，关键在于我们自己如何简化问题，如何以退为进。
退而求其次是一种很聪明策略。你想想啊，假设这是一道***，你不会实现这个计算器，但是你写了字符串转整数的算法并指出了容易溢出的陷阱，那起码可以得 20 分吧；如果你能够处理加减法，那可以得 40 分吧；如果你能处理加减乘除四则运算，那起码够 70 分了；再加上处理空格字符，80 有了吧。我就是不会处理括号，那就算了，80 已经很 OK 了好不好。
作者：labuladong
链接：https://leetcode-cn.com/problems/basic-calculator-ii/solution/chai-jie-fu-za-wen-ti-shi-xian-yi-ge-wan-zheng-ji-/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
评论中：
lc224
执行用时：80 ms, 在所有 C++ 提交中击败了14.17%的用户
内存消耗：280.7 MB, 在所有 C++ 提交中击败了10.88%的用户
class Solution {
public:
int calculate(string s) {
int begin = 0;
return calHelper(s,begin);
}
int calHelper(string s,int& i){//这里传的是引用
char operation = '+';
stack<int> nums;
int num=0;
int res=0;
for(i;i<s.size();i++){
if(s[i]>='0' && s[i]<='9'){
num=num*10 + (s[i]-'0');
}
// cout<<num<<endl;
if(s[i]=='('){//递归
num=calHelper(s,++i);//从i的下一个计算，进入递归
i++;//计算完，i指向‘）’，需要再++,）之后肯定不是数字，但可能是符号和)
}
if(i>=s.size()-1 || ((s[i]<'0'||s[i]>'9')&&s[i]!=' ')){
int pre=0;
switch(operation){
case '+':nums.push(num);
break;
case '-':nums.push(-num);
break;
case '*':
pre = nums.top();
nums.pop();
nums.push(pre*num);
break;
case '/':
pre = nums.top();
nums.pop();
nums.push(pre/num);
break;
}
operation = s[i];
num = 0;
}
if(s[i]==')'){
break;//返回递归
}
}
while(!nums.empty()){
res+=nums.top();
nums.pop();
}
return res;
}
};
值得注意的地方：
https://leetcode-cn.com/problems/basic-calculator-ii/solution/chai-jie-fu-za-wen-ti-shi-xian-yi-ge-wan-zheng-ji-/620683
int calHelper(string s, int& i) 这一句中 i 前边不加 & 为什么结果会错误?
c++写法这里有个坑，就是不能用char c = s[i]，因为当进入递归之后退出来，i指向‘)’，如果用变量c代替的话，会出现当前c还是之前的‘(’，会造成逻辑混乱，而实时的用s[i]则能够走正确逻辑，同时switch那段需要放到判断‘(’的后面，从而使得跳回现在函数栈时，正确判断之后该怎么走。 总体来说，就是按照层主的代码写，没有问题，重点在于实时更新位置i,
加&是把原来的传值改为传引用，也就是对i的改变就是对原始对象的改变，不加&的话，当退出递归调用，s[i] 指向的还是原来进入递归的条件，也就是‘(’
https://leetcode-cn.com/problems/basic-calculator-ii/solution/chai-jie-fu-za-wen-ti-shi-xian-yi-ge-wan-zheng-ji-/684160
if (((s[i] < '0' || s[i] > '9') && s[i] != ' ') || i >= s.size() - 1)
这个部分是不是需要换下顺序，因为当最后一个字符是）时，递归结束，i++就超出索引了
if (i >= s.size() - 1||((s[i] < '0' || s[i] > '9') && s[i] != ' ') )
if (i >= s.size() || s[i] == ')')
