前段时间我们学习了利用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;};
std::map<oper, prv_num_t> p_num={
{'+',{81,82}},
{'-',{81,82}},
{'*',{41,42}},
{'/',{41,42}},
{'=',{100,100}}
};
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('=');
while(1){
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;
case '-': return x-y;
case '*': return x*y;
case '/': return 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;};
std::map<oper, prv_num_t> p_num={
{'+',{81,82}},
{'-',{81,82}},
{'*',{41,42}},
{'/',{41,42}},
{'=',{100,100}}
};
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('=');
while(1){
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}}
}
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);
}
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);
+ 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){
- scanf("%f %c",&x,&op);
- operands.push(x);
+ scanf(" %c",&op);
+ if(isdigit(op)) {
+ ungetc(op, 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())){
+ 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);
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;};
std::map<oper, prv_num_t> p_num={
{'+',{81,82}},
{'-',{81,82}},
{'*',{41,42}},
{'/',{41,42}},
{'=',{100,100}},
{'^',{32,31}},
{'L',{22,21}},
{'S',{22,21}},
{'C',{22,21}},
};
int prior(oper op1, oper op2){
return p_num[op1].left - p_num[op2].right;
}
#include<string.h>
operand calc(){
operand x, y;
if(strchr("+-*/^L",history.top())){
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);
case 'S': return sin(y);
case 'C': return cos(y);
}
printf("Err");
return -1;
}
operand solve(){
operand x, y;
oper op;
history.push('=');
while(1){
scanf(" %c",&op);
if(isdigit(op)) {
ungetc(op, 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;
}
|
