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

68 阅读 0 评论 45 点赞

我是靠谱客的博主迷路老虎，最近开发中收集的这篇文章主要介绍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("");
}
}
}

本次题目谢谢chc和zhw的帮助哈哈哈哈哈哈！