《北理工数据结构实验二》由会员分享，可在线阅读，更多相关《北理工数据结构实验二（37页珍藏版）》请在金锄头文库上搜索。
1、北理工数据结构实验二数据结构与算法设计实验报告实验学院：班级：学号：姓名：一、实验目的1 .通过实验实践、巩固栈的相关操作；2 .熟悉VC环境，加强编程、调试的练习；3 .用C语言实现栈的抽象数据类型，实现栈的 建立、进栈、出栈、取数据等基本操作；4 .用C语言实现判断运算符优先级、表达式求 值等基本操作；5 .理论知识与实际问题相结合，利用上述基本 操作实现简单计算器。二、实验内容1、简单计算器。请按照四则运算加、减、乘、除、哥（人）和括 号的优先关系和惯例，编写计算器程序。要求：从键盘输入一个完整的表达式，以回车作为 表达式输入结束的标志。输入表达式中的数值均为大于等于零的整 数。中间的计
2、算过程如果出现小数也只取 整。例如，输入：4+2*5= 输出：14输入：（4+2）*（2-10）= 输出：-48三、程序设计1、概要设计为实现上述程序功能，应用栈存储运算符和操作 数，为此需要建立一个抽象数据类型：栈。(1)栈的抽象数据类型定义为:ADT Stack数据对象：D=ai|ai ElemSet, i=l, 2, 3,n, nO数据关系：Rl= |ai D, i=l, 2,n基本操作：InitStack(&S)操作结果：创建一个空栈s。Push (&S, e)初始条件：栈S已存在 操作结果:插入运算符e作为新的栈顶元GetTop(&S)初始条件：栈S已存在且非空 操作结果:用e返回寄
3、存运算符栈S的栈顶元素Pop (&S, &e)初始条件：栈S已存在且非空 操作结果:删除寄存运算符栈S的栈顶元素Operate(a,theta,b)初始条件：a, b为整数，theta为运算符 操作结果：返回a与b运算的结果Precede(d,c)初始条件：d, c为运算符操作结果：若d优先级大于c,返回； 若d优先级小于c,返回 =S.stacksize ) /若栈满则追加存储空间 S.base = (ElemTypel * ) realloc( S.base,(S.stacksize+STACKINCREMENT) * sizeof(ElemTypel);if(! S. base )exi
4、t(OVERFLOW); / 存储分配失败S.top = S.base + S.stacksize;S.stacksize+=STACKINCREMENT; * S.top + = e; / 元素 e 插入 栈顶，后修改栈顶指针return OK; / *S.top=e;S.top +; /Pushlchar GetTop1( SqStackl S) /取栈顶元素并返回其值ElemType1 e;if ( S.top=S.base) return ERROR; /e = *(S.top-1);return e; /GetTop1int Pop1 ( SqStack1 &S, ElemType1
5、 &e )栈空 删除栈顶元素，并用e返回其值if ( S.top=S.base) return ERROR; /S.top；栈空/ -S.top;e=*S.top;return OK; Pop1int InitStack2( SqStack2 / 构造一个空栈SS.base =&S )ElemType2*)malloc(STACKINITSIZEsizeof(ElemType2);/ 为顺序栈动态分配存储空间ifS.base)exit(OVERFLOW); / 分配失败 S.top = S.base;S.stacksize = STACK INIT SIZE;return OK; InitSt
6、ack2 int Push2( SqStack2 &S, ElemType2 e ) / 将元素e插入栈中，使其成为新的 栈顶元素if ( S.top-S.base=S.stacksize ) /若栈满则追加存储空间 S.base = (ElemType2 * ) realloc( S.base,(S.stacksize+STACKINCREMENT) * sizeof(ElemType2);if(! S. base )exit(OVERFLOW); / 存储分配失败S.top = S.base + S.stacksize;S.stacksize+=STACKINCREMENT; * S.to
7、p + = e; / 元素 e 插入栈顶，后修改栈顶指针return OK; / *S.top=e;S.top +; /Push2int GetTop2( SqStack2 S) /取栈顶元素并返回其值ElemType2 e;if ( S.top=S.base)return ERROR; /栈空e = *(S.top-1);return e; /GetTop2int Pop2 ( SqStack2 &S, ElemType2&e ) 删除栈顶元素，并用e返回其值if ( S.top=S.base) return ERROR; /栈空e = * - S.top; /-S.top;e=*S.top
8、;return OK; /Pop2 int In (char c) 判断c是否为运算符，是则返回1, 否则返回0Oif(c=+|c=-|c=*11c=/|c=A|c=(|c=)11c=)return 1;elsereturn 0; /Inchar Precede(char d,char c) /判断运算符d与运算符c的优先级 switch(c)case+:switch(d)case+:return ;break;case-:return ;break;case*:return ;break;case/:return ;break;caseA:return ;break;case(:return
9、 ;break;case=:return ;break; case-:return ;break; case*:return ;break; case/:return ;break; casereturn ;break; case(:return ;break; case=:return ;break;case*:switch(d)case+:return ;break; case-:return ;break; case/:return ;break; casereturn ;break; case(:return ;break; case=:return ;break;case/:switch(d)case+:return ;break; case-:return ;break; case/:return ;break; casereturn ;break; case(:return ;break; case=:return ;break;caseA:switch(d)case+:return ;break; case-:return ;break; case*:return ;break; case/:return ;break; case(:retu
