[TOC]
【案例分析】
已知表达式=操作数+操作符，其中操作数是123这样的数字，操作符是运算符和界限符（如括号）。
做实验前先理清：
1.四则运算的优先性：先乘除后加减，括号优先，从左到右。
2.中缀表达式转换成后缀表达式：
- 遇到数字就直接输出到后缀表达式中，遇到操作符就判断其优先级，并将其压入栈中。
- 如果栈顶元素的优先级大于等于当前操作符，则先将栈顶元素弹出并输出到后缀表达式中，再将当前操作符压入栈中。
- 如果遇到了左括号，则直接将其压入栈中，如果遇到了右括号，则弹出栈中的元素，直到遇到了左括号为止，并将这些元素输出到后缀表达式中。
- 最后，将栈中剩余的元素依次弹出，并输出到后缀表达式中。
3.后缀表达式计算：遍历后缀表达式，如果遇到数字则直接入栈，如果遇到操作符，则弹出栈顶的两个元素，进行计算后将结果入栈。最后留在栈里的就是最终结果。
【实验过程】
1.定义
该段定义了结构体element，存放操作数num和操作符op，供stack和queue容器随时进出。
并在里面定义了布尔变量flag，用于识别中缀表达式当前字符是操作数还是操作符。
最后调用了map用于判断运算符的优先级。
1
2
3
4
5
6
7
8
9
10
| struct element{
double num; //存放操作数
char op; //存放操作符
bool flag; //true 表示操作数，false 表示操作符
};
string str; //输入的中缀表达式
stack<element>s; //操作符栈
queue<element>q; //后缀表达式队列
map<char,int>op; //判断优先级,字符到整型的映射
|
2.用map判断优先级
1<2，先乘除后加减（括号另外考虑）
1
2
3
4
| map<char,int>op; //判断优先级,字符到整型的映射
op['+'] = op['-'] = 1;
op['*'] = op['/'] = 2;
|
temp.op定义为操作符栈的当前操作符
s.top().op是操作符栈的栈顶操作符
1
2
3
4
5
6
7
| while(!s.empty() && op[temp.op]<=op[s.top().op]){ //当前操作符栈的优先级低于栈顶，并且栈不为空
q.push(s.top());
s.pop();
}
s.push(temp);
index++;
}
|
3.处理多位数问题
一位数的方法：检测到当前读取的字符是“数字”，temp转为1，表示操作数，把字符转化成阿拉伯数并进队列。
多位数的方法：读取到第一个数字后进行循环判断，一直到读取完毕或者遇到不是数字的操作符，若进入循环，那么此次读入的数为 前一个 * 10 + 现在的数字
1
2
3
4
5
6
7
8
9
| if(str[index]>='0' && str[index]<='9'){ //当前读取的是数字
temp.flag = true;
temp.num = str[index++]-'0' ; //转化成数字
while(index>str.size() && str[index]>='0' && str[index]<'9'){ //处理多位数
temp.num = temp.num*10 + str[index]-'0';
index++; //下一位
}
q.push(temp);//进后缀表达式队列
}
|
4.处理括号问题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| if(str[index] =='(') {
s.push(temp);//对左括号，直接进操作符栈
index++; //下一位
continue;
}else if(str[index]==')'){
while(s.top().op!='('){ //为右括号匹配左括号
q.push(s.top());
s.pop(); //出栈元素加入到队列
}
s.pop();//将左括号出栈
index++;
continue;
}
temp.flag=false;
temp.op=str[index];
|
5.输入：去掉空格
基于map
1
2
3
4
5
| for(int i = 0; i < str.size(); i++) { //去掉空格
if(str[i] == ' ') {
str.erase(str.begin() + i);
}
}
|
【完整代码】
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
98
99
100
101
102
103
104
105
106
107
108
| #include<iostream>
using namespace std;
#include<queue>
#include<stack>
#include<string>
#include<map>
struct element{
double num; //存放操作数
char op; //存放操作符
bool flag; //true 表示操作数，false 表示操作符
};
string str; //输入的中缀表达式
stack<element>s; //操作符栈
queue<element>q; //后缀表达式队列
map<char,int>op; //判断优先级,字符到整型的映射
int suffix(){
//将中缀表达式str转换成后缀表达式
element temp;
int index = 0; //当前位置
while(index < str.size()) {
if(str[index]>='0' && str[index]<='9'){ //当前读取的是数字
temp.flag = true;
temp.num = str[index++]-'0' ; //转化成数字
while(index<str.size() && str[index]>='0' && str[index]<'9'){ //处理多位数
temp.num = temp.num*10 + str[index]-'0';
index++; //下一位
}
q.push(temp);//进后缀表达式队列
}else{
temp.flag = false; //当前读取的是符号
temp.op = str[index];
if(str[index] =='(') {
s.push(temp);//对左括号，直接进操作符栈
index++; //下一位
continue;
}else if(str[index]==')'){
while(s.top().op!='('){ //为右括号匹配左括号
q.push(s.top());
s.pop(); //出栈元素加入到队列
}
s.pop();//将左括号出栈
index++;
continue;
}
temp.flag=false;
temp.op=str[index];
while(!s.empty() && op[temp.op]<=op[s.top().op]){ //当前操作符栈的优先级低于栈顶，并且栈不为空
q.push(s.top());
s.pop();
}
s.push(temp);
index++;
}
}
while(!s.empty()){
q.push(s.top());
s.pop();
}
return 1;
}
double cal(){
double top1,top2;
element cur,temp;
while(!q.empty()){ //后缀表达式队列从头依次读取
cur = q.front(); //cur记录队首
q.pop(); //出队列
if(cur.flag==true){
s.push(cur); //对操作数入栈
}else{//遇到操作符，对栈里的操作数出栈
top1 = s.top().num;
s.pop();
top2 = s.top().num;
s.pop();
temp.flag=true; //记录运算结果
if(cur.op == '+') temp.num = top2+top1;
if(cur.op == '-') temp.num = top2-top1;
if(cur.op == '*') temp.num = top2*top1;
if(cur.op == '/') temp.num = top2/top1;
s.push(temp);//计算结果进栈
}
}
return s.top().num;
}
int main(){
op['+'] = op['-'] = 1;
op['*'] = op['/'] = 2;
getline(cin,str);
while(!s.empty()){
s.pop(); //清空
}
for(int i = 0; i < str.size(); i++) { //去掉空格
if(str[i] == ' ') {
str.erase(str.begin() + i);
}
}
suffix();
cout<<"计算结果为："<<cal()<<endl;
return 0;
}
|