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

《数据结构与算法设计》 实验报告 ——实验二 学院： 班级： 学号： 姓名： 一、实验目的 通过实验实践、巩固栈的相关操作； 熟悉VC环境，加强编程、调试的练习； 用C语言实现栈的抽象数据类型，实现栈的建立、进栈、出栈、取数据等基本操作； 用C语言实现判断运算符优先级、表达式求值等基本操作； 理论知识与实际问题相结合，利用上述基本操作实现简单计算器。 二、实验内容 1、简单计算器。 请按照四则运算加、减、乘、除、幂（^）和括号的优先关系和惯例，编写计算器程序。要求： 从键盘输入一个完整的表达式，以回车作为表达式输入结束的标志。 输入表达式中的数值均为大于等于零的整数。中间的计算过程如果出现小数也只取整。 例如，输入：4+2*5= 输出：14 输入：(4+2)*(2-10)= 输出：-48 三、程序设计 1、概要设计 为实现上述程序功能，应用栈存储运算符和操作数，为此需要建立一个抽象数据类型：栈。 （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）、抽象数据类型定义 typedef char ElemType1; //定义元素类型1为char typedef int ElemType2; //定义元素类型2为int typedef struct {//栈SqStack1存储元素为char ElemType1 *base; //栈空间基址 ElemType1 *top; //栈顶指针 int stacksize; //当前分配的栈空间大小 }SqStack1; typedef struct {//栈SqStack2存储元素为int ElemType2 *base; //栈空间基址 ElemType2 *top; //栈顶指针 int stacksize; //当前分配的栈空间大小 }SqStack2; （3）、操作算法程序实现： int InitStack1( SqStack1 S ) { //构造一个空栈S S.base = ( ElemType1 *)malloc( STACK_INIT_SIZE * sizeof(ElemType1) ); //为顺序栈动态分配存储空间 if ( ! S. base) exit(OVERFLOW); //分配失败 S.top = S.base; S.stacksize = STACK_INIT_SIZE; return