数据结构实验之栈与队列二：一般算术表达式转换成后缀式

本文主要是介绍数据结构实验之栈与队列二：一般算术表达式转换成后缀式，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

数据结构实验之栈与队列二：一般算术表达式转换成后缀式

Description
对于一个基于二元运算符的算术表达式，转换为对应的后缀式，并输出之。

Input
输入一个算术表达式，以‘#’字符作为结束标志。

Output
输出该表达式转换所得到的后缀式。

Samples
Sample #1
Input
a*b+(c-d/e)*f#

Output
abcde/-f+

分析：

一般表达式转换后缀式的规则：

   首先，表达式有字母、加减号、乘除号、左括号和右括号组成，理清优先顺序，如果当前操作符大于栈顶操作符，则入栈；若小于，则弹出栈顶操纵符，直至满足入栈要求，或直至栈空字母：不需要入栈，直接输出加减号：优先级小于乘除号，入栈时大于左括号乘除号：优先级最大，入栈时大于左括号左括号：入栈时优先级最高（因为先算括号里面的），所以直接入栈，不需要判断，入栈后优先级最低，等待右括号的到来右括号：作用是弹出栈中遇到左括号之前的所有操作符，然后将左括号pop一下（左括号不能输出）

同级操作符的优先级：

按照运算从左至右的顺序，举个例子：当前判断的元素是’+‘，栈顶元素是’+‘或’-‘，那么栈顶元素需弹出，因为在一般表达式中栈顶元素在当前判断元素的左边，所以先运算

#include<iostream>
#include<stack>
#include<string>
using namespace std;int main()
{stack<char> mystack;string s;cin>>s;for(int i = 0;s[i]!='#';i++){if(s[i]>='a'&&s[i]<='z')cout<<s[i];else if(s[i]=='(')mystack.push(s[i]);else if(s[i]==')'){while(mystack.top()!='('){cout<<mystack.top();mystack.pop();}mystack.pop();}else if(s[i]=='+'||s[i]=='-'){while(mystack.size()!=0&&mystack.top()!='('){cout<<mystack.top();mystack.pop();}mystack.push(s[i]);}else if(s[i]=='*'||s[i]=='/'){while(mystack.size()!=0&&mystack.top()!='('&&(mystack.top()=='*'||mystack.top()=='/')){cout<<mystack.top();mystack.pop();}mystack.push(s[i]);}}while(mystack.size()!=0){cout<<mystack.top();mystack.pop();}return 0;
}