因为操作数在后缀表达式中它们的顺序与中缀表达式一致，所以操作数不需要进行特殊处理，所以遇到数字就输出，遇到符号就经过处理再输出
所以需要用一个存储结构存符号
为什么用栈存储：
要利用后进先出的特性
出栈也就是加入到后缀表达式中，一部分一部分处理，处理完一部分，要处理他邻近的那部分，也就是需要操作最近加入的运算符，而不是最开始加入的（那样离太远了），后进先出刚好符合
比如1+1+2*(3+5)-1/2
先处理括号内的这部分，处理完括号外的那部分，再处理*，后处理两个加号
处理符号概述：
从左至右依次遍历中缀表达式，一个字符一个字符的处理
运算符都要入栈处理，而后续输出的运算符也只从栈内取（保证取的运算符都是经过处理的）
（这里的栈内处理，实则不用在栈内操作运算符，而是通过于当前运算符做比较来当作处理）
什么时候输出：运算优先级较高时输出（因为要保证优先级高的先运算的原则）
（但由于输出的运算符只从栈内取，所以这里的输出具体来说是：运算优先级高于当前处理运算符时输出）
具体实现步骤：
因为：
括号内的运算符优先级最高，而左括号是运算括号内的起始标志，所以，一旦遇到左括号，需要存下，让括号内的运算符优先运算（也就说明了，左括号的优先级最低）
左括号消除标志是出现右括号
所以：
遇到左括号时，直接入栈，先存着
遇到右括号时，直接一直出栈，直到遇到左括号，把左括号也一并出栈
因为后缀表达式无括号这个运算符，所以只需要删除，不需要把括号放入后缀表达式
如果遇到其他运算符，
若栈空，则直接入栈
若栈非空：
1、如果当前运算符优先级高于栈顶运算符，则入栈
2、如果当前运算符优先级低于栈顶运算符，则将高于当前运算符的栈内元素全出栈，最后将当前运算符入栈
3、遍历完，把剩余栈内运算符全部输出
注意
不论前缀还是后缀表达式，都是从左至右运算，所以当遇到两个优先级相同的运算符时，先出现的运算符优先级高于后出现的，所以当前运算符优先级较低，这种情况归于1，用=来表示
代码
构造栈
#include <iostream>
#include<string>
using namespace std;
#define MAXQSIZE 100
typedef struct {
char *base; // 栈底指针
char *top; // 栈顶指针
int stacksize;
} SqStack;
// 初始化栈
void InitStack(SqStack &S) {
S.base = new char[MAXQSIZE];
if (!S.base) {
cout << "存储分配失败" << endl;
return;
}
S.top = S.base; // 栈顶指针初始化为栈底
S.stacksize = MAXQSIZE; // 设置栈的大小
}
// 判断栈空
bool isEmpty (SqStack &S)
{
if (S.top == S.base) {
return true;
}
return false;
}
// 入栈
void Push(SqStack &S, char elem) {
// 检查栈满
if (S.top - S.base >= S.stacksize) {
cout << "栈已满" << endl;
return;
}
*S.top++ = elem; // 推入元素
}
// 出栈
void Pop(SqStack &S, char &elem) {
if (!isEmpty(S)) {
elem = *--S.top;
} else {
cout << "栈空，无法弹出元素。" << endl;
}
}
// 获取栈顶元素
char getHead(SqStack &S) {
return *(S.top - 1);
}预备函数
// 判断是否为运算符
bool isOperator(char elem) {
return (elem == '+' || elem == '-' || elem == '*' || elem == '/' || elem == '(' || elem == ')');
}
// 得到优先级
int getPrecede(char elem) {
if (elem == '(')
return 0;
if (elem == '+' || elem == '-')
return 1;
if (elem == '*' || elem == '/')
return 2;
return 0;
}主要函数
void transform(string expressions)
{
// 用于存运算符
SqStack S;
InitStack(S);
// 用于存出栈的元素
char elem = '0';
// 开始从左到右处理
for (int i = 0; i < expressions.length(); i++)
{
char expression = expressions[i];
if (expression == '(')
{
// 左括号直接入栈,优先级最低
Push(S,expression);
} else if (expression == ')')
{
// 右括号直接出栈直到遇到到左括号
Pop(S,elem);
while (elem != '(' && !isEmpty(S))
{
cout<<elem<<" ";
Pop(S,elem);
}
} else {
// 其他字符
// 数字直接输出
if (!isOperator(expression))
{
cout<<expression<<" ";
} else {
// 是运算符
// 如果栈空，直接入栈
if (isEmpty(S))
{
Push(S,expression);
continue;
}
// 栈非空
// 如果当前运算符优先级大于栈顶运算符，则入栈
if (getPrecede(expression) > getPrecede(getHead(S)))
{
Push(S,expression);
} else {
// 当前运算符优先级低于栈顶运算符，一直输出，直到当前运算符优先级大于栈顶运算符，入栈
// 因为从左到右运算，所以先出现的运算符优先级高于后出现的，这里用“=”表示
while (getPrecede(expression) <= getPrecede(getHead(S)) && !isEmpty(S))
{
Pop(S,elem);
cout<<elem<<" ";
}
// 当前运算符优先级大于栈顶运算符，入栈
Push(S,expression);
}
}
}
}
// 处理栈内剩余运算符
while (!isEmpty(S))
{
Pop(S,elem);
cout<<elem<<" ";
}
}测试
int main()
{
// 9+(3-1)*3+1/2
// 9 3 1 - 3 * + 1 2 / +
string expressions;
cout<<"输入表达式"<<endl;
cin>>expressions;
cout<<"后缀表达式为："<<endl;
transform(expressions);
return 0;
}