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

《数据结构中缀式中缀表达式改后缀表达式并求值.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《数据结构》课程设计报告课程设计题目：中缀表达式改后缀表达式并求值一.实验目的·掌握栈的特征及基本操作，如入栈、出栈等，栈的顺序存储结构和链式存储结构的实现，以便在实际问题中灵活应用。·掌握栈的典型应用——中缀表达式转后缀表达式，并利用后缀表达式求值。一.实验内容（一）中缀表达式转后缀表达式的方法：1.遇到操作数：直接输出（添加到后缀表达式中）2.栈为空时，遇到运算符，直接入栈3.遇到左括号：将其入栈4.遇到右括号：执行出栈操作，并将出栈的元素输出，直到弹出栈的是左括号，左括号不输出。5.遇到其他运算符：加减乘除：弹出所有优先级大于或者等于该运算符的栈顶元素，然后将该运算符入栈6.最终将栈中

2、的元素依次出栈，输出。（二）二.实验分析程序源码（要求对每个函数及主要代码加上注释语句），源码出处。////main.c//后缀表达式求值////Createdby颜彦闻on14/12/2.//Copyright(c)2014年颜彦闻.Allrightsreserved.//#include#include#defineStackSize100#defineQueueSize100typedefcharDataType;typedefstruct{chardata[100];intfront,rear;}SeqQueue;//定义队列类型voidInit

3、Queue(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(Queue

4、Empty(*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[

5、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

6、'-':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

7、{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!='#');}D