数据结构实习报告：设计一个演示用运算优先法对算数表达式求值过程的程序。

实习报告题目：设计一个演示用运算优先法对算数表达式求值过程的程序。班级：姓名：学号：完成日期：一、需求分析1建立运算数栈SqStack1和运算符栈SqStack2辅助分析算符有限关系.2用户输入以“#”结尾的算数表达式，本程序需要用户自行输入表达式（运算符可以是加（+）；减（-）；乘（*）；除（/）；括号（（））），以字符形式读入，在读入的同时，完成运算符和运算数的识别处理，在识别出运算数的同时，要将其字符序列形式转换成整数形式。3在程序的适当位置输出运算符栈、运算数栈、输入字符和主要操作的内容，即演示运算操作。4测试数据见原题。5程序执行的命令包括：（1）建立算数表达式；（2）得到运算表达式的值；（3）演示运算过程。二、概要设计1.设定栈的抽象数据类型定义：ADTStack{数据对象D＝{ai|ai∈charSet,i=1,2,...,n,n≥0}数据关系：R1＝{ai-1,ai|ai-1,ai∈D,i=2,...,n}（约定an端为栈顶，a1端为栈底）基本操作：InitStack（&S）操作结果：构造一个空栈S。Gettop(S,&e)初始条件：栈S已存在。操作结果：若栈S不空，则以e返回栈顶元素。Push(&S,e)初始条件：栈S已存在。操作结果：插入元素e为新的栈顶元素。Pop(&S,&e)初始条件：栈S已存在且非空。操作结果：删除S的栈顶元素，并用e返回其值。}ADTStack2.本程序包括三个模块（1）主程序模块：Voidmain(){初始化；函数；}（2）栈模块——实现栈抽象数据类型（3）运算模块——实现运算并演示其过程模块各模块之间调用关系如下：三、详细设计1、元素类型、结点类型typedefstruct{int*base;int*top;intstacksize;}SqStack1;//操作数栈typedefstruct{char*base;char*top;intstacksize;}SqStack2;//操作符栈2、栈类型typedefstruct{char*base;char*top;intstacksize;}Stack;//栈类型栈的基本操作设置如下：voidInitStack(Stack&S)//初始化，设S为空栈（S.top=NULL）主程序模块运算模块栈模块StatusGetTop(StackS,ElemTypee)//若栈S不空，则以e带回栈顶元素并返回TRUE，否则返回FALSEStatusPush(Stack&S,ElemTypee)//若分配空间成功，则在S的栈顶插入新的栈顶元素e，并返回TRUE，//否则返回FALSE其中部分操作的算法：StatusPush(Stack&S,ElemTypee){//若分配空间成功，则在S的栈顶插入新的栈顶元素e，并返回TRUE；//否则栈不变，并返回FALSEif(MakeNode(p,e)){P.next=S.top;S.top=p;S.size++;ReturnTRUE;}elsereturnFALSE;}StatusPop(Stack&S,ElemType&e){//若栈不空，则删除S的栈顶元素并以e带回其值，且返回TRUE，//否则返回FALSE，且e无意义if(StackEmpty(S))returnFALSE;else{p=S.top;S.top=S.top-next;e=p-:data;S.size--;returnTRUE;}}3、运算代码intOperate(inta,chartheta,intb)//计算表达式值：主要是将大的表达式转化成小的表达式进行逐步求值{intc;if(theta=='+')c=a+b;elseif(theta=='-')c=a-b;elseif(theta=='*')c=a*b;elsec=a/b;returnc;}//Operateintresult(SqStack1*OPND,SqStack2*OPTR)//求值{chara=0;chartheta;intb,c,number=0;IntInitStack(OPND);CharInitStack(OPTR);CharPush(OPTR,'#');a=getchar();while(a!='#'||CharGetTop(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);}elseswitch(Precede(a,CharGetTop(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=CharPop(OPTR);c=IntPop(OPND);b=IntPop(OPND);IntPush(OPND,Operate(b,theta,c));printf(主要操作：Operate(%d,%c,%d),b,theta,c);break;}printf(OPND栈：%dOPTR栈：%c\n,IntGetTop(OPND),CharGetTop(OPTR));}printf(Theresultis%d.\n,IntGetTop(OPND));//打印输出表达式值returnOK;}4.主函数和其他函数的代码voidmain()//主函数，使用自定义函数完成功能{SqStack1s1,*OPND;SqStack2s2,*OPTR;OPND=&s1;OPTR=&s2;printf(Pleaseenteranexpressionwithaendof'#'.\n);printf(TheExpression:);result(OPND,OPTR);}charPrecede(chara,charb)//运算优先级判断{inti,j;charTable[8][8]={'','+','-','*','/','(',')','#','+','','','','','','','','-','','','','','','','','*','','','','','','','','/','','','','','','','','(','','','','','','=','',')','','','','','','','','#','','','','','','','=',};//优先级表格for(i=0;i8;i++)if(Table[0][i]==a)//纵坐标寻找break;for(j=0;j8;j++)//横坐标寻找if(Table[j][0]==b)break;returnTable[j][i];}intIn(charc)//判断c是否为操作符{if(c=='('||c=='+'||c=='-'||c=='*'||c=='/'||c==')'||c=='#'||c=='^')return1;//如果是操作符返回1elsereturn0;//不是，返回0}5．函数的调用关系图反映了演示程序的层次结构：四、调试分析算术表达式求值程序较为庞大，调试花费时间较多，主要是在for循环和while循环时容易出错，对于涉及的循环的操作开始和结束条件设置很关键。五、用户手册1.本程序开发环境为VC6.0，运行环境为dos操作系统，执行文件为：1.exe2.运行该程序后,产生如下图所示的界面：mainresultInitStackPushGetTopInPrecedePop3.按照提示输入一组表达式。4.输入完成后，按回车键。5.屏幕上打印出对应于该表达式的后缀表达式。6.打印表达式计算结果。六、测试结果1.2.34.七、附录源程序文件名清单：1.cpp//主程序1.exe//可执行文件stdio.h//程序中用到的头文件stdlib.h//程序中用到的头文件string.h//程序中用到的头文件math.h//程序中用到的头文件程序代码：：#includestdio.h#includestdlib.h#includestring.h#includemath.h#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10#defineERROR0#defineOK1//********************************************栈模块typedefstructSqStack1//运算数栈{int*base;int*top;intstacksize;}SqStack1;typedefstructSqStack2//运算符栈{char*base;char*top;intstacksize;}SqStack2;voidIntInitStack(SqStack1*S){S-base=(int*)malloc(STACK_INIT_SIZE*sizeof(int));if(!S-base)exit(ERROR);S-top=S-base;S-stacksize=STACK_INIT_SIZE;}voidCharInitStack(SqStack2*S){S-base=(char*)malloc(STACK_INIT_SIZE*sizeof(char));if(!S-base)exit(ERROR);S-top=S-base;S-stacksize=STACK_INIT_SIZE;}intIntGetTop(SqStack1*S)//取栈顶元素{inte;if((*S).top==(*S).base)return0;e=*((*S).top-1);returne;}charCharGetTop(SqStack2*S)//取栈顶元素{chare;if((*S).top==(*S).base)return0;e=*((*S).top-1);returne;}intIntPush(SqStack1*S,inte){*(*S).top++=e;returnOK;}intCharPush(SqStack2*S,chare){*(*S).top++=e;returnOK;}intIntPop(SqStack1*S){inte;if((*S).top==(*S).base)return0;e=*--(*S).top;returne;}intCharPop(SqStack2*S){chare;if((*S).top==(*S).base)return0;e=*--(*S).top;returne;}//——————————————————*******************运算模块charPrecede(chara,charb)//运算优先级判断{inti,j;charTable[8][8]={'','+','-','*','/','(',')','#','+','','','','','','','','-','','','','','','','','*','','','','','','','','/','','','','','','','','(','','','','','','=','',')','','','','','','','','#','','','','','','','=',};//优先级表格for(i=0