logo
i囡漫笔
NEWS LETTER

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

Scroll down

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

当然没有那么简单！

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

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

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

那么解决方案哪里来？！探索解决方案，可以从百度来，可以问专业学者等等。

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

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

1
2
3
4
5
6
+：81，82
-：81，82
*：41，42
/：41，42
=：100，100
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为左符号类型为定义的oper，op2为右符号（新符号）

最后使用必须要有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
while（prior(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;
}
推荐文章
站内
相关 (54.5%)
16分钟

【实例1の更新1】表达式求值——加入新的单目运算符

在原基础上逐一的实现 `指数、对数以及三角函数` 的表达式求值

1
本站作者
原创文章
站内
相关 (52.9%)
16分钟

【实例1の更新2】表达式求值——加入括号运算

加入括号进行运算、优化报错方法

2
本站作者
原创文章
站内
推荐 (5.1%)
6分钟

Hexo博客NJK主题的相关文章智能推荐插件hexo-article-recommender进阶配置（DIY）

DIY客制化文章底部“文章推荐模块”，本篇文章介绍Nunjucks（NJK）模板的hexo主题（如NexT主题）如何实现。hexo-article-recomm

3
i囡漫笔
随心漫笔写文章
站内
推荐 (5.1%)
6分钟

Hexo博客EJS主题的相关文章智能推荐插件hexo-article-recommender进阶配置（DIY）

DIY客制化文章底部“文章推荐模块”，本篇文章介绍EJS模板的hexo主题如何实现。hexo-article-recommender为Hexo博客提供本地化智能

4
i囡漫笔
随心漫笔写文章

--- over ---

其他文章
目录导航 置顶
  1. 1. [原则：没有解决方案之前绝不能试图开始编程]
  2. 2. [解决方案一:算符优先文法]
  3. 3. 实践方案
    1. 3.1. 首先，根据实践方案进行初始化
    2. 3.2. 其次，建立实践方案对应的函数
    3. 3.3. 处理函数的丰富
  4. 4. 问题解决
请输入关键词进行搜索
  • to close