中缀表达式转后缀表达式(堆栈跟队列的应用)
中缀表达式转后缀表达式(堆栈和队列的应用)
上学的时候没有好好读书,学校留下的实验作业从来就没有做过,每次要交实验报告就去找同学拷贝一份,然后自己做适当修改就提交了。
一学期下来感觉什么也没有,在家里自责之余,写点实验。
对于中缀表达式转为后缀表达式,如果考试
比如
中缀表达式:(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、最后将所有元素出队列并打印就可得到后缀表达式
上学的时候没有好好读书,学校留下的实验作业从来就没有做过,每次要交实验报告就去找同学拷贝一份,然后自己做适当修改就提交了。
一学期下来感觉什么也没有,在家里自责之余,写点实验。
对于中缀表达式转为后缀表达式,如果考试
比如
中缀表达式:(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); }