逆波兰（转载）

发表于 | 更新于: | 分类于 |
字数统计: 899 字 | 阅读时长 ≈ 4 分钟

输入有两行,第一行为逆波兰式的结果,第二行为输入表达式的正确计算结果。逆波兰式中相邻的数字或运算符之间不用输出空格

保证表达式计算的合理性,不需判断除零等情况

表达式的计算遵循同级运算从左向右,先乘除后加减

样例输入:

2+1*3+4

样例输出:

213*+4+

9

解题思路:

首先定义两个栈,一个临时存储运算符S1,另一个作为输入逆波兰式S2的存放栈

在S1中先放入一个‘#’运算符调整为最低,方便运算符的比较

然后开始从表达式中取值

(1)若取出的是表达式,直接将其放置到S2存放栈中

(2)若取出的运算符,则将该元素与S1栈顶元素进行比较,如果该运算符优先级大于(小于或者等于都不行)S1栈顶运算符优先级,则将该运算符进S1栈,否则,将S1栈栈的栈顶运算符弹出,送入S2栈,之后再和S1现在的栈顶比较,直到运算符优先级大于栈顶为止后，将该运算符送入S1中

(3)重复上述1-2步,直到所有输入字符都处理完毕

(4)将S1中的所有符号除‘#’以外都push到S2中

这样我们就得到了一个逆波兰序列

计算结果:

将逆波兰式依次堆入一个栈中,如果堆入的是一个运算符,取出栈里的头两个操作数(必为数字),将其执行运算符所代表的操作后

(一般是 下 运算符 上),将结果放回栈中,最后剩下的栈顶就是结果

代码如下:

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
109
110
am>
#include <stack>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
 
int precede(char a) {
	switch (a)
	{
	case '+':
		return 1;
	case '-':
		return 1;
	case '*':
		return 2;
	case '/':
		return 2;
	case '#':
		return 0;
	}
}
 
bool comparePrecde(char a,char b) {  //前表达式中的元素 后栈中的元素
	int pre_a = precede(a);
	int pre_b = precede(b);
 
	if (pre_a > pre_b) {
		return true;
	}
	else {
		return false;
	}
}
 
int main() {
 
	stack<char> numStack;  //用来存储数字
	stack<char> exprStack;  //用来存储表达式
	stack<char> tempStack;  //暂时存储
	stack<float> resStack;  //用来存储计算结果
	vector<char> opVec;   //正序输出
	exprStack.push('#');   
 
	string buffer;   //用来读取中缀表达式
	cin >> buffer;
	for (int i = 0; i < buffer.size(); ++i) {   //数字和运算符分离
		if (isdigit(buffer[i])) {
			numStack.push(buffer[i]);
		}
		else {
			while (!comparePrecde(buffer[i], exprStack.top())) {
				numStack.push(exprStack.top());
				exprStack.pop();
			}
			exprStack.push(buffer[i]);
		}
	}
	
	while (exprStack.top() != '#') {     //剩余的元素压入栈
		numStack.push(exprStack.top());
		exprStack.pop();
	}
	
	while (!numStack.empty()) {
		opVec.push_back(numStack.top());
		tempStack.push(numStack.top());
		numStack.pop();
	}
	
	reverse(opVec.begin(), opVec.end());  //输出逆波兰式列
	for (auto x : opVec) {
		cout << x;
	}
 
	cout << endl;
	//计算结果
	while (!tempStack.empty()) {
		if (isdigit(tempStack.top())) {
			resStack.push((float)(tempStack.top() - '0'));  //char to int
			tempStack.pop();
		}
		else {
			char expr = tempStack.top();
			tempStack.pop();
			float a = resStack.top();
			resStack.pop();
			float b = resStack.top();
			resStack.pop();
 
			switch (expr)
			{
			case'+':
				resStack.push(b + a);
				break;
			case'-':
				resStack.push(b - a);
				break;
			case'*':
				resStack.push(b * a);
				break;
			case'/':
				resStack.push(b / a);
				break;
			}
		}
	}
	cout << resStack.top() << endl;   //输出结果
	return 0;
}

————————————————
版权声明：本文为CSDN博主「alex1997222」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/alex1997222/article/details/82764166