数据结构栈和队列应用表达式求值.pdf
2018-2018 学年第一学期 数据结构课内实验报告 实验名：栈和队列的应用：表达式的求值 姓名：学号：班级：指导老师：日期:实验题目：1、实验目的：通过此实验进一步理解栈和队列，提高运用理论解决实际问题的能力。2、实验内容：例如，输入9-2+4*7)/5+3#，并按回车键，即可输出结果如下：表达式的运算结果是：6 表达式的后缀表达式为：9 2 4 7*+5/-3+3、数据结构及算法思想：表达式计算是实现程序设计逻辑语言的基本问题之一，也是栈和队列应用的一 个典型的例子。该设计是先通过栈将中缀表达式转换为后缀表达式，在转换过 程中又用到了队列的操作。而在得到后缀表达式之后，又用到队列的操作对生 成的后缀表达式进行计算。在整个设计的实现过程中，用到的都是栈和队列的 概念。b5E2RGbCAP 4、模块化分:本程序分为2个模块：1)中缀表达式转换为后缀表达式;中缀表达式转换为后缀表达式 void CTPostExp(SeqQueue*Q case 6:SeqStack S char c,t。In itStack(&S。Push(&S,#。运算符栈/初始化栈 压入栈底元素#case 1:do 扫描中缀表达式 c=getchar(。switch(c case case 0:case 2 case 3 case 4 case 5 去除空格符 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(cv=Priority(GetTop(S t=Pop(&S。EnQueue(Q,t。Push(&S,c。breako while(c!=#。以#号结束表达式扫描 (2后缀表达式的计算 DataType CPostExp(SeqQueue Q SeqStack S char ch。int x,y。In itStack(&S。while(!QueueEmpty(Q ch=DeQueue(&Q。if(ch=0&ch 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 7:Push(&S,(char(x/y+0。break。return GetTop(S。输入9-2+4*7)/5+3#，并按回车键，输出：表达式的运算结果是：6 表达式的后缀表达式为：9 2 4 7*+5/-3 6、调试情况，设计技巧及体会：表达式是由运算对象、运算符、括号组成的有意义的式子。要写此程 序，必须了解到底什么是中缀表达式、后缀表达式并灵活运用栈和队 列o plEanqFDPw 7、源程序清单：#in clude#define StackSize 100#define QueueSize 100/*队列的相关操作*/typedef char DataType。typedef struct char data100。int fron t,rear。SeqQueue。/定义队列类型 void Ini tQueue(SeqQueue*Q 初始化队列 Q-fro nt=0。Q-rear=0。int QueueEmpty(SeqQueue Q/判空队列 return Q.rear=Q.fro nt。void En Queue(SeqQueue*Q,DataType x/入队列 if(Q-rear+1%QueueSize=Q-fro nt pr in tf(Queue overflow。else Q-dataQ-rear=x。Q-rear=(Q-rear+1%QueueSize。DataType DeQueue(SeqQueue*Q charx。if(QueueEmpty(*Q return 0。else x=Q-dataQ-fro nt 。Q-fro nt=(Q-fro nt+1%QueueSize。return x。/*栈的相关操作*/typedef struct DataType data100。int top。SeqStack。/栈类型的定义 void In itStack(SeqStack*S /初始化栈 S-top=-1。void Push(SeqStack*S,DataType x /入栈 if(S-top=StackSize-1 prin tf(Stack ouerflow。else S-top=S-top+1。S-data S-top=x。DataType Pop(SeqStack*S /出栈 if(S-top=-1 prin tf(stack un derflow return 0。else return S-dataS-top-。DataType GetTop(SeqStack S /取栈顶元素 if(S.top=-1 prin tf(stack empty return 0。else return S.data S.top 。/求运算符优先级函数 int Priority(DataType op switch(op case(:case#:retur n 0。case-:case+:retur n 1。case*:case/:retur n 2。return-1。void CTPostExp(SeqQueue*Q SeqStack S。/char c,t。In itStack(&S。/Push(&S,#。/do /扫描中缀表达式 c=getchar(。switch(c case :break。/去除空格符 case O:case T: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!=#En Queue(Q,t。while(t!=(&S.top!=-1。break。case+:case-:case*:case/:while(Priority(cv=Priority(GetTop(S t=Pop(&S。EnQueue(Q,t。Push(&S,c。break。while(c!=#。/以#号结束表达式扫描/后缀表达式的计算 DataType CPostExp(SeqQueue Q SeqStack S。char ch。int x,y。In itStack(&S。while(!QueueEmpty(Q 运算符栈 初始化栈 压入栈底元素#ch=DeQueue(&Q if(ch=0&chv=9 Push(&S,ch。else y=Pop(&S-0。x=Pop(&S-0。switch(ch case+:Push(&S,(char(x+y+O。break。case-:Push(&S,(char(x-y+O。break。case*:Push(&S,(char(x*y+O。break。case 7:Push(&S,(char(x/y+O。break。return GetTop(S。void mai n(SeqQueue Q/InitQueue(&Q。/printf(表达式的运算结果是：cn,CPostExp(Q。/输出计算结果 printf(”表达式的后缀表达式为：。pri ntf(%2c,DeQueue(&Q。prin tf(n 申明：所有资料为本人收集整理，仅限个人学习使用，勿做商业用 途。定义队列，存放后缀表达式 初始化队列 调用转换函数将中缀表达式转换成后缀表达式 CTPostExp(&Q。/while(!QueueEmpty(Q/输出后缀表达式
