logo
i囡漫笔
NEWS LETTER

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

  • Home
  • example-optimization-1.html
Scroll down

前段时间我们学习了利用stack实现五种运算符的运算：【实例】表达式求值——利用stack实现五种运算符的运算 | 《课程设计》笔记 (i-nmb.cn)

实际上我们的表达式求值中并不是只有这5种运算，他还包括了 指数、对数以及三角函数等等。

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

写在前面

之前，在【实例】表达式求值——利用stack实现五种运算符的运算 | 《课程设计》笔记 (i-nmb.cn)中，我们做出了一下代码

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 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();
}

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

今天的实例更新，是建立再此代码基础上的

实现目标

1、优化之前的代码

2、逐一的实现 指数、对数以及三角函数 的表达式求值

1.优化代码

在加入新功能之前，我们先审视之前我们敲击的代码，我们在operand solve(){}函数中使用了以下循环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
operand solve(){
	while(1){
	……………………………………………………
		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;
		}
		……………………………………
	}
	…………………………………………
}

这个循环实质上是一个运算核心，放在循环中，总是不太合适。

所以我们把他提取出来，改造成一个函数operand calc(){}，返回类型为之前定义的operand（操作数）

operand calc()在循环while(prior(history.top(),op)<0)返回运算结果，若输入出错，则输出Err，返回-1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
operand calc(){
	operand x, y;
	y = operands.top();
	operands.pop();
	x = operands.top();
	operands.pop();
	switch(history.top()){
		case '+': return x+y;//当运算符为+时，在循环while(prior(history.top(),op)<0)返回x+y运算结果
		case '-': return x-y;//当运算符为-时，在循环while(prior(history.top(),op)<0)返回x-y运算结果
		case '*': return x*y;//当运算符为*时，在循环while(prior(history.top(),op)<0)返回x*y运算结果
		case '/': return x/y;//当运算符为/时，在循环while(prior(history.top(),op)<0)返回x/y运算结果
	}
	printf("Err");
	return -1;
}

而原 while(prior(history.top(), op)<0){}循环体中改为

1
2
3
4
while(prior(history.top(),op)<0){
	operands.push(calc());
	history.pop();
}

最后将以下代码设置为全局变量

1
2
std::stack<oper> history;//历史栈 
std::stack<operand> operands;

至此优化结束，优化后的总代码为：

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
72
73
74
75
76
77
78
79
80
#include<stdio.h>
#include<stack>
#include<map>

typedef char oper;//运算符
typedef float operand;
std::stack<oper> history;//历史栈 
std::stack<operand> operands;

/*优先数表*/
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 calc(){
	operand x, y;
	y = operands.top();
	operands.pop();
	x = operands.top();
	operands.pop();
	switch(history.top()){
		case '+': return x+y;
		case '-': return x-y;
		case '*': return x*y;
		case '/': return x/y;
	}
	printf("Err");
	return -1;
}


operand solve(){
	operand x, y;
	oper op;

	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){
			operands.push(calc());
			history.pop();
		}
		if(prior(history.top(),op)==0) break;
		history.push(op);
	}
	return operands.top();
}

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

2.增加指数运算和对数运算符

增加指数运算符

增加指数运算相对简单，在map（std::map<oper, prv_num_t> p_num）里面增加{"关键字",{左优先数,右优先数}}，左优先级大于右优先（从左到右运算）【2^3^2==64!=2^(3^2)】

即

1
2
3
4
5
6
7
8
9
10
std::map<oper, prv_num_t> p_num={
	{'+',{81,82}},
	{'-',{81,82}},
	{'*',{41,42}},
	{'/',{41,42}},
	{'=',{100,100}},
    
+    {'^',{32,31}}
    
};

并且在运算函数calc(){}加入返回运算值

即

1
2
3
4
5
6
7
	case '*': return x*y;
	case '/': return x/y;

+	case '^': return pow(x,y);

}
printf("Err");

因为用到了pow函数，所以我们在头文件加入#include<math.h>

至此，增加指数运算符操作结束

增加对数运算符

同理

在map（std::map<oper, prv_num_t> p_num）里面增加{"关键字",{左优先数,右优先数}}，左优先级小于右优先（从右到左运算）【log （2,log(2,8))=3】

1
2
3
4
5
6
7
8
9
10
11
12
std::map<oper, prv_num_t>  p_num={
	{'+',{81,82}},
	{'-',{81,82}},
	{'*',{41,42}},
	{'/',{41,42}},
	{'=', {100,100}},
	{'^',{32,31}}, 
    
+	{'L',{22,21}}//对数运算符log(x,y) ；log (x,log(x,x)) ，右边优先 
    
}
printf("Err");

在运算函数calc(){}加入返回运算值

1
2
3
4
5
6
7
8
9
	case '*': return x*y;
	case '/': return x/y;
	case '^': return pow(x,y);
	
+	case 'L': return log(y)/log(x);//对数换底公式 ,以x（先输入的数）为底数

}
printf("Err");

至此，增加对数运算符操作结束

试试2L8= 答案是3

3.增加三角函数（单目运算符）

在map添加关键字

1
2
3
4
5
6
7
8
9
10
11
12
13
std::map<oper, prv_num_t>  p_num={
	{'+',{81,82}},
	{'-',{81,82}},
	{'*',{41,42}},
	{'/',{41,42}},
	{'=', {100,100}},
	{'^',{32,31}}, 
    {'L',{22,21}},	//对数运算符log(x,y) ；log (x,log(x,x)) ，右边优先 
    
+    {'S',{22,21}},//定义sin函数 
+	{'C',{22,21}},//定义cos函数; 
}
printf("Err");

在运算函数calc(){}加入返回运算值

1
2
3
4
5
6
7
8
9
10
11
	case '*': return x*y;
	case '/': return x/y;
	case '^': return pow(x,y);
	case 'L': return log(y)/log(x);//对数换底公式 ,以x（先输入的数）为底数

+	case 'S': return sin(y); 		
+	case 'C': return cos(y); 

}
printf("Err");

至此，增加三角函数符号

冲突

之前我们增加的是双目运算符，遵循着 '操作数' '运算符' '操作数'

现在，我们的单目运算符，遵循 '运算符' '操作数'

一、输入模式不同的解决办法

二者输入模式不同，怎么办？难道之前辛苦搭建的程序崩塌了？

其实我们输入表达式的时候已经将完整的表达式输入了，此时我们只需要判断下一位是不是运算符，而进行对应计算，也就是预读下一位数

预读下一位数如果是数字，那么返还给键盘（模拟键盘重新输入）

预读下一位数如果不是数字，那么作为op（运算符）

所以在while(1){}处，更改以下代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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);		//scanf("%f %c",&x,&op); 3+40=;3+C0=两个符号合起来
-		operands.push(x);

	
+	scanf(" %c",&op);//预读下一位数 

+	if(isdigit(op)) {			//isdigiy判断是否是数字 //if(op是数字) #include<ctype.h>//判断字符类型 
+		ungetc(op, stdin);		//还回字符 ,还给stdin（键盘）
+		scanf("%f",&x);
+		operands.push(x);
+		continue; 
+	}

并且增加头文件#include<ctype.h>

此时输入模式不同的问题得以解决

二、运算模式不同的解决

如果是双目运算符，那么我们操作数栈的操作如下

1
2
3
4
y = operands.top();
operands.pop();
x = operands.top();
operands.pop();

由此可见，我们在运算双目运算符的时候，把y赋予栈顶值，然后弹出栈顶以获取下一个数来赋予x，之后再一次弹出栈顶

相当于一个双目运算符运算过后，弹出两个数

而如果用单目运算符运算，只需要运算一个数

也就是说，单目运算符运算过后，弹出一个数

解决办法

我们需要判断运算符是单目运算符还是双目运算符

1
2
3
4
if(history.top()是双目运算符){
	y = operands.top();
	operands.pop();
}

如果是双目运算符我们就弹多走1个栈顶

​ if(history.top()是双目运算符)我们使用if(strchr("+-*/^L",history.top()))实现

也就是在operand calc()函数中做以下操作

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
operand calc(){
	operand x, y;
	
-	y = operands.top();
-	operands.pop();

+	if(strchr("+-*/^L",history.top())){	//strchr在 "+-*/^L"找到 history.top()，如果找到返回位置，找不到返回空值【用来判断（整数和0）】 
+		y = operands.top();
+		operands.pop();
+	}
	
	x = operands.top();
	operands.pop();
	switch(history.top()){
		case '+': return x+y;
		case '-': return x-y;
		case '*': return x*y;
		case '/': return x/y;
		case '^': return pow(x,y);
		case 'L': return log(y)/log(x);//log c库的对数换底公式 
        case 'S': return sin(y);
		case 'C': return cos(y); 
	}
	printf("Err");
	return -1;
}

我们引用了strchr("+-*/^L",history.top())因此需要加入#include<string.h>

问题解决

最终代码

处理完毕后最终代码如下

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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include<stdio.h>
#include<stack>
#include<map>
#include<math.h>
typedef char oper;//运算符
typedef float operand;
std::stack<oper> history;//历史栈 
std::stack<operand> operands;

/*优先数表*/
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}},
	{'^',{32,31}}, 
	{'L',{22,21}},//对数运算符log(x,y) ；log (x,log(x,x)) ，右边优先 
	{'S',{22,21}},//定义sin函数 
	{'C',{22,21}},//定义cos函数; 
};


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

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

#include<string.h>
operand calc(){
	operand x, y;
//	if(history.top()是双目运算符){
	if(strchr("+-*/^L",history.top())){//strchr在 "+-*/^L"找到 history.top()，如果找到返回位置，找不到返回空值【用来判断（整数和0）】 
		y = operands.top();
		operands.pop();
	}
	x = operands.top();
	operands.pop();
	switch(history.top()){
		case '+': return x+y;
		case '-': return x-y;
		case '*': return x*y;
		case '/': return x/y;
		case '^': return pow(x,y);
		case 'L': return log(y)/log(x);//log c库的对数换底公式
		case 'S': return sin(y); 
		case 'C': return cos(y); 
	}
	printf("Err");
	return -1;
}


operand solve(){
	operand x, y;
	oper op;

	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(" %c",&op);//预读下一位数 
//	if(op是数字)
	if(isdigit(op)) {//isdigiy判断是否是数字 
		ungetc(op, stdin);//还回字符 ,还给stdin（键盘） 
		scanf("%f",&x);
		operands.push(x);
		continue; 
	}	
		while(prior(history.top(), op)<0){
			operands.push(calc());
			history.pop();
		}
		if(prior(history.top(),op)==0) break;
		history.push(op);
	}
	return operands.top();
}

int main(){
	printf("%g\n",solve());
	
	return 0;
}
推荐文章
站内
相关 (54.5%)
11分钟

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

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

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

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

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

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

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

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

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

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

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

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

--- over ---

其他文章
目录导航 置顶
  1. 1. 写在前面
  2. 2. 实现目标
  3. 3. 1.优化代码
  4. 4. 2.增加指数运算和对数运算符
    1. 4.1. 增加指数运算符
    2. 4.2. 增加对数运算符
  5. 5. 3.增加三角函数（单目运算符）
    1. 5.1. 冲突
    2. 5.2. 一、输入模式不同的解决办法
    3. 5.3. 二、运算模式不同的解决
  6. 6. 最终代码
请输入关键词进行搜索
  • to close