实验三 栈和队列的应用 表达式的求值

《实验三 栈和队列的应用 表达式的求值》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、2011-2012学年第一学期数据结构课内实验报告实验名:栈和队列的应用：表达式的求值姓名：张蓉学号：09411100126班级：信息与计算科学091班指导老师:肖小克日期：2011年10月21日7实验题目：1、实验目的：通过此实验进一步理解栈和队列，提高运用理论解决实际问题的能力。2、实验内容:例如，输入9-（2+4*7）/5+3#，并按回车键，即可输出结果如下：表达式的运算结果是：6表达式的后缀表达式为：9247*+5/-3+3、数据结构及算法思想:表达式计算是实现程序设计逻辑语言的基本问题之一，也是栈和队列应用的一个典型的例子。该设计是先通过栈将中缀表达式转换为后缀表达式，在转

2、换过程中又用到了队列的操作。而在得到后缀表达式之后，又用到队列的操作对生成的后缀表达式进行计算。在整个设计的实现过程中，用到的都是栈和队列的概念。  4、模块化分:本程序分为2个模块：（1）中缀表达式转换为后缀表达式；（2）求后缀表达式5、详细设计及运行结果:(1)中缀表达式转换为后缀表达式voidCTPostExp(SeqQueue*Q){SeqStackS;//运算符栈charc,t;InitStack(&S);//初始化栈Push(&S,'#');//压入栈底元素‘#’do{//扫描中缀表达式c=getchar();switch(c){case'':break;//去除空格符c

3、ase'0':case'1':case'2':case'3':7case'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(&

4、S);EnQueue(Q,t);}Push(&S,c);break;}}while(c!='#');//以'#'号结束表达式扫描}(2)后缀表达式的计算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;c

5、ase'-':Push(&S,(char)(x-y+'0'));break;case'*':Push(&S,(char)(x*y+'0'));break;case'/':Push(&S,(char)(x/y+'0'));break;}}7}returnGetTop(S);}输入9-（2+4*7）/5+3#，并按回车键，输出：表达式的运算结果是：6表达式的后缀表达式为：9247*+5/-31、调试情况，设计技巧及体会：表达式是由运算对象、运算符、括号组成的有意义的式子。要写此程序，必须了解到底什么是中缀表达式、后缀表达式并灵活运用栈和队列。2、源程序清单:#include

6、h>#defineStackSize100#defineQueueSize100/*队列的相关操作*/typedefcharDataType;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)%Q

7、ueueSize==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;}7}/*栈