贤鱼的刷题日常(数据结构栈学习)--P1175 表达式的转换--题目详解

🏆今日学习目标：
🍀例题讲解P1175 表达式的转换
✅创作者：贤鱼
⏰预计时间：25分钟
🎉个人主页：贤鱼的个人主页
🔥专栏系列：c++
🍁贤鱼的个人社区，欢迎你的加入 贤鱼摆烂团

表达式的转换

题目描述

平常我们书写的表达式称为中缀表达式，因为它将运算符放在两个操作数中间，许多情况下为了确定运算顺序，括号是不可少的，而后缀表达式就不必用括号了。

后缀标记法：书写表达式时采用运算紧跟在两个操作数之后，从而实现了无括号处理和优先级处理，使计算机的处理规则简化为：从左到右顺序完成计算，并用结果取而代之。

例如：8-(3+2*6)/5+4 可以写为：8 3 2 6 * + 5 / - 4 +

其计算步骤为：

8 3 2 6 * + 5 / - 4 +
8 3 12 + 5 / - 4 +
8 15 5 / - 4 +
8 3 - 4 +
5 4 +
9
1
2
3
4
5
6

编写一个程序，完成这个转换，要求输出的每一个数据间都留一个空格。

输入格式

就一行，是一个中缀表达式。输入的符号中只有这些基本符号 0123456789+-*/^()，并且不会出现形如 2*-3 的格式。

表达式中的基本数字也都是一位的，不会出现形如 12 形式的数字。

所输入的字符串不要判错。

输出格式

若干个后缀表达式，第 $i+1$ 行比第 $i$ 行少一个运算符和一个操作数，最后一行只有一个数字，表示运算结果。

样例 #1

样例输入 #1

8-(3+2*6)/5+4
1

样例输出 #1

8 3 2 6 * + 5 / - 4 + 
8 3 12 + 5 / - 4 + 
8 15 5 / - 4 + 
8 3 - 4 + 
5 4 + 
9
1
2
3
4
5
6

样例 #2

样例输入 #2

2^2^3
1

样例输出 #2

2 2 3 ^ ^
2 8 ^
256
1
2
3

提示

运算的结果可能为负数，/ 以整除运算。并且中间每一步都不会超过 $2^{31}$。字符串长度不超过 $100$。

注意乘方运算 ^ 是从右向左结合的，即 2 ^ 2 ^ 3 为 2 ^ (2 ^ 3)，后缀表达式为 2 2 3 ^ ^。

其他同优先级的运算是从左向右结合的，即 4 / 2 / 2 * 2 为 ((4 / 2) / 2) * 2，后缀表达式为 4 2 / 2 / 2 *。

保证不会出现计算乘方时幂次为负数的情况，故保证一切中间结果为整数。

思路

我们首先来拆分一下题目

• 中缀表达式转换后缀表达式
• 后缀表达式逐步计算输出过程

我们来一步步解决问题
首先来处理一下中缀表达式转换
这里我们将问题继续细分
转换主要有一下几个问题

• +=/*按照什么顺序转换
• 如何处理^
• 如何处理()

众所周知，+=*/涉及一个先后顺序的问题，也就是优先度
先乘除后加减这是小学必备敲门砖
首先写一个函数处理一下顺序问题

int pd(char t){
	switch(t){
		case '+':return 1;
		case '-':return 1;
		case '*':return 2;
		case '/':return 2;
		case '^':return 3;
		case '(':return 0;
		case ')':return 0;
		default:return -1;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12

没毛病吧

从现在开始，我们默认+ -是1，*/是2

用一个op栈存一下符号，记得保证符号的顺序上升
同时遇到左括号入栈，遇到右括号输出左右括号内部符号
遇到数字直接输出就好了

8-(3+2*6)/5+4-----8 3 2 6 * + 5 / - 4 +
通过讲解一下例题解释为什么上升以及括号问题
首先入栈-
接着入栈(+*
然后入栈)
这时候输出括号内的内容，顺序应该是*+（栈内先进后出）8 3 2 6 * +get
此时栈内还有一个-，接着入栈/
注意这时候入栈了一个+，所以输出/-
最后结束的时候判断一下op，有东西全部输出就好了

因为先乘除后加减，如果此时入栈了一个*接着入栈了一个+，因为 * 在+前面运算，所以我们要弹出*，
注意！！！直到弹出到比+优先度小的符号停止弹出，
为什么等于也要弹出？
咱俩优先度一样你在前头你先走

^就是个搅屎棍，需要单独处理
也很简单，题目中说了乘方运算从右向左结合，所以我们判断优先度的时候判断下，如果栈顶和输入元素都是^，直接break，和后面的内容说再见（反正从右往左咱俩都不走等到遇到比咱小的符号一起走）

整完了吧，处理一手运算问题
我们在上一个部分输出的时候记录一个栈ls，用来储存输出第一行的结果(注意此时是倒序，第一部分结束以后我们用一个fh栈来储存结果正序)
怎么运算？
遇到数字输出到num栈，遇到符号弹出num栈栈顶元素*2进行运算，运算完入栈输出就好,完事了
确实就是这么简单，写一个运算函数就好

int js(int x,int y,char t){
	switch(t){
		case '+':return x+y;
		case '-':return x-y;
		case '*':return x*y;
		case '/':return x/y;
		case '^':return pow(x,y);
		default:return -0x3f3f3f3f;//到不了这里不用管他
	}
}
1
2
3
4
5
6
7
8
9
10

注意输出的时候注意一下输出顺序
比如我们的num栈在一波操作下应该是数字的倒叙，输出的话需要反过来输出
fh栈相当于剩下的没有处理的部分，直接输出就好了，我们这里直接输出，记录一下然后再反过来塞回去，这个不慌看代码就懂了
然后继续重复上述操作，直到fh栈为空，这里num还剩一个，刚好输出答案
结束了，休息休息

AC代码

#include
#include
#include
#include
#include
using namespace std;
stack<char>da,op;
char a;
int js(int x,int y,char t){
	switch(t){
		case '+':return x+y;
		case '-':return x-y;
		case '*':return x*y;
		case '/':return x/y;
		case '^':return pow(x,y);
		default:return -0x3f3f3f3f;
	}
}
int pd(char t){
	switch(t){
		case '+':return 1;
		case '-':return 1;
		case '*':return 2;
		case '/':return 2;
		case '^':return 3;
		case '(':return 0;
		case ')':return 0;
		default:return -1;
	}
}
stack<char>fh;
stack<int>nm;
stack<char>ls;
int wc;
void work(){
	while(cin>>a){
		if(isdigit(a)){
			da.push(a);
			char cc=da.top();
			ls.push(cc);
			cout<<cc<<" ";
		}else{
			if(pd(a)==0){
				if(a=='(') op.push(a);
				else{
					while(!op.empty()&&op.top()!='('){
						cout<<op.top()<<" ";
						ls.push(op.top());
						op.pop();
					}
					op.pop();
				}
			}

			else if(pd(a)>=1&&pd(a)<=3){
				if(!op.empty()){
					while(!op.empty()&&pd(a)<=pd(op.top())){
					if(pd(op.top())==pd(a)&&pd(a)==3) break;
					cout<<op.top()<<" ";
					ls.push(op.top());
					if(!op.empty())op.pop();
					}
				}
				op.push(a);
			}
		}
	}
	while(!op.empty()){
		ls.push(op.top());
		cout<<op.top()<<" ";
		op.pop();
	}
}
stack<int>num;
char t;
void cal(){
	while(!fh.empty()){
		t=fh.top();
		fh.pop();
		if(isdigit(t)){
			num.push(t-'0');
		}else{
			int x=num.top();
			num.pop();
			int b=num.top();
			num.pop();
			int sz=js(b,x,t);
			num.push(sz);
			while(!num.empty()){//反过来
				nm.push(num.top());
				num.pop();
			}
			while(!nm.empty()){//反过来
				cout<<nm.top()<<" ";
				num.push(nm.top());
				nm.pop();
			}
			while(!fh.empty()){//反过来
				cout<<fh.top()<<" ";
				op.push(fh.top());
				fh.pop();
			}
			while(!op.empty()){//反过来
				fh.push(op.top());
				op.pop();
			}
			cout<<endl;
		}
	}
}
int main(){
	work();
	while(!ls.empty()){//反过来
		fh.push(ls.top());
		ls.pop();
	}
	cout<<endl;
	cal();
	return 0;
}
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
111
112
113
114
115
116
117
118
119
120