数据结构~栈和队列的应用_表达式的求值.doc

2011-2012学年第一学期数据结构课内实验报告实验名:栈和队列的应用：表达式的求值姓 名：学 号：班 级： 指导老师: 日 期： 实验题目： 1、 实验目的：通过此实验进一步理解栈和队列，提高运用理论解决实际问题的能力。2、 实验内容: 例如，输入9-（2+4*7）/5+3# ，并按回车键，即可输出结果如下：表达式的运算结果是：6表达式的后缀表达式为：9 2 4 7 * +5/-3+3、 数据结构及算法思想: 表达式计算是实现程序设计逻辑语言的基本问题之一，也是栈和队列应用的一个典型的例子。该设计是先通过栈将中缀表达式转换为后缀表达式，在转换过程中又用到了队列的操作。而在得到后缀表达式之后，又用到队列的操作对生成的后缀表达式进行计算。在整个设计的实现过程中，用到的都是栈和队列的概念。 4、 模块化分:本程序分为2个模块：（1）中缀表达式转换为后缀表达式；（2）求后缀表达式5、 详细设计及运行结果:(1)中缀表达式转换为后缀表达式void CTPostExp(SeqQueue *Q) SeqStack S; /运算符栈char c,t; InitStack(&S); /初始化栈 Push(&S,#); /压入栈底元素# do /扫描中缀表达式c=getchar();switch(c)case :break; /去除空格符case 0: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 #:dot=Pop(&S);if(t!=(&t!=#) EnQueue(Q,t);while(t!=(&S.top !=-1);break;case +:case -:case *:case /:while(Priority(c)=0 &ch=9)Push(&S,ch);elsey=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; return GetTop(S);输入9-（2+4*7）/5+3# ，并按回车键，输出：表达式的运算结果是：6 表达式的后缀表达式为：9 2 4 7 * +5/-36、 调试情况，设计技巧及体会：表达式是由运算对象、运算符、括号组成的有意义的式子。要写此程序，必须了解到底什么是中缀表达式、后缀表达式并灵活运用栈和队列。7、 源程序清单: #include#define StackSize 100#define QueueSize 100/*队列的相关操作*/typedef char DataType;typedef struct char data100; int front,rear;SeqQueue; /定义队列类型void InitQueue(SeqQueue *Q) /初始化队列 Q-front =0; Q-rear =0;int QueueEmpty(SeqQueue Q) /判空队列return Q.rear =Q.front ;void EnQueue(SeqQueue *Q,DataType x) /入队列if(Q-rear +1) % QueueSize=Q-front )printf(Queue overflow);elseQ-dataQ-rear=x;Q-rear =(Q-rear +1)%QueueSize;DataType DeQueue(SeqQueue *Q) char x;if(QueueEmpty(*Q) return 0;elsex=Q-dataQ-front ;Q-front =(Q-front +1)%QueueSize;return x; /*栈的相关操作*/typedef structDataType data100;int top;SeqStack; /栈类型的定义void InitStack(SeqStack *S) /初始化栈S-top =-1;void Push(SeqStack *S,DataType x) /入栈if(S-top =StackSize-1)printf(Stack ouerflow);elseS-top =S-top +1;S-data S-top =x;DataType Pop(SeqStack *S) /出栈if(S-top =-1) printf(stack underflow);return 0;elsereturn S-dataS-top -;DataType GetTop(SeqStack S) /取栈顶元素if(S.top =-1) printf(stack empty);return 0;elsereturn S.data S.top ; /求运算符优先级函数int Priority(DataType op) switch(op)case (:case #:return 0; case -:case +:return 1;case *:case /:return 2;return -1;void CTPostExp(SeqQueue *Q)SeqStack S; /运算符栈char c,t;InitStack(&S); /初始化栈Push(&S,#); /压入栈底元素#do /扫描中缀表达式c=getchar();switch(c)case :break; /去除空格符case 0: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 #:dot=Pop(&S);if(t!=(&t!=#) EnQueue(Q,t);while(t!=(&S.top !=-1);break;case +:case -:case *:case /:while(Priority(c)=0 &ch=9)Push(&S,ch);elsey=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;return GetTop(S);void main()SeqQueue Q; /定义队列，存放后缀表达式InitQueue(&Q); /初始化队列CTPost