看了标题有人会问,运算符的运算实现?直接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) ;
实践方案
h.push(‘=’); // 用于判断结束,例如:若输入6=
(当栈顶的=和输入的=匹配,则结束)
输入下一个运算符op;
while(h.top()比op优先){ 栈顶元素出栈计算;}
if(h.top()==’=’&& op==’=’){结束}
h.push(op);
转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; }
|
我们根据实践方案(点击转到)
h.push(‘=’); // 用于判断结束,例如:若输入6=
(当栈顶的=和输入的=匹配,则结束)
输入下一个运算符op;
while(h.top()比op优先){
栈顶元素出栈计算;
}
if(h.top()==’=’&& op==’=’){结束}(若有等号匹配,则结束循环)
h.push(op);
转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('='); }
|
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('='); 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]()
所以我们根据
- while(h.top()比op优先){
栈顶元素出栈计算;
}
进行栈顶元素出栈计算;
所以写出以下循环
1 2 3 4 5 6 7 8 9 10 11 12 13
| while(h.top()比op优先){ 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(); }
|
接下来我们需要对比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(); operands.pop(); x = operands.top(); ………………………………………………
|
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('='); 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(); }
|
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;};
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;};
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 solute(){ 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",solute()); return 0; }
|