0%

【实例1】表达式求值——利用stack实现五种运算符的运算

看了标题有人会问,运算符的运算实现?直接printf(“%d”,a+b*c);不就完了么?

当然没有那么简单!

本篇带读者走进如何用stack来实现加减乘除运算

[原则:没有解决方案之前绝不能试图开始编程]

在我们拿到题目后,有些读者习惯于直接开始敲代码,我觉得这样不方便思路的养成。所以 没有解决方案之前绝不能试图开始编程

那么解决方案哪里来?!探索解决方案,可以从百度来,可以问专业学者等等。

[解决方案一:算符优先文法]

给不同运算符赋予“优先级”的概念
优先级相同的运算符按照结合性的顺序计算(从左到右或从右到左)
为了更简单地比较不同运算符的优先级
给每个运算符定义一个称为“优先数”的整数(以下优先数越小,优先级越高)

1
2
3
4
5
6
+:8182
-:8182
*:4142
/:4142
=:100100
3+4*5+2=

确定运算顺序:专家告诉我们:使用计算栈h(保存元素是运算符)
{a1, a2,…, an, k} 此时,k是watch dog,也就是哨兵
for (i=1 ;ai !=k ; ++k) ;

实践方案

  1. h.push(‘=’); // 用于判断结束,例如:若输入6=(当栈顶的=和输入的=匹配,则结束)

  2. 输入下一个运算符op;

  3. while(h.top()比op优先){ 栈顶元素出栈计算;}

  4. if(h.top()==’=’&& op==’=’){结束}

  5. h.push(op);

  6. 转2。(循环)

首先,根据实践方案进行初始化

根据上述实践方案,我们可以知道我们需要用到stack、stdio.h的头文件,并且需要用到oper(运算符)、和operand(操作数),而运算符是char型,操作数为float型

所以我们在文件头需要编写以下代码

1
2
3
4
5
#include<stdio.h>
#include<stack>

typedef char oper; //运算符
typedef float operand;

其次,建立实践方案对应的函数

我们初始化完成后,如果要解决问题,则需要建立解决问题的函数

于是我们建立一个名为solve的函数,因为是处理数据的,将要返回处理数据的数值,而数值的类型上述定义是operand类型

需要加入operand solve(){}函数。

我们在处理运算符时,需要判断运算符的优先级,我们需要一个函数判断左边和右边优先级大小,所以我们引入一个函数 根据定义的一个称为“优先数”的整数(优先数越小,优先级越高)来判断优先级大小。

我们使用int prior(oper op1, oper op2){},根据优先数相减得到的int型的正负值判断,其中op1为左符号类型为定义的operop2为右符号(新符号)

最后使用必须要有main函数main(){}

所以构造完毕后,总代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<stdio.h>
#include<stack>

typedef char oper; //运算符
typedef float operand; //运算数


int prior(oper op1, oper op2){
return;
}

operand solve(){
return;
}

main(){

}

处理函数的丰富

我们主要的处理函数是operand solve()

最简单的加减乘除运算是拥有两个数和一个运算符组成,所以我们要先定义两个数和运算符

我们还需要两个栈(一个存放操作数,一个存放操作符)

完善函数如下

1
2
3
4
5
6
operand solute(){
operand x, y;
oper op;
std::stack<oper> history; //历史栈 ,存放历史操作符号
std::stack<operand> operands; //存放操作数
}

我们根据实践方案(点击转到)

  1. h.push(‘=’); // 用于判断结束,例如:若输入6=(当栈顶的=和输入的=匹配,则结束)

  2. 输入下一个运算符op;

  3. while(h.top()比op优先){

​ 栈顶元素出栈计算;

}

  1. if(h.top()==’=’&& op==’=’){结束}(若有等号匹配,则结束循环)

  2. h.push(op);

  3. 转2。(循环)

1.h.push(‘=’);

那么我们添加history.push('=');输入等号,whach dog(士兵)进栈

1
2
3
4
5
6
7
operand solute(){
operand x, y;
oper op;
std::stack<oper> history; //历史栈 ,存放历史操作符号
std::stack<operand> operands; //存放操作数
history.push('=');//输入等号,whach dog(士兵)进栈
}

2.步骤2-5循环,直到若有等号匹配,则结束循环;

所以我们加入循环条件

1
2
3
4
5
6
7
8
9
10
11
operand solute(){
operand x, y;
oper op;
std::stack<oper> history; //历史栈 ,存放历史操作符号
std::stack<operand> operands; //存放操作数
history.push('=');//输入等号,whach dog(士兵)进栈
while(1){

if(prior(history.top(),op)==0) break;
}
}

3.输入下一个数和运算符op;

我们需要在循环体中持续不断的输入数和运算符

观察式子:3+2+1*5=5*8/7-4=9*8/7-5=

我们发现,我们输入的每个数字后面有且仅有一个运算符

所以我们加入

1
2
scanf("%f %c",&x,&op);		//输入一个数字和一个字符
operands.push(x); //将数字压入存放操作数的栈

4.栈顶元素出栈计算;

我们需要判断运算符的优先级,如果存放历史操作符号的栈顶比op优先,(优先数越小,优先级越高),那么直接计算历史操作数链接的两个数

示意图如下

image-20220522224804731

所以我们根据

  1. while(h.top()比op优先){

​ 栈顶元素出栈计算;

}

进行栈顶元素出栈计算;

所以写出以下循环

1
2
3
4
5
6
7
8
9
10
11
12
13
while(h.top()比op优先){
y = operands.top(); //让y为最新的数(优先级高的历史操作符的右边的数)
operands.pop(); //弹走最新的数(优先级高的历史操作符的右边的数)
x = operands.top(); //让x为优先级高的历史操作符的左边的数
operands.pop(); //弹走历史操作符的左边的数
switch(history.top()){ //判断优先级高的历史操作符
case '+': operands.push(x + y) ; break;
case '-': operands.push(x - y) ; break;
case '*': operands.push(x * y) ; break;
case '/': operands.push(x / y) ; break;
}
history.pop();//弹走历史操作符的栈顶
}

接下来我们需要对比history.top()【历史操作符(上一次的运算符号)】和op【即将压入history栈的符号】优先

通过之前的函数int prior(oper op1, oper op2)进行丰富,

又因为优先数越小,优先级越高,所以我们判断优先数的做差,判断差的正负性就可以判断优先级。

我们完善函数int prior(oper op1, oper op2)

1
2
3
int prior(oper op1, oper op2){
return p_num[op1].left - p_num[op2].right;
}

从而完善循环判断

1
2
3
4
5
whileprior(history.top(), op)<0){
y = operands.top(); //让y为最新的数(优先级高的历史操作符的右边的数)
operands.pop(); //弹走最新的数(优先级高的历史操作符的右边的数)
x = operands.top(); //让x为优先级高的历史操作符的左边的数
………………………………………………

5.h.push(op);压入op

若优先级不大于栈顶的优先级,要将op压入history栈history.push(op);,此操作要在判断是否为等号之后

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
operand solve(){
operand x, y;
oper op;
std::stack<oper> history;//历史栈
std::stack<operand> operands;
history.push('=');//输入等号,whach dog(士兵)进栈
while(1){
/*******************
*2. 输入下一个运算符op;
*3. while(h.top()比op优先){ 栈顶元素出栈计算;}
*4. if(h.top()=='='&& op=='='){结束}
*5. h.push(op);
*6. 转2。
********************/
scanf("%f %c",&x,&op);
operands.push(x);
while(prior(history.top(), op)<0){
y = operands.top();
operands.pop();
x = operands.top();
operands.pop();
switch(history.top()){
case '+': operands.push(x + y) ; break;
case '-': operands.push(x - y) ; break;
case '*': operands.push(x * y) ; break;
case '/': operands.push(x / y) ; break;
}
history.pop();
}
if(prior(history.top(),op)==0) break;
history.push(op);
}
return operands.top();
}

6.函数的完善

我们的解决函数operand solve(){}趋近完美,但是程序是由main(){}开始

所以我们要完善main函数

1
2
3
4
int main(){
printf("%g\n",solve());
return 0;
}

在函数int prior(oper op1, oper op2){}中,我们没有赋予p_num[op1].left(左符号、旧符号)和p_num[op2].right(右符号、新符号)的值(优先数)。所以我们在函数int prior(oper op1, oper op2){}之前加入以下代码,并且加入#include<map>

1
2
3
4
5
6
7
8
9
struct prv_num_t{char left,right;};//定义结构体 prv_num_t  _t代表类型 
//关键字只包含一部分数据项,就称为map
std::map<oper, prv_num_t> p_num={
{'+',{81,82}},
{'-',{81,82}},
{'*',{41,42}},
{'/',{41,42}},
{'=',{100,100}}
};
计算优先数的示意图

问题解决

最终获得代码

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include<stdio.h>
#include<stack>
#include<map>

typedef char oper;//运算符
typedef float operand;

/*优先数表*/
struct prv_num_t{char left,right;};//定义结构体 prv_num_t _t代表类型
//关键字只包含一部分数据项,就称为map
//关键字包含全部数据项,成为
std::map<oper, prv_num_t> p_num={
{'+',{81,82}},
{'-',{81,82}},
{'*',{41,42}},
{'/',{41,42}},
{'=',{100,100}}
};


/*op1在左,op2在右*/
/*返回值为负: op1优先级高于op2*/
/*返回值为正: op2优先级高于op1*/
/*返回值为0: op1优先级等于op2*/

int prior(oper op1, oper op2){
return p_num[op1].left - p_num[op2].right;
}

operand solute(){
operand x, y;
oper op;
std::stack<oper> history;//历史栈
std::stack<operand> operands;
history.push('=');//输入等号,whach dog(士兵)进栈
while(1){
/****************************************
*2. 输入下一个运算符op;
*3. while(h.top()比op优先){ 栈顶元素出栈计算;}
*4. if(h.top()=='='&& op=='='){结束}
*5. h.push(op);
*6. 转2。
******************************************/
scanf("%f %c",&x,&op);
operands.push(x);
while(prior(history.top(), op)<0){

y = operands.top();
operands.pop();
x = operands.top();
operands.pop();
switch(history.top()){
case '+': operands.push(x + y) ; break;
case '-': operands.push(x - y) ; break;
case '*': operands.push(x * y) ; break;
case '/': operands.push(x / y) ; break;
}
history.pop();
}
if(prior(history.top(),op)==0) break;
history.push(op);
}
return operands.top();
}

int main(){
printf("%g\n",solute());

return 0;
}

技术分享,如果您觉得内容不错的话不妨进行打赏,您的支持将鼓励我继续创作!
  • 本文作者: i囡漫笔
  • 本文链接: https://i-nmb.cn/example.html
  • 版权声明: 本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!

欢迎关注我的其它发布渠道