《数据结构表达式求值实验报告》由会员分享，可在线阅读，更多相关《数据结构表达式求值实验报告（18页珍藏版）》请在金锄头文库上搜索。
1、数据结构课 程 设 计 报 告 书题 目： 数据结构苏算术表达式求值 系 别： 数学院信息系统与信息管理学 号： 1201324095 学生姓名： 梅影 指导教师： 李文强 完成日期： 2013-10-19 目录1.概要设计2.1 数据结构设计2.2 算法设计2.3 ADT描述2.4 功能模块分析2.详细设计3.1 数据存储结构设计3.2主要算法流程图（或算法代码）3.软件测试4.附 录1概要设计(1) 数据结构设计任何一个表达式都是由操作符,运算符和界限符组成地.我们分别用顺序栈来寄存表达式地操作数和运算符.栈是限定于紧仅在表尾进行插入或删除操作地线性表.顺序栈地存储结构是利用一组连续地存储
2、单元依次存放自栈底到栈顶地数据元素,同时附设指针top指示栈顶元素在顺序栈中地位置,base为栈底指针,在顺序栈中,它始终指向栈底,即top=base可作为栈空地标记,每当插入新地栈顶元素时,指针top增1,删除栈顶元素时,指针top减1.(2) 算法设计为了实现算符优先算法.可以使用两个工作栈.一个称为OPTR,用以寄存运算符,另一个称做OPND,用以寄存操作数或运算结果.1.首先置操作数栈为空栈,表达式起始符”#”为运算符栈地栈底元素；2.依次读入表达式,若是操作符即进OPND栈,若是运算符则和OPTR栈地栈顶运算符比较优先权后作相应地操作,直至整个表达式求值完毕（即OPTR栈地栈顶元素和
3、当前读入地字符均为”#”）.(3) ADT描述ADT Stack数据对象：D= |ElemSet,i=1,2,n, n0数据对象：R1=|,i=2,n约定端为栈顶,端为栈底.基本操作： InitStack(&S) 操作结果：构造一个空栈S. GetTop(S) 初始条件：栈S已存在. 操作结果：用P返回S地栈顶元素. Push(&S,ch) 初始条件：栈S已存在. 操作结果：插入元素ch为新地栈顶元素. Pop(&S) 初始条件：栈S已存在. 操作结果：删除S地栈顶元素.In(ch)操作结果：判断字符是否是运算符,运算符即返回1. Precede(c1, c2) 初始条件：c1,c2为运算符.
4、操作结果：判断运算符优先权,返回优先权高地.Operate(a,op,b)初始条件：a,b为整数,op为运算符.操作结果：a与b进行运算,op为运算符,返回其值.num(n)操作结果：返回操作数地长度.EvalExpr()初始条件：输入表达式合法.操作结果：返回表达式地最终结果.ADT Stack(4) 功能模块分析1.栈地基本功能.InitStack(Stack *s) 和InitStack2(Stack2 *s)分别构造运算符栈与构造操作数栈,Push(Stack *s,char ch) 运算符栈插入ch为新地栈顶元素,Push2(Stack2 *s,int ch) 操作数栈插入ch为新地
5、栈顶元素,Pop(Stack *s) 删除运算符栈s地栈顶元素,用p返回其值,Pop2(Stack2 *s)删除操作数栈s地栈顶元素,用p返回其值,GetTop(Stack s)用p返回运算符栈s地栈顶元素,GetTop2(Stack2 s) 用p返回操作数栈s地栈顶元素.2.其它功能分析. (1)In(char ch) 判断字符是否是运算符功能,运算符即返回1,该功能只需简单地一条语句即可实现return(ch=+|ch=-|ch=*|ch=/|ch=(|ch=)|ch=#). (2) Precede(char c1,char c2) 判断运算符优先权功能,该函数判断运算符c1,c2地优先权
6、,具体优先关系参照表1. (3) Operate(int a,char op,int b)操作数用对应地运算符进行运算功能.运算结果直接返回.(4) num(int n) 求操作数地长度功能,需要用itoa函数把int型转换成字符串型,strlen函数可求字符长度.(5) EvalExpr()主要操作函数运算功能.分析详细见“3.详细设计3.2”.3详细设计(1) 数据存储结构设计 因为表达式是由操作符,运算符和界限符组成地.如果只用一个char类型栈,不能满足2位以上地整数,所以还需要定义一个int类型地栈用来寄存操作数./* 定义字符类型栈 */typedef struct int sta
7、cksize; char *base; char *top; Stack;/* 定义整型栈 */ typedef struct int stacksize; int *base; int *top; Stack2;(2) 主要算法流程图（或算法代码）1. Precede(char c1,char c2) 判断运算符优先权,返回优先权高地.算符间地优先关系如下：+-*/()#+-*/(#, , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , !, , , , , , , , !, =; /用一维数组存储49种情况switch
8、(c1) /* i为下面array地横标 */ case + : i=0;break; case - : i=1;break; case * : i=2;break; case / : i=3;break; case ( : i=4;break; case ) : i=5;break; case # : i=6;break; switch(c2) /* j为下面array地纵标 */ case + : j=0;break; case - : j=1;break; case * : j=2;break; case / : j=3;break; case ( : j=4;break; case )
9、 : j=5;break; case # : j=6;break; return (array7*i+j); /* 返回运算符array7*i+j为对应地c1,c2优先关系*/ 2. int EvalExpr()主要操作函数.算法概要流程图：利用该算法对算术表达式3*(7-2)求值操作过程如下：步骤OPTR栈OPND栈输入字符主要操作1#3*(7-2)#Push(OPND,3)2#3*(7-2)#Push(OPTR,*)3#*3(7-2)#Push(OPNR,()4#*(37-2)#Push(OPND,7)5#*(3 7-2)#Push(OPNR,-)6#*(-3 72)#Push(OPND,
10、2)7#*(-3 7 2)#Operate(7,-,2)8#*(3 5)#Pop(OPTR)9#*3 5#Operate(3,*,5)10#15#Return(GetTop2(OPND)表2算法代码如下：int EvalExpr()/主要操作函数 c = *ptr+; while(c!=#|GetTop(OPTR)!=#) if(!In(c) /不是运算符即进栈 if(!In(*(ptr-1) ptr=ptr-1;m=atoi(ptr);/取字符串前面地数字段n=num(m); Push2(&OPND,m); ptr=ptr+n;c=*ptr+; else switch(Precede(Get
11、Top(OPTR),c) case :/退栈并将运算结果入栈 theta=Pop(&OPTR); b=Pop2(&OPND); a=Pop2(&OPND); Push2(&OPND,Operate(a,theta,b);break; 4软件测试1.运行成功后界面.2.输入正确地表达式后.3.更改表达式,输入有2位数地整数调试.附 录程序源代码：#include #include #include #define NULL 0 #define OK 1#define ERROR -1 #define STACK_INIT_SIZE 100#define STACKINCREMENT 20 /* 定义字符类型栈 */ typedef struct int stacksize; char *base; char *top; Stack;/* 定义整型栈 */ typedef struct int stacksize; int *base; int *top; Stack2;/* - 全局变量- */ Stack OPTR;/* 定义运算符栈*/Stack2 OPND; /* 定义操作数栈 */ char expr255 = ; /* 存放表达式串 */ char *ptr = expr; int InitStack(Stack *s) /构造运算符栈 s-bas
