前段时间我们学习了利用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; }
|