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

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

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

2、顶元素，然后将该运算符入栈6.最终将栈中的元素依次出栈，输出。(二)二.实验分析程序源码(要求对毎个函数及主要代码加上注释语句)，源码出处。////main.c//后缀表达式求值////Createdby颜彦闻on14/12/2.//Copyright(c)2014年颜彦闻.Allrightsreserved.//#include#include#defineStackSize100#defineQueueSize100typedefcharDataType;typedefstruct{chardataflOO];in

3、tfront,rear;}SeqQueue;//定义队列•戈型voidInitQueue(SeqQueue*Q)//初始化队列{Q->front=0;Q->rear=0;}intQueueEmpty(SeqQueueQ)//判空{returnQ.rear==Q.front;}voidEnQueue(SeqQueue*Q，DataTypex)//元素入队列困数{if((Q->rear+l)%QueueSize==Q->front)printff'Queueoverflow");else{Q->datafQ->rear]=x;Q->rear=(Q->rear+

4、1)%QueueSize;DataTypeDeQueue(SeqQueue*Q)charx;if(QueueEmpty(*Q))return0;else{x=Q->data[Q->front];Q->front=(Q->front+l)%QueueSize;returnx;}}//栈的相关操作typedefstruct{DataTypedata[100J;inttop;}SeqStack;voidInitStack(SeqStack*S)//栈的初始化{S->top=-l;//进栈函数//退栈顶指针函数voidPush(SeqStackDataTypex)

5、{*if(S->top==StackSize-1)printf(”stackoverflow’’)；else{S-〉top=S-〉top+l;S-〉data[S-〉top]=x;DataTypePop(SeqStack*S){'if(S->top==-l){printff’stackunderflown)return0;}elsereturnS->data[S->top—];DataTypeGetTop(SeqStackS)//取拽顶元素{"if(S.top==-l){printf(Mstackempty”);return0;}elsereturnS.da

6、ta[S.top];intPriority(DataTypeop){switch(op)//求运算符优先级函数casecasereturn0;case■-’：case•+’：return1;case•*’：case7’：return2;}return-1;}voidCTPostExp(SeqQueue*Q){SeqStackS;charc，t;InitStack(&S);Push(&S；#f);doc=getchar();switch(c)casecasecasecasecasecasecasecasecasecasebreak;456789EnQueue

7、(Q,c);break;caseX’：Push(&S，c);break;casey：case•#’：{do{t=Pop(&S);if(t!=’C&&t!=’#’)EnQueue(Q，t);}while(t!-('&&S.top!=-l);break;case•+’：case•-’：case•*':case7:while(Priority(c)<=Priority(GetTop(S))){t=Pop(&S);EnQueue(Q,t);}Push(&S，c);break;}while(c!=.#’);DataTypeCPostExp(SeqQueueQ){、S

8、eqStackS;charch;intx，y;InitStack(