北京理工大学数据结构实验报告实验二.doc

《数据结构与算法设计》 实验报告 ——实验二 学院： 班级： 学号： 姓名： 一、实验目的 通过实验实践、巩固的相关操作； VC环境，编程、调试的； C语言，实现的建立数据等基本操作； 理论知识与实际相结合，上述基本操作实现计算器。 1、简单计算器。 请按照四则运算加、减、乘、除、幂（^）和括号的优先关系和惯例，编写计算器程序。要求： 从键盘输入一个完整的表达式，以回车作为表达式输入结束的标志。 输入表达式中的数值均为大于等于零的整数。中间的计算过程如果出现小数也只取整。 例如，输入：4+2*5= 输出：14 输入：(4+2)*(2-10)= 输出：-48 三、程序设计 1、概要设计 为实现上述程序功能，应用存储运算符和，需要建立一个抽象数据类型：。 ）的抽象数据类型定义为： ADT Stack{ D={ai|ai∈ElemSet,i=1,2,3……,n,n≥0} 数据关系：R1={ ai-1,ai|ai∈D,i=1,2,……,n} 基本操作： InitStack(S) 操作结果：创建一个空栈S。 Push(S, e) 初始条件：栈S已存在 操作结果：插入运算符e作为新的栈顶元素 GetTop(S) 初始条件：栈S已存在且非空 操作结果：用e返回寄存运算符栈S的栈顶元素 Pop(S,e) 初始条件：栈S已存在且非空 操作结果：删除寄存运算符栈S的栈顶元素 Operate(a,theta,b) 初始条件：a，b为整数，theta为运算符 操作结果：返回a与b运算的结果 Precede(d,c) 初始条件：d，c为运算符 操作结果：若d优先级大于c,返回‘’；若d优先级小于c,返回‘’；若d优先级等于c,返回‘=’； EvaluateExpression() 初始条件：输入合法的表达式 操作结果：返回表达式的值 }ADT Stack ⑵主程序流程 调用EvaluateExpression()函数计算表达式的值，并将结果输出在屏幕上。 ⑶各函数模块的调用关系 先由主函数调用计算求值函数； 再由求值模块调用栈构造函数，构造两个栈分别用来保存操作数和运算符，然后根据情况多次调用进栈、出栈、取栈顶元素、判断运算符优先级、计算表达式的值等多个函数，计算并返回表达式的值； 最后由主函数在屏幕上输出表达式的结果。 ⑷流程图 2、详细设计 (1)、宏定义 #define STACK_INIT_SIZE 10 // 栈存储空间的初始分配量 #define STACKINCREMENT 10 // 空间的分配增量 #define OK 1 // 正确时返回值为真 #define ERROR 0 // 出错时返回值为假 （2）抽象数据类型定义）操作程序实现：）主程序代码实现： int main() { int x; x=EvaluateExpression(); //返回表达式的值 printf(%d\n,x); //输出表达式的值 return 0; } 不C语言语法，应使用C++; ； 本程序的运行环境为DOS操作系统，执行文件为：.exe，双击。 进入程序后，Enter键结束。 屏幕输出上述表达式的结果，按任意键退出程序。： 二： 七、程序清单 #include stdio.h #include stdlib.h #include math.h typedef char ElemType1; //定义元素类型1为char typedef int ElemType2; //定义元素类型2为int #define STACK_INIT_SIZE 10 // 栈存储空间的初始分配量 #define STACKINCREMENT 10 // 空间的分配增量 #define OK 1 // 正确时返回值为真 #define ERROR 0 // 出错时返回值为假 typedef struct { //栈SqStack1存储元素为char ElemType1 *base; //栈空间基址 ElemType1 *top; //栈顶指针 int stacksize; //当前分配的栈空间大小 }SqStack1; typedef struct { //栈SqStack2存储元素为int ElemType2 *base; //栈空间基址 ElemType2 *top; //栈顶