基本计算器
实现一个基本计算器
题源:LeetCode224,LeetCode227,LeetCode772
其中,第772题是这类题的终极版(不包括自定义运算符的题)
也就是说,它的解法——双栈法,可以作为这类题的通解
下面我们来看具体的题目
为了说明这个解法,我们先把目光投到人类是如何处理一个算式的
小学我们就知道,计算的关键是处理好优先级,即先算括号里的内容,再算乘除法,最后算加减法
由于运算符是左结合的,如果优先级相同,就从左向右算
比如1-(5+1)/2+2*3这个算式,我们先计算5+1=6,然后算6/2=3,2*3=6,最后算1-3=-2,-2+6=4
发现没有可以算的东西了,就知道答案是4
其实我们编程计算的思路基本上也是与之一致的
别急,先从简单的地方看起
第一种情况——只有加减号(或者只有乘除号)
这可就好了,此时没有优先级的干扰,只考虑结合律,也就是从左向右算
比如1+2-3+4,扫描到1和+并保存,接着扫描到2,我们就立即计算1+2=3并保存
然后扫描到-和3,计算3-3=0并保存,最后扫描到+和4,计算0+4=4并保存,接着发现扫描结束,那4就是答案
代码如下1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32class Solution{
public:
int calculate(string s)
{
int num1=0,num2=0;//只需要两个int保存操作数
char operation;
for(int i=0;i < s.size();++i)
{
if(isdigit(s[i]))
{
if(i==0)//暂且不考虑第一个数为负数的情况,将第一个数存入num1,以后再找到数,就存入num2
{
for(;isdigit(s[i]);++i)
num1=num1*10-'0'+s[i];
--i;
}
else
{
for(;isdigit(s[i]);++i)
num2=num2*10-'0'+s[i];
--i;
//找到第二个操作数后,执行运算,结果保存到num1,然后将num2置零
num1+=operation=='+'?num2:-num2;
num2=0;
}
}
else//保存运算符
operation=s[i];
}
return num1;//最终结果保存在num1里
}
};
更简单的写法是——使用栈
如果符号是+,就把当前数字压栈,如果是-,就把它的相反数压栈,最后将栈内数字累加
这种方法对下面加减乘除共存的情况有所帮助,但是它放弃了立即计算的能力,空间消耗大1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28class Solution{
public:
int calculate(string s)
{
stack<int> nums;
char operation;
int answer=0;
for(int i=0;i < s.size();++i)
{
if(isdigit(s[i]))
{
int num=0;
for(;isdigit(s[i]);++i)
num=num*10-'0'+s[i];
--i;
nums.push(i==0||operation=='+'?num:-num);
}
else
operation=s[i];
}
while(!nums.empty())
{
answer+=nums.top();
nums.pop();
}
return answer;
}
};
对于负数的处理:只需要最前面填上0,就转化为0-负数的算式;对于空格,只需要continue就可以了
这里只写出基本逻辑,不纠结具体细节
下面我们开始考虑复杂的情况了,如果加减乘除都有怎么办?
第二种情况——加减乘除都有(即力扣227题)
其实这还是比较好解决的,因为,/就是最高的优先级了,基于上述栈解法,我们可以扫描一遍
如果前面的符号是+-,就直接push,如果是/,我们就从栈顶弹出元素执行运算再将结果push,最后累加,代码如下1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42class Solution{
public:
int calculate(string s)
{
stack<int> nums;
char operation=' ';//初始运算符设为空格,用来标记第一个数
int answer=0;
for(int i=0;i < s.size();++i)
{
if(s[i]==' ')//跳过空格
continue;
if(isdigit(s[i]))//扫描到数,考察前面的符号
{
int num=0;
for(;isdigit(s[i]);++i)
num=num*10-'0'+s[i];
--i;
if(operation==' '||operation=='+')//如果是第一个数或者前面是+号,push
nums.push(num);
else if(operation=='-')//如果前面是-号,push相反数
nums.push(-num);
else if(operation=='*'||operation=='/')//如果前面是乘除号,执行弹出,运算,压入(正负号体现在前面的数上了)
{
int prenum=nums.top();
nums.pop();
if(operation=='*')
nums.push(prenum*num);
else
nums.push(prenum/num);
}
}
else
operation=s[i];//记录下运算符
}
while(!nums.empty())//执行累加
{
answer+=nums.top();
nums.pop();
}
return answer;
}
};
上面的也是LeetCode官解的思路,但是就如我们说的,它使用了更多的空间,因为一些能够立即计算的东西我们没有计算
考虑一下1+2-3*4/6+5,如何尽可能的把能算的算出来以减少空间消耗呢?
我们要知道哪些运算是安全的
注意到,运算符是左结合的,也就是说运算符左边的算式如果优先级相同或更高,都是可以算的
那么,以运算符为标准,扫描到+,我们什么都做不了;扫描到2,是否就直接计算1+2了呢?
答案是否定的!!因为我们不知道2后面是什么——万一是*呢?
但是扫描到-,我们就放心了,此时计算1+2就是安全的,我们执行计算,保存3
接着扫描到*,会不会计算3-3?不会,因为-的优先级比*高,所以仅仅保存*,不执行运算
扫描到/,计算34=12,保存;扫描到/,计算12/6=2,保存;扫描到+,计算3-2=1,保存
最后计算1+5,得到答案6,返回
我们用*双栈法实现上述过程
定义两个栈,nums栈存放操作数,ops栈存放运算符
扫描整个字符串,遇到空格跳过,遇到数字,则将完整的操作数存入nums
遇到运算符,压栈,在压栈之前,计算当前可以运算的部分
运算是通过operation函数实现的,从ops中弹出运算符,nums中弹出两个操作数,执行运算,结果push回nums
可以运算的部分指的是比当前运算符高级或同级的所有运算,用一个val函数返回运算符的优先级1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50class Solution {
public:
stack<int> nums;
stack<char> ops;
int val(char c)
{
if(c=='*'||c=='/')
return 2;
return 1;
}
void operation()
{
int temp1=nums.top();
nums.pop();
int temp2=nums.top();
nums.pop();
switch(ops.top())
{
case '+':nums.push(temp2+temp1);break;
case '-':nums.push(temp2-temp1);break;
case '*':nums.push(temp2*temp1);break;
case '/':nums.push(temp2/temp1);break;
}
ops.pop();
}
int calculate(string s) {
for(int i=0;i < s.size();++i)
{
if(s[i]==' ')
continue;
else if(isdigit(s[i]))
{
long n=0;
for(;isdigit(s[i]);++i)
n=n*10+s[i]-'0';
--i;
nums.push(n);
}
else
{
while(!ops.empty()&&val(ops.top())>=val(s[i]))
operation();
ops.push(s[i]);
}
}
while(!ops.empty())
operation();
return nums.top();
}
};
一些思考:
- 对于双栈法来说,优先级高的立即运算不仅是减少空间消耗的手段,也是必要的
因为比如对于1-2+3,如果不在看到+时立即计算1-2,由于最后是从后往前算的,就会变成3+2=5,1-2=-1
这个问题在前一种方法里是通过乘除立即运算,+-保存符号来避免的 - 搜索可以运算的部分时,遇到第一个优先级低的就停止,会不会导致没算完?
是不会的,因为比当前运算符高级或同级的一定在前面算过了 - 循环结束时会剩下什么样的算式?首先,不会有相同的符号出现,其次,前面的算式优先级一定比后面的低
所以,要么只剩下一个算式,要么是一个数加减一个乘除式,此时从后往前算是符合优先级的
接下来考虑有括号的情况第三种情况——带括号的加减运算(即力扣224题)
其实关键仍然是优先级的问题,但是与上面只有两种优先级不同,括号使优先级变成了无数种
但是,我们还是可以沿用上面的方法,将优先级高的先算,存入栈中,直到只剩下优先级相同的加减运算
为了达到这个目的,我们在遇到左括号后,就要优先处理后面的内容,直到遇到一个右括号,将结果记录下来
举个栗子:1+(2+3-(4+5)),先保存1,记录+,然后遇到左括号,保存2和3,记录-,又遇到左括号,保存4和5
终于遇到右括号了,我们可以一直计算到前面的左括号,即5+4=9,然后看到前面保存的-,知道应该保存-9
然后又遇到第二个右括号,计算-9+3+2=-4,这个括号前面是+,所以保存-4,最后发现后面没有东西了,计算-4+1=-3,返回答案-3
或许你发现了,我上面的算式都是从后往前写的,这是栈先进后出的特性决定的
要实现上述过程,具体怎样操作呢?
首先,可以预想,类似上面的过程,我们需要一个数字栈来保持数据
但是,怎样确保我们发现右括号时计算到前面匹配的左括号就停止呢?
一种作法是记录当前括号中的数字数目,但由于计算后可能需要更新,实现起来比较复杂
我采用了比较无脑的办法,也就是——每遇到一个左括号，就开一个新栈
这样,当前栈算完了,也就是这个括号算完了,那么,我们将结果判断符号后加入上一层栈
所以,可以用一个vector<stack<int>>来保存所有的栈,每次都对最后一个栈进行操作
代码如下但是细节处理挺麻烦,我也是提交了好多次才通过1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53class Solution{
public:
int calculate(string s)
{
vector<stack<int>> nums;
nums.push_back({});//保存所有的栈,一开始预留一个空栈
char operation=' ';
vector<char> presigns={' '};//presigns记录括号前的符号,一开始即为' '
int answer=0;
for(int i=0;i < s.size();++i)
{
if(s[i]==' ')
continue;
if(isdigit(s[i]))
{
int num=0;
for(;isdigit(s[i]);++i)
num=num*10-'0'+s[i];
--i;
nums.back().push(operation=='-'?-num:num);//将数字push进当前栈
}
else
{
if(s[i]=='(')//遇到左括号,开一个新栈,记录括号的符号,数字符号置为' '
{
nums.push_back({});
presigns.push_back(operation);
operation=' ';
}
else if(s[i]==')')//遇到右括号,将当前栈算完,push进上一个栈
{
int answer=0;//内部的暂时的answer
while(!nums.back().empty())
{
answer+=nums.back().top();
nums.back().pop();
}
nums.pop_back();
nums.back().push(presigns.back()=='-'?-answer:answer);
presigns.pop_back();
}
else
operation=s[i];
}
}
while(!nums.back().empty())
{
answer+=nums.back().top();
nums.back().pop();
}
return answer;
}
};
而双栈法也可以很好地解决括号位置的问题
我们把括号也视为一个运算符(指示优先级),计算方式和上面的双栈法相同,遇到左括号,正常入栈
遇到右括号,一路算到左括号,然后保存结果(相当于是用ops栈记录了括号的范围)
代码实现1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55class Solution {
public:
stack<int> nums;
stack<char> ops;
void operation()
{
int temp1=nums.top();
nums.pop();
int temp2=nums.top();
nums.pop();
if(ops.top()=='+')
nums.push(temp2+temp1);
else
nums.push(temp2-temp1);
ops.pop();
}
int calculate(string s) {
//边界处理,防止第一个数字带符号,补0
if(s[0]=='+'||s[0]=='-')
s="0"+s;
while(s.find("(-")!=-1){
s.replace(s.find("(-"),2,"(0-");
}
for(int i=0;i < s.size();++i)
{
if(s[i]==' ')
continue;
else if(isdigit(s[i]))
{
int n=0;
for(;isdigit(s[i]);++i)
n=n*10-'0'+s[i];
--i;
nums.push(n);
}
else if(s[i]=='(')
ops.push('(');
else if(s[i]==')')
{
while(ops.top()!='(')
operation();
ops.pop();
}
else
{
while(!ops.empty()&&ops.top()!='(')
operation();
ops.push(s[i]);
}
}
while(!ops.empty())
operation();
return nums.top();
}
};最后一种情况——加减乘除和括号都有
其实有了上面的铺垫,再用双栈法解决这个”终极问题”也就是水到渠成了
其实就是第二种和第三种情况双栈法写法的结合,不多说了,直接上代码1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58class Solution {
public:
stack<int> nums;
stack<char> ops;
int val(char c)//优先级判断函数
{
if(c=='*'||c=='/')
return 2;
return 1;
}
void operation()//运算函数
{
int temp1=nums.top();
nums.pop();
int temp2=nums.top();
nums.pop();
switch(ops.top())
{
case '+':nums.push(temp2+temp1);break;
case '-':nums.push(temp2-temp1);break;
case '*':nums.push(temp2*temp1);break;
case '/':nums.push(temp2/temp1);break;
}
ops.pop();
}
int calculate(string s) {
for(int i=0;i < s.size();++i)
{
if(s[i]==' ')
continue;
else if(isdigit(s[i]))
{
int n=0;
for(;isdigit(s[i]);++i)
n=n*10-'0'+s[i];
--i;
nums.push(n);
}
else if(s[i]=='(')
ops.push('(');
else if(s[i]==')')
{
while(ops.top()!='(')
operation();
ops.pop();
}
else
{
while(!ops.empty()&&ops.top()!='('&&val(ops.top())>=val(s[i]))
operation();
ops.push(s[i]);
}
}
while(!ops.empty())
operation();
return nums.top();
}
};总结
我们先大体介绍了一下人类是怎么处理算式的
然后从最简单的只含加减的情况开始,提供了两种方法
一种是直接计算,即两两运算,结果再和后面的数运算
另一种是先将所有数存入栈,再执行累加
然后看既有加减又有乘除和带括号的加减的情况,各提供了两种方法
一种是直接计算的双栈法
另一种是先算优先级高的,保存下来,再算优先级低的,它更容易理解,但处理复杂问题比较难写
最后对于加减乘除和括号都有的情况,提供了双栈法的解法
可以说,掌握了双栈法的写法,这类题都不在话下彩蛋
如果打开Windows自带计算器(Fn+F12),调成科学模式,然后输入算式
会发现它和双栈法的计算顺序是极为类似的
比如,输入1+2,还不会运算,当我们再键入-,屏幕上就会显示3
再键入3*(,屏幕上显示0,这是进入了括号内运算的意思
键入4*5),看到括号时,计算并显示20如果再键入+,就会将前面所有的都算出来,显示-57
你也可以自己去试验一下
