#include <iostream>using namespace std;#define MaxSize 50typedef char ElemType;typedef struct{ElemType data[MaxSize];int top;} SqStack;//栈初始化void initStack(SqStack &S){S.top = -1;}//判断栈空bool stackEmpty(SqStack S){if(S.top == -1)return true;elsereturn false;}//入栈bool push(SqStack &S,ElemType x){if(S.top == MaxSize-1)return false;S.top++;S.data[S.top] = x;return true;}//出栈bool pop(SqStack &S,ElemType &x){if(S.top == -1)return false;x = S.data[S.top--];return true;}//读栈顶元素bool getTop(SqStack S,ElemType &x){if(S.top == -1)return false;x = S.data[S.top];return true;}//中缀转后缀函数bool reversePolish(ElemType str[],int length){SqStack S;//声明符号栈initStack(S);//符号栈初始化string polish;//声明后缀表达式字符串int i;//i是遍历中缀表达式的下标for(i=0; i<length; i++){switch(str[i]){case '(':push(S,str[i]);//左括号直接入栈break;case ')'://遇到右括号，不入栈，弹出栈中（ 上面的所有符号并加入后缀表达式，最后把左括号弹出ElemType topElem,x;getTop(S,topElem);//读取栈顶元素while(topElem != '('){pop(S,x);polish+=x;if(stackEmpty(S)){//cout<<"栈空！"<<endl;break;}elsegetTop(S,topElem);}pop(S,x);break;case '+':case '-'://先弹出比自己级别高的或者与自己同级的运算符,加入后缀表达式//cout<<"是+或者-，入栈"<<endl;if(!stackEmpty(S))//如果栈非空{ElemType topElem;getTop(S,topElem);//读取栈顶元素while(topElem == '+' || topElem == '-' || topElem == '*' || topElem == '/'){ElemType x;pop(S,x);polish+=x;if(stackEmpty(S)){//cout<<"栈空！"<<endl;break;}elsegetTop(S,topElem);}}push(S,str[i]);//弹出后自己入栈break;case '*':case '/'://先弹出比自己级别高的或者与自己同级的运算符,加入后缀表达式//cout<<"是*或者/，入栈"<<endl;if(!stackEmpty(S))//如果栈非空{ElemType topElem;getTop(S,topElem);//读取栈顶元素while(topElem == '*' || topElem == '/'){ElemType x;pop(S,x);polish+=x;if(stackEmpty(S)){// cout<<"栈空！"<<endl;break;}elsegetTop(S,topElem);}}push(S,str[i]);//弹出后自己入栈break;default:polish+=str[i];}}while(!stackEmpty(S)){ElemType x;pop(S,x);polish+=x;}cout<<"后缀表达式为："<<endl;cout<<polish;return true;}int main(){ElemType str[MaxSize];int length;cout<<"请输入中缀字符串长度：";cin>>length;cout<<"请输入中缀表达式："<<endl;cin>>str;cout<<"您输入的中缀表达式为：";cout<<str<<endl;reversePolish(str,length);return 0;}
代码有个缺点，输入的时候必须输入要测试的中缀字符串长度，我懒得改了~~其他应该还是没问题的
