《数据结构实习报告设计一个演示用运算优先法对算数表达式求值过程的程序.doc》由会员分享，可在线阅读，更多相关《数据结构实习报告设计一个演示用运算优先法对算数表达式求值过程的程序.doc（23页珍藏版）》请在三一文库上搜索。
1、.WORD完美格式.专业知识编辑整理实习报告题目：设计一个演示用运算优先法对算数表达式求值过程的程序。班级：姓名：学号：完成日期：一、需求分析1建立运算数栈SqStackl和运算符栈SqStack2辅助分析算符有限关 系.2用户输入以“ #”结尾的算数表达式，本程序需要用户自行输入表 达式（运算符可以是加（+）;减（-）;乘（*）;除（/）；括号（）， 以字符形式读入，在读入的同时，完成运算符和运算数的识别处理， 在识别出运算数的同时，要将其字符序列形式转换成整数形式。3在程序的适当位置输出运算符栈、运算数栈、输入字符和主要操作 的内容，即演示运算操作。4测试数据见原题。5程序执行的命令包括：
2、（1）建立算数表达式；（2）得到运算表达式的值；（3）演示运算过程。二、概要设计1. 设定栈的抽象数据类型定义：ADT Stack数据对象n0 D= ai | ai charSet, i=1,2，,n,数据关系：R1 = <ai-1, ai >| ai-1, ai D, i=2,n (约定an端为栈顶，al端为栈底)基本操作：InitStack ( &S)操作结果：构造个空栈SoGettop(S,&e)初始条件：栈S已存在。操作结果：右栈S不空，则以e返回栈顶兀素。Push(&S,e)初始条件：栈S已存在。操作结果：插入兀素e为新的栈顶兀素。Pop (&am
3、p;S, &e)初始条件：栈S已存在且非空。操作结果：删除S的栈顶兀素，并用e返回其值。ADT Stack2. 本程序包括三个模块(1) 主程序模块：Void mai n()初始化;函数；(2) 栈模块实现栈抽象数据类型(3) 运算模块一一实现运算并演示其过程模块各模块之间调用关系如下：主程序模块运算模块栈模块三、详细设计1、元素类型、结点类型typedef structint *base;int *top;/操作数栈/操作符栈int stacksize; SqStack1; typedef struct char *base; char *top;int stacksize; SqS
4、tack2;2、栈类型typedef structchar *base;char *top; int stacksize;Stack; / 栈类型栈的基本操作设置如下：void In itStack(Stack &S)/初始化，设S为空栈(S.top=NULL).WORD完美格式.Status GetT op(Stack S,ElemT ype e)/若栈S不空，则以e带回栈顶元素并返回TRUE,否则返回FALSEStatus Push(Stack&S,ElemT ype e)/若分配空间成功，则在 S的栈顶插入新的栈顶元素e,并返回TRUE,/否则返回FALSE其中部分操作的
5、算法：Status Push(Stack &S,ElemT ype e)/若分配空间成功，则在S的栈顶插入新的栈顶元素e,并返回TRUE；/否则栈不变，并返回FALSEif(MakeNode(p,e)Pn ext=S.top;S.top=p;S.size+;Retur n TRUE;else return FALSE;Status Pop(Stack & S,ElemT ype &e)/若栈不空，则删除S的栈顶元素并以e带回其值，且返回TRUE,/否则返回FALSE且e无意义if(StackEmpty(S) return FALSE;elsep=S.top;S.top=
6、S.top->n ext;e=p->:data;S.size-;return TRUE;3、运算代码int Operate( int a,char theta,i nt b) /计算表达式值：主要是将大的表达式转化成小的表达式进行逐步求值in t c;if(theta='+') c=a+b;else if(theta='-') c=a-b;else if(theta='*') c=a*b;else c=a/b;return c;/Operatein t result(SqStack1 *OPND,SqStack2 *OPTR) / 求
7、值char a=0;char theta;int b,c ,nu mber=0;In tin itStack(OPND); Chari nitStack(OPTR); CharPush(OPTR,#);a=getchar();while(a!=# | CharGetT op(OPTR)!=#) printf("输入字符：%c ",a);if(!In(a)/不是运算符则进栈 nu mber=0;while(!I n(a)number = number*10 +(a-48);/ 处理多位整数z=10*x+ya = getchar();in tPush(OPND, nu mber
8、);printf("主要操作：Push(OPND,%d)",number);elseswitch(Precede(a,CharGetT op(OPTR)case '<':CharPush(OPTR,a);a=getchar();printf("主要操作：Push(OPTR,%c)",a);break;case '=':CharPop(OPTR);a=getchar();printf("主要操作：Pop(OPTR,%c)",a);break;case '>':theta=Cha
9、rPop(OPTR);c=i ntPop(OPND);b=i ntPop(OPND);in tPush(OPND,Operate(b,theta,c);printf("主要操作：Operate(%d,%c,%d) ",b,theta,c); break;prin tf("OPND栈:%dOPTR栈：%cn",intGetTop(OPND),CharGetTop(OPTR);printf("The result is %d.n",intGetTop(OPND); / 打印输出表达式值return OK;4. 主函数和其他函数的代码voi
10、d ma in () /主函数，使用自定义函数完成功能SqStack1 s1,*OPND;SqStack2 s2,*OPTR;OPND=&s1;OPTR=&s2;prin tf("Please en ter an expressi on with a end of #.n");prin tf("The Expressi on:”)； result(OPND,OPTR);char Precede(char a,char b)/运算优先级判断int i,j;char Table88='''+' '- '*
11、' '/' '(' ')' '#''+ ''>''>''<''<''<''>''>'J J J J J J J J'''>''>''<''<''<''>''>' J J J J J J J
12、 J'*''>''>''>''>''<''>''>'JJJJJJ JJ'/''>''>''>''>''<''>''>'/，JJJJJ JJ'(''<''<''<''<
13、;''<''_''' JJJJJJ JJ')''>''>''>''>''''>''>'/ J J J J J J J Jf f J J J J J J J J; /优先级表格for(i_0;i<8;i+)if(T able0i_a) / 纵坐标寻找break;for(j_0;j<8;j+) / 横坐标寻找if(Tablej0_b)break;return T
14、ableji;int In(char c)/判断c是否为操作符if ( c_'(' | c_'+' | c_'-' | c _ '*'| c_'/' | c_')' | c_'#'| c_'A') return 1;/如果是操作符返回1elsereturn 0;/不是，返回05 .函数的调用关系图反映了演示程序的层次结构：四、调试分析算术表达式求值程序较为庞大，调试花费时间较多，主要是在for循环和while循环时容易出错，对于涉及的循环的操作开始和结束条件设 置很关
15、键。五、用户手册1. 本程序开发环境为 V 6.0,运行环境为dos操作系统，执行文件为：1.exe2. 运行该程序后，产生如下图所示的界面：I * C:Use rslencvcDesktop|$队歹!JlDebugl.exe,=i 凹 肚3. 按照提示输入一组表达式4. 输入完成后，按回车键。.专业知识编辑整理.WORD完美格式.5. 屏幕上打印出对应于该表达式的后缀表达式6. 打印表达式计算结果。六、测试结果1.3.专业知识编辑整理2.key to cont inue半:结果Press any戋戋戋戋戋戋戋戋戋5333772551戋 戋戋戋戋戋戋戋戋* TJr_.TTJr_!TJr_!TJ
16、r_! R RRRRRRRRT TTTTTTTTP ppppppppo ooooooooPush<OPND,3> Pusli<OPTR,<> Push<0PTR,7> Pusli<0PND,7> Push<OPTR,2> Pusli<OPND,2> Operate<7,-,2> Pop<OPTB,#> OperatE(3,*,5>丄 4二.e_.e厂Jr-二.e厂Jr-二p二r-二p- 祁>#要要要要要要要要要 t'-2主±-i-壬主±-i-壬主 m 7
17、达3*<®3 * <7 - 2>># Alxaxaxax.WORD完美格式.专业知识编辑整理亡bugM < - -'；PusJKOPND, t Push<OPTB, :Pusli<OPND, ：0per4te<l, :Push<OPTR, :Pusli<OPNP, t Operate(3, ；PushtOPTR, :Push<OFN», :0perate<6,+ ,2>33>MrrN.TJ応-.T D D D D D DH4>4>OPND>：OPHD 咦 iOPND
18、>S：A10OPTR1： U OPT用:热+ QPTfV戋：+ OFTR找i tt OPT阳春+OPTR1:t + QPTJfl Ji ttOPT H啜：+OFTR 栈 i +OPTR桟：#结果：込Press any key to continuie4.'C.lJ5er5le novoD esktopVQ Ek?ClDeb ugl. exe ”s-2IAAAAAAA 请尊询諭丄Ig黑la卿48繆夷达式幷以结屋K = 1024/4-«#:1iln:Push<OPMD,1024>；Pu31i<OPTR,4>:PUsh<OPMD,4>；Op
19、erate<1024,Z,4>:Push<OPTB.8>:Pusli<OPND,B>:Operate<256,*,8>OPNDtJ： 1024OPND 桟；1B24 OPTOPHD 栈；4 OPT H栈；/OPND 栈；256 OPTR 桟；tt OPNDttt 256 OPT*桟；* OPHD栈 i 8 OPTR桟：*OPND栈！ 208 OPTRjft- tt:tt结杲池04g.Press anu key to continue七、附录源程序文件名清单：l.cpp/主程序1.exe/可执行文件stdio.h/程序中用到的头文件stdlib.h
20、/程序中用到的头文件string.h/程序中用到的头文件math.h/程序中用到的头文件程序代码：#in clude<stdio.h>#in clude<stdlib.h>#in clude<stri ng.h>#in clude<math.h>#defi ne STACK_INIT_SIZE 100#defi ne STACKINCREMENT 10#defi ne ERROR 0#defi ne OK 1*栈模块typedef struct SqStack1 运算数栈int *base;int *top;int stacksize;SqSta
21、ck1;typedef struct SqStack2 运算符栈char *base;char *top;int stacksize;SqStack2;void Intln itStack(SqStack1 *S)S->base=(i nt *)malloc(STACK_INIT_SIZE*sizeof(i nt);if(!S->base) exit(ERROR);S->top二S->base;S->stacksize二STACK_INIT_SIZE;void CharI nitStack(SqStack2 *S)S->base=(char *)malloc
22、(STACK_INIT_SIZE*sizeof(char);if(!S->base) exit(ERROR);S->top=S->base;S->stacksize=STACK_INIT_SIZE;int IntGetT op(SqStack1 *S) / 取栈顶元素int e;if(*S).top=(*S).base)return 0;e=*(*S).top-1);retur n e;char CharGetT op(SqStack2 *S) / 取栈顶元素char e;if(*S).top=(*S).base) return 0;e=*(*S).top-1);ret
23、ur n e;int In tPush(SqStack1 *S,i nt e)*(*S).top+=e;retur n OK;int CharPush(SqStack2 *S,char e)*(*S).top+=e;retur n OK; int In tPop(SqStack1 *S)int e;if(*S).top=(*S).base) return 0;e=*-(*S).top;retur n e;int CharPop(SqStack2 *S)char e;if(*S).top=(*S).base) return 0;e=*-(*s).top;retur n e;/* 运算模块char
24、 Precede(char a,char b)/运算优先级判断int i,j;char Table88=<''<''<# ,'V','V','V' /优先级表格for(i=0;i<8;i+)if(TableOi=a)/纵坐标寻找break;for(j=0;j<8;j+) /横坐标寻找if(Tablej0=b)break;retur n Tableji;int Operate©nt a,char theta,int b) /计算表达式值：主要是将大的表达式转化成小的表达式进行逐
25、步求值int c;if(theta='+') c=a+b;else if(theta='-') c=a-b;else if(theta='*') c=a*b;else c=a/b;return c;/Operateint In(char c)/判断c是否为操作符if ( c='(' | c='+' | c='-' | c = '*'| c='/' | c=')' |c=#| c='A')return 1;/如果是操作符返回1elsere
26、turn 0;/不是，返回0in t result(SqStack1 *OPND,SqStack2 *OPTR) /char a=0;char theta;int b,c ,nu mber=0;Intln itStack(OPND);Chari nitStack(OPTR);CharPush(OPTR, '#');a=getchar();while(a!='#' | CharGetT op(OPTR)!二'#')printf("输入字符：%c ",a);if(!l n(a)/不是运算符则进栈nu mber=0;while(!l
27、 n(a)nu mber = nu mber*10 +(a-48);求值/处理多位整数z=10*x+ya = getchar();In tPush(OPND, nu mber);pri ntf(”主要操作： Push(OPND,%d)”,nu mber);elseswitch(Precede(a,CharGetT op(OPTR)case '<':CharPush(OPTR,a);a=getchar();printf("主要操作：Push(OPTR,%c)",a);break;case '=':CharPop(OPTR);a=getch
28、ar();printf("主要操作：Pop(OPTR,%c)",a);break;case '>':theta二CharPop(OPTR);c=I ntPop(OPND);b=I ntPop(OPND);In tPush(OPND,Operate(b,theta,c);printf(" 主 要操作 ： Operate(%d,%c,%d)",b,theta,c);break;prin tf("OPND栈 ：%dOPTR栈：%cn",lntGetT op(OPND),CharGetT op(OPTR);printf("n 结果:%d.n",IntGetT op(OPND); / 打印输出表达式值 retur n OK;/主程序模块void ma in ()/主函数，使用自定义函数完成功能SqStack1 s1,*OPND;SqStack2 s2,*OPTR;OPND 二&s1;OPTR=&s2;printf("请输入算数表达式并以#结尾.n");printf(”算数表达式:”); result(OPND,OPTR);