中缀表达式转后缀表达式（堆栈和队列的应用）
上学的时候没有好好读书，学校留下的实验作业从来就没有做过，每次要交实验报告就去找同学拷贝一份，然后自己做适当修改就提交了。
一学期下来感觉什么也没有，在家里自责之余，写点实验。
对于中缀表达式转为后缀表达式，如果考试
比如
中缀表达式：（8+9*10）-4/2+3
其转化思路：
1、将每个操作符对应的两个操作数用括号括上（（（8+（9*10））-（4/2））+3）
2、将操作符移到对应的括号外（（（8（910*）+）（42）/）-3）+
3、去掉括号即可 8910*+42/-3+
如果要用数据结构中的栈和队列实现
1、用一个字符串存储表达式
2、扫描字符串。当其为0--9时直接入队列，遇到左括号入栈，操作符级别 #：0用于最后判断，+ -：1,* /:2
3、首先向堆中放一个#，当进入堆的操作符的级别不小于栈顶操作符的优先级，则入栈，否则弹出栈顶元素并进入队列，将下一个操作符压入栈。
4、一直循环直到将所有字符处理完
5、最后将所有元素出队列并打印就可得到后缀表达式

#include<stdio.h>#define Max 20//自定义栈template<class Elem>struct Stack{int top;Elem *p;int size;};template<class Elem>void Set_Ssize(Stack<Elem> &sta,int n){sta.size=n;sta.p=new Elem[sta.size];sta.top=0;}template<class Elem>void Push(Stack<Elem> &sta,Elem item){sta.p[sta.top++]=item;}template<class Elem>void Pop(Stack<Elem> &sta,Elem &e){e=sta.p[--sta.top];}template<class Elem>bool IsEmpty(Stack<Elem> &sta){return sta.top==0;}template<class Elem>bool IsFull(Stack<Elem> &sta){return sta.top==sta.size;}//自定义队列template<class Elem>struct MyQuene{int front;int rear;Elem *p;int size;};template<class Elem>void Set_Qsize(MyQuene<Elem> &Q,int n){Q.size=n;Q.front=0;Q.rear=0;Q.p=new Elem[Q.size];}template<class Elem>void AddQuene(MyQuene<Elem> &Q,Elem item){Q.p[Q.rear++]=item;if(Q.rear==Q.size)Q.rear=0;}template<class Elem>void DeleteQuene(MyQuene<Elem> &Q,Elem& e){e=Q.p[Q.front++];if(Q.front==Q.size)Q.front=0;}template<class Elem>Elem GetTop(Stack<Elem> &sta){return sta.p[sta.top-1];}template<class Elem>bool IsEmpty(MyQuene<Elem> &Q){return Q.front==Q.rear;}template<class Elem>bool IsFull(MyQuene<Elem> &Q){int len=Q.front<Q.rear?Q.rear-Q.front:Q.rear-Q.front+Q.size;return len==Q.size-1;}//定义运算符的优先级int GetPrecedence(char a){switch(a){case '#':return 0;case '+':case '-':return 1;case '*':case '/':return 2;case '^':return 3;default:break;}}template<class Elem>void Middle_Bhind(Stack<Elem> &st,MyQuene<Elem>&Mq,char*A,int n){//中缀表达式转为后缀表达式(自己的实验需求)Set_Ssize(st,n);Set_Qsize(Mq,n+1);char tem;int i=0;Push(st,'#');do{if((A[i]>='0'&&A[i]<='9')||(A[i]>='A'&&A[i]<='Z')||(A[i]>='a'&&A[i]<='z'))AddQuene(Mq,A[i]);else if(A[i]=='(')Push(st,A[i]);else if(A[i]==')'){while(GetTop(st)!='('){Pop(st,tem);AddQuene(Mq,tem);}Pop(st,tem);}else if(GetTop(st)=='(')Push(st,A[i]);else{while(GetPrecedence(A[i])<=GetPrecedence(GetTop(st))){Pop(st,tem);AddQuene(Mq,tem);}Push(st,A[i]);}i++;}while(A[i]!='\0');while(GetTop(st)!='#'){Pop(st,tem);AddQuene(Mq,tem);}while(!IsEmpty(Mq)){DeleteQuene(Mq,tem);printf("%c",tem);}putchar('\n');}void main(){char str[Max];Stack<char> st;MyQuene<char>Mq;printf("请输入中缀表达式:");gets(str);printf("后缀表达式:");Middle_Bhind(st,Mq,str,Max);}