算术表达式求值演示程序

数理学院课程设计报告书课程名称数据结构课程设计设计题目算术表达式求值演示专业班级学号姓名指导教师2014年12月1设计时间2014年12月23~2014年12月29日2设计目的设计一个程序，演示算符优先法对算术表达式求值的过程。利用算符优先关系，实现对算术四则混合运算表达式的求值。3设计任务(1)设置运算符栈和运算数栈辅助分析算符优先关系；(2)在读入表达式的字符序列的同时，完成运算符和运算数的识别处理，以及相应的运算；(3)在识别出运算数的同时，要将其字符序列形式转换成整数形式；(4)在程序的适当位置输出运算符栈、运算数栈、输入字符和主要操作的内容。4设计内容4.1需求分析4.1.1该程序能实现算术四则运算表达式的求值，显示运算过程。4.1.2输入的形式：表达式，例如5*（3+7）#。包含的运算符只能有'+'、'-'、'*'、'/'、'('')'；4.1.3输出的形式：运算结果，50。4.1.4程序所能达到的功能：对表达式求值并输出。4.2总体设计4.2.1①.栈的抽象数据类型定义：ADTStack{数据对象：D={ai|ai∈Char,i=1,2.......,n,n≥0}数据关系：R1={＜ai-1,ai＞|ai-1,ai∈D,i=2,3....n}约定an端为栈顶，ai端为栈底4.2.2基本操作：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为运算符。操作结果：判断运算符优先权，返回优先权高的。Operate(a,op,b)初始条件：a,b为整数，op为运算符。操作结果：a与b进行运算，op为运算符，返回其值。num(n)操作结果：返回操作数的长度。EvalExpr()初始条件：输入表达式合法。操作结果：返回表达式的最终结果。}ADTStack主程序的流程：EvaluateExpression()函数实现了对表达式求值的功能，main()函数直接调用EvaluateExpression()对输入的表达式求值输出。算法流程图4.2.3函数的调用关系图mainEvaluateExpressionPushprecedeInPopReturnOpOrdOperate输出4.3详细设计4.3.1①.Precede(charc1,charc2)判断运算符优先权，返回优先权高的。算符间的优先关系如下：+-*/()#+-*/(=)#=算法伪代码如下：charPrecede(charc1,charc2){staticchararray[49]={'','','','','','','','','','','','','','','','','','','','','','','','','','','','','','','','','','=','!','','','','','!','','','','','','','','!','='};//用一维数组存储49种情况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;}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(array[7*i+j]);/*返回运算符array[7*i+j]为对应的c1,c2优先关系*/}②利用该算法对算术表达式4*(6-2)求值操作过程如下：步骤OPTR栈OPND栈输入字符主要操作1#4*(6-2)#Push(OPND,’4’)2#4*(6-2)#Push(OPTR,’*’)3#*4(6-2)#Push(OPNR,’(’)4#*(46-2)#Push(OPND,’6’)5#*(46-2)#Push(OPNR,’-’)6#*(-462)#Push(OPND,’2’)7#*(-462)#Operate(‘6’,’-’,’2’)8#*(44)#Pop(OPTR)9#*44#Operate(‘4’,’*’,4’)10#16#Return(GetTop2(OPND))算法伪代码如下：intEvalExpr()//主要操作函数{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++;}elseswitch(Precede(GetTop(OPTR),c)){case''://栈顶元素优先权底Push(&OPTR,c);c=*ptr++;break;case'='://脱括号并接收下一字符x=Pop(&OPTR);c=*ptr++;break;case''://退栈并将运算结果入栈theta=Pop(&OPTR);b=Pop2(&OPND);a=Pop2(&OPND);Push2(&OPND,Operate(a,theta,b));break;}}4.3.2主函数和其他函数的伪码intmain(){printf(请输入正确的表达式以'#'结尾:);do{gets(expr);}while(!*expr);InitStack(&OPTR);/*初始化运算符栈*/Push(&OPTR,'#');/*将#压入运算符栈*/InitStack2(&OPND);/*初始化操作数栈*/printf(表达式结果为:%d\n,EvalExpr());return0;}4.3.3函数的调用关系图调用关系图4.4测试与分析4.4.1测试mainEvaluateExpressionPushprecedeInPopReturnOpOrdOperate输出4.4.2实验分析：表达式求值程序是一个多次调用函数的过程，且调用的过程较为复杂，调试花费时间较多。在while循环时指针移动容易出错，因此多次出现内存错误，对于涉及的循环的操作开始和结束条件设置很关键。本次实验熟悉了栈数据结构的表示与实现方法。算法时间和空间分析：算法的运行时间主要花在while循环上，它从头到尾扫描后缀表达式中的每一个数据（每个操作数或运算符均为一个数据），若后缀表达式由n个数据组成，则此算法的时间复杂度为O(n)。此算法在运行时所占用的临时空间主要取决于栈S的大小，显然，它的最大深度不会超过表达式中操作数的个数，因为操作数的个数与运算符（假定把’#’也看作为一个特殊运算符，即结束运算符）的个数相等，所以此算法的空间复杂度也同样为O(n)。4.5附录源程序：#includestdio.h#includestdlib.h#includestring.h#defineNULL0#defineOK1#defineERROR-1#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT20/*定义字符类型栈*/typedefstruct{intstacksize;char*base;char*top;}Stack;/*定义整型栈*/typedefstruct{intstacksize;int*base;int*top;}Stack2;/*-----------------全局变量---------------*/StackOPTR;/*定义运算符栈*/Stack2OPND;/*定义操作数栈*/charexpr[255]=;/*存放表达式串*/char*ptr=expr;intInitStack(Stack*s)//构造运算符栈{s-base=(char*)malloc(STACK_INIT_SIZE*sizeof(char));if(!s-base)returnERROR;s-top=s-base;s-stacksize=STACK_INIT_SIZE;returnOK;}intInitStack2(Stack2*s)//构造操作数栈{s-base=(int*)malloc(STACK_INIT_SIZE*sizeof(int));if(!s-base)returnERROR;s-stacksize=STACK_INIT_SIZE;s-top=s-base;returnOK;}intIn(charch)//判断字符是否是运算符，运算符即返回1{return(ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch=='('||ch==')'||ch=='#');}intPush(Stack*s,charch)//运算符栈插入ch为新的栈顶元素{*s-top=ch;s-top++;return0;}intPush2(Stack2*s,intch)//操作数栈插入ch为新的栈顶元素{*s-top=ch;s-top++;return0;}charPop(Stack*s)//删除运算符栈s的栈顶元素，用p返回其值{charp;s-top--;p=*s-top;returnp;}intPop2(Stack2*s)//删除操作数栈s的栈顶元素，用p返回其值{intp;s-top--;p=*s-top;returnp;}charGetTop(Stacks)//用p返回运算符栈s的栈顶元素{charp=*(s.top-1);returnp;}intGetTop2(Stack2s)//用p返回操作数栈s的栈顶元素{intp=*(s.top-1);returnp;}/*判断运算符优先权，返回优先权高的*/charPrecede(charc1,charc2){inti=0,j=0;staticchararray[49]={'','','','','','','','','','','','','','','','','','','','','','','','','','','','','','','','','','=','!','','','','','!','','','','','','','','!','='};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;}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(array[7*i+j]);/*返回运算