数据结构表达式求值实验报告

1、1 数据结构数据结构 课 程 设 计 报 告 书 题 目： 数据结构苏算术表达式求值 系 别： 数学院信息系统与信息管理 学 号： 1201324095 学生姓名： 梅影 指导教师： 李文强 完成日期： 2013-10-19 2 目录目录 1.概要设计 2.1 数据结构设计 2.2 算法设计 2.3 ADT 描述 2.4 功能模块分析 2.详细设计 3.1 数据存储结构设计 3.2 主要算法流程图（或算法代码） 3.软件测试 4.附 录 3 1概要设计概要设计 (1) 数据结构设计 任何一个表达式都是由操作符,运算符和界限符组成地.我们分别用顺序栈来寄存表达 式地操作数和运算符.栈是限定于紧仅

2、在表尾进行插入或删除操作地线性表.顺序栈地存储 结构是利用一组连续地存储单元依次存放自栈底到栈顶地数据元素,同时附设指针 top 指示 栈顶元素在顺序栈中地位置,base 为栈底指针,在顺序栈中,它始终指向栈底,即 top=base 可作为栈空地标记,每当插入新地栈顶元素时,指针 top 增 1,删除栈顶元素时,指针 top 减 1. (2) 算法设计 为了实现算符优先算法.可以使用两个工作栈.一个称为 OPTR,用以寄存运算符,另一个 称做 OPND,用以寄存操作数或运算结果. 1.首先置操作数栈为空栈,表达式起始符”#”为运算符栈地栈底元素； 2.依次读入表达式,若是操作符即进 OPND

3、栈,若是运算符则和 OPTR 栈地栈顶运算符比 较优先权后作相应地操作,直至整个表达式求值完毕（即 OPTR 栈地栈顶元素和当前读入地 字符均为”#” ）. (3) ADT 描述 ADT Stack 数据对象：D= |ElemSet,i=1,2,n, n0 i a i a 数据对象：R1=|,i=2,n 1 , ii aa 1i aDai 约定端为栈顶,端为栈底. n a i a 基本操作： InitStack( char *base; char *top; Stack; /* 定义整型栈 */ typedef struct int stacksize; int *base; int *top

4、; Stack2; (2) 主要算法流程图（或算法代码） 1. Precede(char c1,char c2) 判断运算符优先权,返回优先权高地. 算符间地优先关系如下： +-*/()# + - * / ( #, , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , !, , , , , , , , !, =; /用一维数组存储 49 种情况 switch(c1) /* i 为下面 array 地横标 */ case + : i=0;break; case - : i=1;break; case * : i=2;break

5、; 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 ) : j=5;break; case # : j=6;break; return (array7*i+j); /* 返回运算符 array7*i+j为对应地

6、c1,c2 优先关系*/ 2. int EvalExpr()主要操作函数.算法概要流程图： 7 利用该算法对算术表达式 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,2) 7#*(-3 7 2)#Operate(7,-,2) 8#*(3 5)#Pop(OPTR) 9#*3 5#Operate

7、(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);/取字符串前面地数字段 8 n=num(m); Push2( ptr=ptr+n; c=*ptr+; else switch(Precede(GetTop(OPTR),c) case :/退栈并将运算结果入栈 theta=Pop( b=Pop2( a=Pop2( P

8、ush2( break; 4 4软件测试软件测试 1.运行成功后界面. 9 2.输入正确地表达式后. 3.更改表达式,输入有 2 位数地整数调试. 10 附附 录录 程序源代码： #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; /* 定义整型栈 *

9、/ typedef struct int stacksize; int *base; int *top; Stack2; 11 /* - 全局变量- */ Stack OPTR;/* 定义运算符栈*/ Stack2 OPND; /* 定义操作数栈 */ char expr255 = ; /* 存放表达式串 */ char *ptr = expr; int InitStack(Stack *s) /构造运算符栈 s-base=(char *)malloc(STACK_INIT_SIZE*sizeof(char); if(!s-base) return ERROR; s-top=s-base; s

10、-stacksize=STACK_INIT_SIZE; return OK; int InitStack2(Stack2 *s) /构造操作数栈 s-base=(int *)malloc(STACK_INIT_SIZE*sizeof(int); if(!s-base) return ERROR; s-stacksize=STACK_INIT_SIZE; s-top=s-base; return OK; 12 int In(char ch) /判断字符是否是运算符,运算符即返回 1 return(ch=+|ch=-|ch=*|ch=/|ch=(|ch=)|ch=#); int Push(Stac

11、k *s,char ch) /运算符栈插入 ch 为新地栈顶元素 *s-top=ch; s-top+; return 0; int Push2(Stack2 *s,int ch)/操作数栈插入 ch 为新地栈顶元素 *s-top=ch; s-top+; return 0; char Pop(Stack *s) /删除运算符栈 s 地栈顶元素,用 p 返回其值 char p; s-top-; p=*s-top; 13 return p; int Pop2(Stack2 *s)/删除操作数栈 s 地栈顶元素,用 p 返回其值 int p; s-top-; p=*s-top; return p; c

12、har GetTop(Stack s)/用 p 返回运算符栈 s 地栈顶元素 char p=*(s.top-1); return p; int GetTop2(Stack2 s) /用 p 返回操作数栈 s 地栈顶元素 int p=*(s.top-1); return p; /* 判断运算符优先权,返回优先权高地 */ char Precede(char c1,char c2) 14 int i=0,j=0; static char array49= , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , !, , , ,

13、 , , , , !, =; switch(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; 15 switch(c2) /* j 为下面 array 地纵标 */ case + : j=0;break; case - : j=1;break; case * : j=2;break; case / : j=3;bre

14、ak; case ( : j=4;break; case ) : j=5;break; case # : j=6;break; return (array7*i+j); /* 返回运算符 */ /*操作函数 */ int Operate(int a,char op,int b) switch(op) case + : return (a+b); case - : return (a-b); case * : return (a*b); case / : return (a/b); 16 return 0; int num(int n)/返回操作数地长度 char p10; itoa(n,p,10);/把整型转换成字符串型 n=strlen(p); return n; int EvalExpr()/主要操作函数 char c,theta,x; int n,m; int a,b; c = *ptr+; while(c!=#|GetTop(OPTR)!=#) if(!In(c) if(!In(*(ptr-1) ptr=ptr-1; m=atoi(ptr);/取字符串前面地数字段 n=num(m); Push2( 17 ptr=ptr+n; c=*ptr+; else switch(Precede(GetTop(OPTR),c) case : theta=Po