数据结构中缀式中缀表达式改后缀表达式并求值

《数据结构》课程设计报告课程设计题目：中缀表达式改后缀表达式并求值一.实验目的·掌握栈的特征及基本操作，如入栈、出栈等，栈的顺序存储结构和链式存储结构的实现，以便在实际问题中灵活应用。·掌握栈的典型应用——中缀表达式转后缀表达式，并利用后缀表达式求值。二.实验内容（一）中缀表达式转后缀表达式的方法：1.遇到操作数：直接输出（添加到后缀表达式中）2.栈为空时，遇到运算符，直接入栈3.遇到左括号：将其入栈4.遇到右括号：执行出栈操作，并将出栈的元素输出，直到弹出栈的是左括号，左括号不输出。5.遇到其他运算符：加减乘除：弹出所有优先级大于或者等于该运算符的栈顶元素，然后将该运算符入栈6.最终将栈中的元素依次出栈，输出。（二）三.实验分析程序源码（要求对每个函数及主要代码加上注释语句），源码出处。////main.c//后缀表达式求值////Createdby颜彦闻on14/12/2.//Copyright(c)2014年颜彦闻.Allrightsreserved.//#includestdio.h#includestdlib.h#defineStackSize100#defineQueueSize100typedefcharDataType;typedefstruct{chardata[100];intfront,rear;}SeqQueue;//定义队列类型voidInitQueue(SeqQueue*Q)//初始化队列{Q-front=0;Q-rear=0;}intQueueEmpty(SeqQueueQ)//判空{returnQ.rear==Q.front;}voidEnQueue(SeqQueue*Q,DataTypex)//元素入队列函数{if((Q-rear+1)%QueueSize==Q-front)printf(Queueoverflow);else{Q-data[Q-rear]=x;Q-rear=(Q-rear+1)%QueueSize;}}DataTypeDeQueue(SeqQueue*Q){charx;if(QueueEmpty(*Q))return0;else{x=Q-data[Q-front];Q-front=(Q-front+1)%QueueSize;returnx;}}//栈的相关操作typedefstruct{DataTypedata[100];inttop;}SeqStack;voidInitStack(SeqStack*S)//栈的初始化{S-top=-1;}voidPush(SeqStack*S,DataTypex)//进栈函数{if(S-top==StackSize-1)printf(stackoverflow);else{S-top=S-top+1;S-data[S-top]=x;}}DataTypePop(SeqStack*S)//退栈顶指针函数{if(S-top==-1){printf(stackunderflow);return0;}elsereturnS-data[S-top--];}DataTypeGetTop(SeqStackS)//取栈顶元素{if(S.top==-1){printf(stackempty);return0;}elsereturnS.data[S.top];}intPriority(DataTypeop)//求运算符优先级函数{switch(op){case'(':case'#':return0;case'-':case'+':return1;case'*':case'/':return2;}return-1;}voidCTPostExp(SeqQueue*Q){SeqStackS;charc,t;InitStack(&S);Push(&S,'#');do{c=getchar();switch(c){case'':break;case'1':case'2':case'3':case'4':case'5':case'6':case'7':case'8':case'9':EnQueue(Q,c);break;case'(':Push(&S,c);break;case')':case'#':{do{t=Pop(&S);if(t!='('&&t!='#')EnQueue(Q,t);}while(t!='('&&S.top!=-1);break;}case'+':case'-':case'*':case'/':while(Priority(c)=Priority(GetTop(S))){t=Pop(&S);EnQueue(Q,t);}Push(&S,c);break;}}while(c!='#');}DataTypeCPostExp(SeqQueueQ){SeqStackS;charch;intx,y;InitStack(&S);while(!QueueEmpty(Q)){ch=DeQueue(&Q);if(ch='0'&&ch='9')Push(&S,ch);else{y=Pop(&S)-'0';x=Pop(&S)-'0';switch(ch){case'+':Push(&S,(char)(x+y+'0'));break;case'-':Push(&S,(char)(x-y+'0'));break;case'*':Push(&S,(char)(x*y+'0'));break;case'/':Push(&S,(char)(x/y+'0'));break;}}}returnGetTop(S);}intmain(intargc,char*argv[]){SeqQueueQ;InitQueue(&Q);printf(输入表达式：\n);CTPostExp(&Q);printf(结果：%c\n,CPostExp(Q));printf(后缀表达式：);while(!QueueEmpty(Q))printf(%2c,DeQueue(&Q));printf(\n);system(PAUSE);return0;}四.算法时间复杂度。0（n）五.小结除了主函数以外的其他函数是参考书上的代码，修改和增加了部分代码后，才可以运行。通过运行代码，深刻体会栈的后进先出的特性。六、用户手册1）系统要求：win98以上操作系统2）语言平台：c或c++3）工具：Xcode