《数据结构实习报告_设计一个演示用运算优先法对算数表达式求值过程的程序》由会员分享,可在线阅读,更多相关《数据结构实习报告_设计一个演示用运算优先法对算数表达式求值过程的程序(21页珍藏版)》请在金锄头文库上搜索。
1、 . . . .实习报告题目:设计一个演示用运算优先法对算数表达式求值过程的程序。班级: 姓名: 学号: 完成日期: 一、 需求分析1建立运算数栈SqStack1和运算符栈SqStack2辅助分析算符有限关系.2用户输入以“#”结尾的算数表达式,本程序需要用户自行输入表达式(运算符可以是加(+);减(-);乘(*);除(/);括号(),以字符形式读入,在读入的同时,完成运算符和运算数的识别处理,在识别出运算数的同时,要将其字符序列形式转换成整数形式。3在程序的适当位置输出运算符栈、运算数栈、输入字符和主要操作的内容,即演示运算操作。4测试数据见原题。5程序执行的命令包括:(1) 建立算数表达式
2、;(2) 得到运算表达式的值;(3) 演示运算过程。二、 概要设计1. 设定栈的抽象数据类型定义:ADT Stack数据对象 D ai | ai charSet, i=1,2,.,n, n0 数据关系: R1 | ai-1, aiD, i=2,.,n (约定an 端为栈顶,a1 端为栈底)基本操作:InitStack(&S)操作结果:构造一个空栈S。Gettop(S,&e)初始条件:栈S已存在。操作结果:若栈S不空,则以e返回栈顶元素。Push(&S,e)初始条件:栈 S 已存在。操作结果:插入元素 e 为新的栈顶元素。Pop(&S,&e)初始条件:栈 S 已存在且非空。操作结果:删除 S 的
3、栈顶元素,并用 e 返回其值。ADT Stack2. 本程序包括三个模块(1)主程序模块:Void main( )初始化;函数; (2)栈模块实现栈抽象数据类型(3)运算模块实现运算并演示其过程模块各模块之间调用关系如下:主程序模块运算模块栈模块三、详细设计1、 元素类型、结点类型typedef structint *base;int *top;int stacksize;SqStack1;/操作数栈typedef structchar *base;char *top;int stacksize;SqStack2;/操作符栈2、 栈类型typedef structchar *base;char
4、 *top;int stacksize;Stack;/栈类型栈的基本操作设置如下:void InitStack(Stack &S)/初始化,设S为空栈(S.top=NULL)Status GetTop(Stack S,ElemType e)/若栈S不空,则以e带回栈顶元素并返回TRUE,否则返回FALSEStatus Push(Stack&S,ElemType e)/若分配空间成功,则在S的栈顶插入新的栈顶元素e,并返回TRUE,/否则返回FALSE其中部分操作的算法:Status Push(Stack &S,ElemType e)/若分配空间成功,则在S的栈顶插入新的栈顶元素e,并返回TRU
5、E;/否则栈不变,并返回FALSEif(MakeNode(p,e) P.next=S.top;S.top=p; S.size+; Return TRUE; else return FALSE;Status Pop(Stack &S,ElemType &e)/若栈不空,则删除S的栈顶元素并以e带回其值,且返回TRUE,/否则返回FALSE,且e无意义if(StackEmpty(S) return FALSE;elsep=S.top;S.top=S.top-next;e=p-:data;S.size-;return TRUE;3、运算代码int Operate(int a,char theta,i
6、nt b) /计算表达式值:主要是将大的表达式转化成小的表达式进行逐步求值 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 result(SqStack1 *OPND,SqStack2 *OPTR) /求值char a=0;char theta;int b,c,number=0;IntInitStack(OPND);CharInitStack(OPTR);CharPush(OPTR,#);a=getchar();while(a!=# | C
7、harGetTop(OPTR)!=#) printf(输入字符:%c ,a);if(!In(a)/不是运算符则进栈number=0;while(!In(a)number = number*10 +(a-48);/处理多位整数z=10*x+ya = getchar();IntPush(OPND,number); printf(主要操作:Push(OPND,%d) ,number);else switch(Precede(a,CharGetTop(OPTR)case :theta=CharPop(OPTR);c=IntPop(OPND);b=IntPop(OPND);IntPush(OPND,Op
8、erate(b,theta,c);printf(主要操作:Operate(%d,%c,%d) ,b,theta,c);break;printf(OPND栈:%d OPTR栈:%cn,IntGetTop(OPND),CharGetTop(OPTR);printf(The result is %d.n,IntGetTop(OPND); /打印输出表达式值return OK;4.主函数和其他函数的代码void main() /主函数,使用自定义函数完成功能 SqStack1 s1,*OPND;SqStack2 s2,*OPTR;OPND=&s1;OPTR=&s2;printf(Please ente
9、r an expression with a end of #.n);printf(The Expression:);result(OPND,OPTR);char Precede(char a,char b)/运算优先级判断int i,j;char Table88= ,+,-,*,/,(,),#,+,-,*,/,(, ,#, ,=,; /优先级表格for(i=0;i8;i+)if(Table0i=a) /纵坐标寻找break;for(j=0;j8;j+) /横坐标寻找if(Tablej0=b)break;return Tableji;int In(char c) /判断c是否为操作符if (
10、c=( | c=+ | c=- | c = * | c=/ | c=) | c=# | c=)return 1;/如果是操作符返回1elsereturn 0;/不是,返回05函数的调用关系图反映了演示程序的层次结构: mainresultInitStackPushGetTopInPrecedePop四、调试分析算术表达式求值程序较为庞大,调试花费时间较多,主要是在for循环和while循环时容易出错,对于涉及的循环的操作开始和结束条件设置很关键。五、用户手册1. 本程序开发环境为VC 6.0,运行环境为dos操作系统,执行文件为:1.exe2. 运行该程序后,产生如下图所示的界面:3. 按照提
11、示输入一组表达式。4. 输入完成后,按回车键。5. 屏幕上打印出对应于该表达式的后缀表达式。6. 打印表达式计算结果。六、测试结果1.2.34.七、附录源程序文件名清单:1.cpp /主程序1.exe /可执行文件stdio.h /程序中用到的头文件stdlib.h /程序中用到的头文件string.h /程序中用到的头文件math.h /程序中用到的头文件程序代码:#include #include #include#include#define STACK_INIT_SIZE 100#define STACKINCREMENT 10#define ERROR 0#define OK 1/*栈模块typedef struct SqStack1/运算数栈int *base;int *top;int stacksize;SqStack1; typedef