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

数据结构课程设计报告课程设计题目：中缀表达式改后缀表达式并求值1. 实验目的掌握栈的特征及基本操作，如入栈、出栈等，栈的顺序存储结构和链式存储结构的实现，以便在实际问题中灵活应用。掌握栈的典型应用中缀表达式转后缀表达式，并利用后缀表达式求值。2. 实验内容（一）中缀表达式转后缀表达式的方法：1.遇到操作数：直接输出（添加到后缀表达式中）2.栈为空时，遇到运算符，直接入栈3.遇到左括号：将其入栈4.遇到右括号：执行出栈操作，并将出栈的元素输出，直到弹出栈的是左括号，左括号不输出。5.遇到其他运算符：加减乘除：弹出所有优先级大于或者等于该运算符的栈顶元素，然后将该运算符入栈6.最终将栈中的元素依次出栈，输出。（二）3. 实验分析程序源码（要求对每个函数及主要代码加上注释语句），源码出处。/ main.c/ 后缀表达式求值/ Created by 颜彦闻 on 14/12/2./ Copyright (c) 2014年 颜彦闻. All rights reserved./#include #include #define StackSize 100#define QueueSize 100typedef 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); else Q-dataQ-rear=x; Q-rear=(Q-rear+1)%QueueSize; DataType DeQueue(SeqQueue *Q) char x; if(QueueEmpty(*Q) return 0; else x=Q-dataQ-front; Q-front=(Q-front+1)%QueueSize; return x; /栈的相关操作typedef struct DataType data100; int top;SeqStack;void InitStack(SeqStack *S) /栈的初始化 S-top=-1;void Push(SeqStack *S,DataType x) /进栈函数 if(S-top=StackSize-1) printf(stack overflow); else S-top=S-top+1; S-dataS-top=x; DataType Pop(SeqStack *S) /退栈顶指针函数 if(S-top=-1) printf(stack underflow); return 0; else return S-dataS-top-;DataType GetTop(SeqStack S) /取栈顶元素 if(S.top=-1) printf(stack empty); return 0; else return S.dataS.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 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 t=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); 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 /: Push(&S,(char)(x/y+0); break; return GetTop(S);int main(int argc, char *argv) SeqQueue Q; InitQueue(&Q); printf(输入表达式：n); CTPostExp(&Q); printf(结果：%cn,CPostExp(Q); printf(后缀表达式：); while(!QueueEmpty(Q) printf(%2c,DeQueue(&Q); printf(n); system(PAUSE); return 0;4