实习报告_65.docVIP

实习报告 题目：表达式计算是实现程序设计语言的基本问题之一，也是栈的应用的一个典型例子。设计一个程序，演示用算符优先法对算术表达式求值的过程。 班级：计算机06（1） 姓名：崔敬敏 学号：744 完成日期：2008.4.16 Email:cjm@ 一、需求分析 本演示程序中，集合输入的形式为一个以“回车符”为结束标志的整型，输入的算术式是以字符序列的形式从终端输入语法正确的、不含变量的整数表达式。 利用教科书中给出的算符优先关系，实现对算术四则混合运算表达式的求值，并集仿照教科书的例子演示在求值中运算符栈、运算数栈、输入字符和主要操作的变化过程。 3、演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的运算命令；相应的输入数据和运算结果显示在其后。 4、程序执行的命令包括： 1）输入正确的算术表达式；2）输出计算的结果；3）结束。 5、测试数据 3*（7-2）；8；1+2+3+4；88-1*5；1024/4*8；1024/（4*8）；（20+2）*（6/2）；3-3-3； 8/（9-9）；2*（6+2*（3+6*（6+6）））；（（（6+6）*6+3）*2+6）*2； 二、概要设计 为实现上述程序功能，应用栈的顺序存储来实现运算符和操作数的存储。为此，需要一个抽象数据类型：栈。 栈类型定义如下： ADT Stack{ 数据对象：D={ai|ai-elemset,i=1,2,…,n,n=0} 数据关系：R1={ai-1,ai|ai-1,ai-D,i=2,…,n} 约定an端为栈顶，a1端为栈底。 基本操作： initstack(s) 操作结果：构造一个空栈S。 Destroystack(s) 初始条件：栈S已存在。 操作结果：栈S被销毁。 Clearstack(s) 初始条件：栈S已存在。 操作结果：将S清为空栈。 Stackempty(s) 初始条件：栈S已存在。 操作结果：将栈S为空栈，则返回TURE，否则FALSE。 Stacklength(s) 初始条件：栈S已存在。 操作结果：返回S的元素的个数，即栈的长度。 Gettop(s.e) 初始条件：栈S已存在且非空。 操作结果：用e返回S的栈顶元素。 Push(s,e) 初始条件：栈S已存在。 操作结果：插入元素e为新的栈顶元素。 Pop(s,e) 初始条件：栈S已存在且非空。 操作结果：删除S的栈顶元素，并用e返回其值。 Stacktraversre(s,visit()) 初始条件：栈S已存在且非空。 操作结果：从栈底到栈顶依次对S的每个元素调用函数visit().一旦visit()失败，则操作失效。 }ADT stack 本程序包含三个模块： 1）主程序模块 Void main(){ 初始化； 接受命令； 处理命令； } 2）栈单元模块——实现循环链表的抽象数据类型； 3）各模块之间的调用关系如下： 主程序模块 栈单元模块 三、详细设计 1、元素类型、结点类型和指针类型 #define STACK_INIT_SIZE 100 //存储空间初始分配量 #define STACKINCREMENT 10度 //存储空间分配增量 typedef struct{ selemtype *base; //在栈构造之前和销毁之后，base的值为NULL selemtype *top; //栈顶指针 int stacksize; //当前已分配的存储空间，以元素为单位 }sqstack; 2．部分函数的抽象代码 1）函数的抽象算法（伪码）1：status push(sqstack s,selemtype e){ if(s.top==s.base) returnERROR; e=*(s.top-1); return OK; }//push 函数的抽象算法（伪码）2： status gettop(sqstack s,selemtyp