实习报告二算术表达式求值演示-Read.DOC

实习报告二 算术表达式求值演示 题目：设计一个程序，演示用算符优先法对算术表达式求值的过程 班级：计算机05（2） 姓名：刘丹华 学号：22120051203932 完成日期2007.10.27 Email:liudanhua1234@126.com 需求分析 本演示程序中，要求用户以字符序列的形式从终端输入语法正确的，不含变量的整数表达式并以‘#’结束。 由于算符有优先关系，可用栈来实现。设置运算符栈来接收运算符，优先权低的压入栈内，优先权高的进行运算，设置运算数栈来接收运算数，并存储中间的运算结果。 在读入字符序列的同时，完成运算符合运算数（整数）的识别处理，以及相应的运算，在识别出是运算数的同时，将当前字符序列转换成整数形式 运算结果显示在求值过程中运算符栈、运算数栈、当前字符和主要操作的变化过程。 测试数据： 1）、3*（7-2） 2）、8 3）、1+2+3+4 4）、88-1*5 5）、1024/4*8 6）、1024/（4*8） 7）、（20+2）*（6/2） 8）、3-3-3 9）、8/（9-9） 10）、2*（6+2*（3+6*（6+6））） 11)、（（（6+6）*3）*2+6）*2 概要设计 设定运算符栈的抽象数据类型定义： ADT OPTR{ 数据对象：D={ ai∣ai∈CHAR,i=1,2…，n,n=0} 数据关系：R1={ai-1,ai | ai-1,ai∈D,i=2,…，n} 约定an端为栈顶,a1 端为栈底 基本操作： InitStack1(S) //构造一个空栈S,其中元素为CHAR型 GetTop1(S) //若栈不空，则用e返回S的栈顶元素，e为CHAR型 Push1(S,e) //插入e元素为新的栈顶元素,e为CHAR型 Pop1(S,e) //若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR，e为CHAR型 PrintStack1(S，m) //若栈S不空，则从栈底到栈顶输出S的元素(为CHAR型),并用m返回打印长度 }ADT OPTR 2、设定运算数栈的抽象数据类型定义： ADT OPND{ 数据对象：D={ ai∣ai∈ INT,i=1,2…，n,n=0} 数据关系：R1={ai-1,ai | ai-1,ai∈D,i=2,…，n} 约定an端为栈顶,a1 端为栈底 基本操作： InitStack2(S) //构造一个空栈S,其中元素为INT型 GetTop2(S) //若栈不空，则用e返回S的栈顶元素，e为INT型 Push2(S,e) //插入e元素为新的栈顶元素,e为INT型 Pop2(S,e) //若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR，//e为INT型 PrintStack1(S，n) //若栈S不空，则从栈底到栈顶输出S的元素(为INT型),并用n返回打印长度 }ADT OPND 详细设计 运算符栈的实现： #define STATACK_INIT_SIZE 100//存储空间初始分配量 #define STACKINCREMENT 10// 存储空间分配增量 typedef int Status; typedef struct{ char *base; //栈底指针,在栈构造之前和销毁之后，base的值为NULL char *top; //栈顶指针 int stacksize;// //当前已分配的存储空间,以元素为单位 }SqStack1;//运算符栈 基本操作的算法： Status InitStack1(SqStack1 S)//构造一个空栈S，其元素类型为char型 { S.base=(char *)malloc(STACK_INIT_SIZE*sizeof(char)); if(!S.base) return OVERFLOW;//存储分配失败 S.top=S.base; S.stacksize=STACK_INIT_SIZE; return OK; }//InitStack1 char GetTop1(SqStack1 S)//若栈不空，则返回S的栈顶元素 { if(S.top!=S.base) return *(S.top-1); }//GetTop1 Status Push1(SqStack1 S,char e)//插入元素e为新的栈顶元素 { if(S.top-S.base=S.stacksize)//栈满，追加存储空间 { S.base=(char *)realloc(S.base,(S.stacks