数据结构实验栈的应用.doc

《数据结构实验栈的应用.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、课程题目：数据结构试验学院：班级：姓名：学号:实验题目：栈的应用实验内容：算术表达式求值实验目的：掌握栈和队列的概念及工作原理，运用其原理完成实验题目中的内容。实验要求：为了使学生更好的掌握与理解课堂上老师所讲的概念与原理，实验前每个学生要认真预习所做的实验内容及编写源程序伪码（写在纸上及盘中均可）实验学时：4学时设计原理：任何一个表达式都是有操作数、运算符和界限符组成的。我们把运算符和界限符统称为算符，它们构成的集合命名为OP。根据简单算术表达式的运算规则，在运算的每一步中，任意两个相继出现的算符a和b之间的优先关系至多是下面

2、三种关系之一：aba的优先权大于b为实现算符优先算法，可以使用两个工作栈。一个为ＯＰＴＲ，用以寄存预算符；另一个为ＯＰＮＤ，用以寄

3、存操作数或运算结果。算法基本思想：⑴．首先置操作数栈为空栈，表达式起始运算符“＃”为运算符栈的基本元素；⑵．依次读入表达式中每个字符，若是操作数则进ＯＰＮＤ栈，若是运算符则和ＯＰＴＲ栈的栈顶运算符比较优先权执行相应操作，直至整个表达式求值完毕（即ＯＰＴＲ栈的栈顶元素和当前读入的字符均为“＃”）。详细程序清单及注释说明：#include#include#include#include#defineTRUE1#defineFALSE0#defineOK1#d

4、efineERROR0#defineINFEASIBLE-1#defineOVERFLOW-2#defineSTACK_INIT_SIZE100　//初始量分配　#defineSTACKINCREMENT10　　//存储空间的分配增量typedefstruct{char*base;char*top;intstacksize;}sqstack;intinitstack(sqstack&s){　//创造一个空栈Ｓs.base=(char*)malloc(STACK_INIT_SIZE*sizeof(char));if(!s.base

5、)exit(OVERFLOW);s.top=s.base;s.stacksize=STACK_INIT_SIZE;returnOK;}intpush(sqstack&s,chare){　//插入ｅ为新的栈顶元素if(s.top-s.base>=s.stacksize){s.base=(char*)realloc(s.base,(s.stacksize+STACKINCREMENT)*sizeof(char));if(!s.base)exit(OVERFLOW);s.top=s.base+s.stacksize;s.stacksi

6、ze+=STACKINCREMENT;}*s.top++=e;returnOK;}intpop(sqstack&s,char&e){　//若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERRORif(s.top==s.base)returnERROR;e=*--s.top;returnOK;}intgettop(sqstacks){chare;if(s.top==s.base)returnERROR;e=*(s.top-1);returne;}charin(chargetchar){if(getchar>='#

7、'&&getchar<='/')returnOK;elsereturnERROR;}charprecede(charoptrchar,chargetchar1){if(optrchar=='+'){switch(getchar1){case'+':return'>';break;case'-':return'>';break;case'*':return'<';break;case'/':return'<';break;case'(':return'<';break;case')':return'>';break;case'#'

8、:return'>';break;}}if(optrchar=='-'){switch(getchar1){case'+':return'>';break;case'-':return'>';break;case'*':return'<';break;case'