D. DS栈—波兰式，逆波兰式（dsoj c++）

83 阅读 0 评论 55 点赞

我是靠谱客的博主迷路老虎，这篇文章主要介绍D. DS栈—波兰式，逆波兰式（dsoj c++），现在分享给大家，希望可以做个参考。

题目描述

表达式有三种表示方法，分别为：

前缀表示(波兰式)：运算符+操作数1+操作数2

中缀表示：操作数1+运算符+操作数2

后缀表示(逆波兰式)：操作数1+操作数2+运算符

例如：a +b * (c -d ) - e/f

波兰式：-+a*b-cd/ef （运算符在操作数的前面，用递归计算波兰式）

中缀式：a+b*c-d-e/f

逆波兰式：abcd-*+ef/- （运算符在操作数的后面，用栈计算逆波兰式）

中缀表示就是原表达式去掉扣号。

根据表达式求波兰式、逆波兰式都是教材第三章表达式求值的思想。

求波兰式，需要操作数栈(注意不是计算结果入栈，有计算式入栈)，运算符栈。区别在于从后往前扫描表达式，‘(’ 换成')','('换成‘)’。栈顶运算符优先级>新读入运算符优先级出栈，教材第三章表3.1中的相同运算符优先级>（从左往右计算）改为<，例如栈顶为‘+‘，新读入的为‘+’，则栈顶优先级<新读入的优先级。

求逆波兰式，只需要运算符栈。操作数直接输出，操作符按表3.1优先级顺序出栈，输出。

输入表达式，求其波兰式和逆波兰式。

输入

测试次数

每组测试数据一行，一个合法表达式

输出

对每组测试数据，输出两行

第一行，表达式的波兰表示

第二行，表达式的逆波兰表示

不同组测试数据间以空行分隔。

输入样例1 ：

2
4+2*3-10/5
12+3*5+(2+10)*5

输出样例1：

- + 4 * 2 3 / 10 5
4 2 3 * + 10 5 / -

+ + 12 * 3 5 * + 2 10 5
12 3 5 * + 2 10 + 5 * +

复制代码

#include <iostream>
#include <stack>
#include <cstring>
//#include<vector>
using namespace std;
int main()
{
int t;
cin >> t;
while (t--)
{
//前缀（波兰式）从右往左读入
stack<char>sw; //存放操作符
string st; //输入的中缀计算式
string an[1000]; //存输出
cin >> st;
int k=0;
int len= st.length();
for (int i = len-1; i>=0; i--)
{
if (st[i] >= '0'&&st[i]<='9') //如果是数字则直接存进输出
{
string temp = "";
temp = st[i] + temp;
-- i;
while(st[i]>= '0'&&st[i]<= '9') //如果前一个还是数字，则继续进temp里
{
temp = st[i] + temp;
--i;
}
++i;
an[k]=temp;
k++;
continue;
}
if (st[i] == '(') //碰上左括号说明括号里内容输完了
{
while (sw.top() != ')') //将操作符弹出进输出数组里
{
an[k]=sw.top();
k++;
sw.pop();
}
sw.pop();
}
else
{
if (st[i] == ')') //如果碰上右括号就压栈
{
sw.push(st[i]);
}
//如果是+-*/的操作符，就按序比较
while (st[i] == '+' || st[i] == '-' || st[i] == '*' || st[i] == '/')
{
if (sw.empty()) //如果栈是空的，则无需比较，直接压栈
{
sw.push(st[i]);
break;
}
//如果栈不为空，则将当前操作符与栈顶操作符比较优先级，如果低于栈顶操作符，则进输出数组
if (((st[i] == '+' && (sw.top() == '/' || sw.top() == '*' )) || (st[i] == '-' && (sw.top() == '*'
|| sw.top() == '/')) ))
{
an[k]=sw.top();
k++;
sw.pop();
}
//否则，则进栈
else
{
sw.push(st[i]);
break;
}
}
}
}
while (!sw.empty()) //将栈中的操作符传入输出数组
{
an[k]=sw.top();
k++;
sw.pop();
}
for (int i = k - 1; i >= 0; --i) //输出
{
cout << an[i];
if (i) cout << ' ';
else puts("");
}
//后缀（逆波兰式）从左往右读 思路与前缀相似
stack<char>s;
string str;
string ans[1000];
//vector<char> ans;
str = st;
k=0;
len= str.length();
for (int i = 0; i < len; i++)
{
if (str[i] >= '0'&&str[i]<='9')
{
int temp=str[i]-'0';
int j=i+1;
while(str[j]>= '0'&&str[j]<= '9')
{
temp=temp*10+(str[j]-'0');
j++;
}
i=j-1;
ans[k]=to_string(temp);
k++;
}
if (str[i] == ')')
{
while (s.top() != '(')
{
ans[k]=s.top();
k++;
s.pop();
}
if (s.top() == '(')
{
s.pop();
}
}
else
{
if (str[i] == '(')
{
s.push(str[i]);
}
while (str[i] == '+' || str[i] == '-' || str[i] == '*' || str[i] == '/')
{
if ((s.empty()) || (s.top() == '(') || ((str[i] == '*' && (s.top() == '/' || s.top() == '+' || s.top() == '-')) || (str[i] == '/' && (s.top() == '*' || s.top() == '+' || s.top() == '-')) || (str[i] == '+' && (s.top() == '-')) || (str[i] == '-' && (s.top() == '+'))))
{
s.push(str[i]);
break;
}
else
{
while (!s.empty())
{
ans[k]=s.top();
k++;
s.pop();
}
}
}
}
}
while (!s.empty())
{
ans[k]=s.top();
k++;
s.pop();
}
for (int i = 0; i < k; i++)
{
cout << ans[i];
if (i != k - 1) cout << ' ';
}
if (t){
puts("");
puts("");
}
}
}

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
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
#include <iostream>
#include <stack>
#include <cstring>
//#include<vector>
using namespace std;
int main()
{
int t;
cin >> t;
while (t--)
{
//前缀（波兰式）从右往左读入
stack<char>sw; //存放操作符
string st; //输入的中缀计算式
string an[1000]; //存输出
cin >> st;
int k=0;
int len= st.length();
for (int i = len-1; i>=0; i--)
{
if (st[i] >= '0'&&st[i]<='9') //如果是数字则直接存进输出
{
string temp = "";
temp = st[i] + temp;
-- i;
while(st[i]>= '0'&&st[i]<= '9') //如果前一个还是数字，则继续进temp里
{
temp = st[i] + temp;
--i;
}
++i;
an[k]=temp;
k++;
continue;
}
if (st[i] == '(') //碰上左括号说明括号里内容输完了
{
while (sw.top() != ')') //将操作符弹出进输出数组里
{
an[k]=sw.top();
k++;
sw.pop();
}
sw.pop();
}
else
{
if (st[i] == ')') //如果碰上右括号就压栈
{
sw.push(st[i]);
}
//如果是+-*/的操作符，就按序比较
while (st[i] == '+' || st[i] == '-' || st[i] == '*' || st[i] == '/')
{
if (sw.empty()) //如果栈是空的，则无需比较，直接压栈
{
sw.push(st[i]);
break;
}
//如果栈不为空，则将当前操作符与栈顶操作符比较优先级，如果低于栈顶操作符，则进输出数组
if (((st[i] == '+' && (sw.top() == '/' || sw.top() == '*' )) || (st[i] == '-' && (sw.top() == '*'
|| sw.top() == '/')) ))
{
an[k]=sw.top();
k++;
sw.pop();
}
//否则，则进栈
else
{
sw.push(st[i]);
break;
}
}
}
}
while (!sw.empty()) //将栈中的操作符传入输出数组
{
an[k]=sw.top();
k++;
sw.pop();
}
for (int i = k - 1; i >= 0; --i) //输出
{
cout << an[i];
if (i) cout << ' ';
else puts("");
}
//后缀（逆波兰式）从左往右读 思路与前缀相似
stack<char>s;
string str;
string ans[1000];
//vector<char> ans;
str = st;
k=0;
len= str.length();
for (int i = 0; i < len; i++)
{
if (str[i] >= '0'&&str[i]<='9')
{
int temp=str[i]-'0';
int j=i+1;
while(str[j]>= '0'&&str[j]<= '9')
{
temp=temp*10+(str[j]-'0');
j++;
}
i=j-1;
ans[k]=to_string(temp);
k++;
}
if (str[i] == ')')
{
while (s.top() != '(')
{
ans[k]=s.top();
k++;
s.pop();
}
if (s.top() == '(')
{
s.pop();
}
}
else
{
if (str[i] == '(')
{
s.push(str[i]);
}
while (str[i] == '+' || str[i] == '-' || str[i] == '*' || str[i] == '/')
{
if ((s.empty()) || (s.top() == '(') || ((str[i] == '*' && (s.top() == '/' || s.top() == '+' || s.top() == '-')) || (str[i] == '/' && (s.top() == '*' || s.top() == '+' || s.top() == '-')) || (str[i] == '+' && (s.top() == '-')) || (str[i] == '-' && (s.top() == '+'))))
{
s.push(str[i]);
break;
}
else
{
while (!s.empty())
{
ans[k]=s.top();
k++;
s.pop();
}
}
}
}
}
while (!s.empty())
{
ans[k]=s.top();
k++;
s.pop();
}
for (int i = 0; i < k; i++)
{
cout << ans[i];
if (i != k - 1) cout << ' ';
}
if (t){
puts("");
puts("");
}
}
}