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

数据构造课程 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 .-第PAGE12页.优选-----优质-TOC\o"1-3"\h\z\uHYPERLINK\l"_Toc263024560"1．前言PAGEREF_Toc263024560\h1HYPERLINK\l"_Toc263024561"2．概要设计PAGEREF_Toc263024561\h1HYPERLINK\l"_Toc263024562"2.1数据构造设计PAGEREF_Toc263024562\h1HYPERLINK\l"_Toc263024563"2.2算法设计PAGEREF_Toc263024563\h1HYPERLINK\l"_Toc263024564"2.3ADT描述PAGEREF_Toc263024564\h2HYPERLINK\l"_Toc263024565"2.4功能模块分析PAGEREF_Toc263024565\h2HYPERLINK\l"_Toc263024566"3．详细设计PAGEREF_Toc263024566\h3HYPERLINK\l"_Toc263024567"3.1数据存储构造设计PAGEREF_Toc263024567\h3HYPERLINK\l"_Toc263024568"3.2主要算法 流程 快递问题件怎么处理流程河南自建厂房流程下载关于规范招聘需求审批流程制作流程表下载邮件下载流程设计 图〔或算法伪代码〕PAGEREF_Toc263024568\h3HYPERLINK\l"_Toc263024569"4．软件测试PAGEREF_Toc263024569\h6HYPERLINK\l"_Toc263024570"5．心得体会PAGEREF_Toc263024570\h8HYPERLINK\l"_Toc263024571"参考文献PAGEREF_Toc263024571\h8HYPERLINK\l"_Toc263024572"附录PAGEREF_Toc263024572\h81．前言在计算机中，算术表达式由常量、变量、运算符和括号组成。由于不同的运算符具有不同的优先级，又要考虑括号，因此，算术表达式的求值不可能严格地从左到右进展。因而在程序设计时，借助栈实现。算法输入：一个算术表达式，由常量、变量、运算符和括号组成〔以字符串形式输入〕。为简化，规定操作数只能为正整数，操作符为+、-*、/，用*表示完毕。算法输出：表达式运算结果。算法要点：设置运算符栈和运算数栈辅助分析算符优先关系。在读入表达式的字符序列的同时，完成运算符和运算数的识别处理，以及相应运算。2．概要设计2.1数据构造设计任何一个表达式都是由操作符，运算符和界限符组成的。我们分别用顺序栈来存放表达式的操作数和运算符。栈是限定于紧仅在表尾进展插入或删除操作的线性表。顺序栈的存储构造是利用一组连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top指示栈顶元素在顺序栈中的位置，base为栈底指针，在顺序栈中，它始终指向栈底，即top=base可作为栈空的标记，每当插入新的栈顶元素时，指针top增1，删除栈顶元素时，指针top减1。2.2算法设计为了实现算符优先算法。可以使用两个工作栈。一个称为OPTR，用以存放运算符，另一个称做OPND，用以存放操作数或运算结果。1.首先置操作数栈为空栈，表达式起始符〞*〞为运算符栈的栈底元素；2.依次读入表达式，假设是操作符即进OPND栈，假设是运算符则和OPTR栈的栈顶运算符比拟优先权后作相应的操作，直至整个表达式求值完毕〔即OPTR栈的栈顶元素和当前读入的字符均为〞*〞〕。2.3ADT描述ADTStack{数据对象：D={|∈ElemSet,i=1,2,…，n,n≧0}数据对象：R1={<>|,,i=2,…，n}约定端为栈顶，端为栈底。根本操作：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)操作结果：返回操作数的长度。EvalE*pr()初始条件：输入表达式合法。操作结果：返回表达式的最终结果。}ADTStack2.4功能模块分析1.栈的根本功能。InitStack(Stack*s)和InitStack2(Stack2*s)分别构造运算符栈与构造操作数栈，Push(Stack*s,charch)运算符栈插入ch为新的栈顶元素，Push2(Stack2*s,intch)操作数栈插入ch为新的栈顶元素，Pop(Stack*s)删除运算符栈s的栈顶元素，用p返回其值，Pop2(Stack2*s)删除操作数栈s的栈顶元素，用p返回其值，GetTop(Stacks)用p返回运算符栈s的栈顶元素，GetTop2(Stack2s)用p返回操作数栈s的栈顶元素。2.其它功能分析。(1)In(charch)判断字符是否是运算符功能，运算符即返回1，该功能只需简单的一条语句即可实现，return(ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch=='('||ch==')'||ch=='*')。(2)Precede(charc1,charc2)判断运算符优先权功能，该函数判断运算符c1,c2的优先权，具体优先关系参照表1。(3)Operate(inta,charop,intb)操作数用对应的运算符进展运算功能。运算结果直接返回。(4)num(intn)求操作数的长度功能，需要用itoa函数把int型转换成字符串型，strlen函数可求字符长度。(5)EvalE*pr()主要操作函数运算功能。分析详细见"3.详细设计…3.2〞。3．详细设计3.1数据存储构造设计因为表达式是由操作符，运算符和界限符组成的。如果只用一个char类型栈，不能满足2位以上的整数，所以还需要定义一个int类型的栈用来存放操作数。/*定义字符类型栈*/typedefstruct{char*base;char*top;intStacksize;}Operator;/*定义整型栈*/typedefstruct{int*base;int*top;intStacksize;}Operand;3.2主要算法 流程图 破产流程图 免费下载数据库流程图下载数据库流程图下载研究框架流程图下载流程图下载word 〔或算法伪代码〕1.Precede(charc1,charc2)判断运算符优先权，返回优先权高的。算符间的优先关系如下：+-*/()*+><<<<>>->><<<>>*>>>><>>/>>>><>>(<<<<<=)>>>>>>*<<<<<=表1算法伪代码如下：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优先关系*/}2.intEvalE*pr()主要操作函数。算法概要流程图：利用该算法对算术表达式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**(37-2)*Push(OPNR,’-’)6**(-372)*Push(OPND,’2’)7**(-372)*Operate(‘7’,’-’,’2’)8**(35)*Pop(OPTR)9**35*Operate(‘3’,’*’,5’)10*15*Return(GetTop2(OPND))表2算法伪代码如下：intEvalE*pr()//主要操作函数{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'='://脱括号并接收下一字符*=Pop(&OPTR);c=*ptr++;break;case'>'://退栈并将运算结果入栈theta=Pop(&OPTR);b=Pop2(&OPND);a=Pop2(&OPND);Push2(&OPND,Operate(a,theta,b));break;}}4．软件测试1.运行成功后界面。2.输入正确的表达式后。3.更改表达式，输入有2位数的整数调试。5．心得体会这次课程设计让我更加了解大一学到的C和这个学期学到的数据构造。课设 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 目要求不仅要求对课本知识有较深刻的了解，同时要求程序设计者有较强的思维和动手能力和更加了解编程思想和编程技巧。这次课程设计让我有一个深刻的体会，那就是细节决定成败，编程最需要的是严谨，如何的严谨都不过分，往往检查了半天发现错误发生在*个括号，分号，引号，或者数据类型上。就像我在写EvalE*pr()函数时，忘了指针的地址符值不用加*号，这一点小小的错误也耽误了我几十分钟，所以说细节很重要。程序设计时，也不要怕遇到错误，在实际操作过程中犯的一些错误还会有意外的收获，感觉课程设计很有意思。在具体操作中这学期所学的数据构造的理论知识得到稳固，到达课程设计的根本目的，也发现自己的缺乏之出，在以后的上机中应更加注意，同时体会到C语言具有的语句简洁，使用灵活，执行效率高等特点。发现上机的重要作用，特别算术表达式有了深刻的理解。这个程序是我们3个人完成的，同时我认为我们的工作是一个团队的工作，团队需要个人，个人也离不开团队，必须发扬团结协作的精神。*个人的离群都可能导致导致整项工作的失败。实习中只有一个人知道原理是远远不够的，必须让每个人都知道，否则一个人的错误，就有可能导致整个工作失败。团结协作是我们成功的一项非常重要的保证。而这次课程设计也正好锻炼我们这一点，这也是非常珍贵的最后，感谢教师在这次课程设计的悉心指导，祝教师身体安康，工作顺利。参考文献：1."数据构造(C语言版)"严蔚敏清华大学2."C语言程序设计"丁峻岭中国铁道3."C程序设计"谭浩强清华大学附录程序源代码：*include*include*include*defineNULL0*defineOK1*defineERROR-1*defineSTACK_INIT_SIZE100*defineSTACKINCREMENT20/*定义字符类型栈*/typedefstruct{intstacksize;char*base;char*top;}Stack;/*定义整型栈*/typedefstruct{intstacksize;int*base;int*top;}Stack2;/*----------------全局变量----------------*/StackOPTR;//定义运算符栈Stack2OPND;//定义操作数栈chare*pr[255];//存放表达式串char*ptr=e*pr;/*--------------构造运算符栈--------------*/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->top=s->base;s->stacksize=STACK_INIT_SIZE;returnOK;}/*----------判断字符是否是运算符----------*/intIn(charch){return(ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch=='('||ch==')'||ch=='*');}/*----------运算符栈顶插入新元素----------*/intPush(Stack*s,charch){*s->top=ch;s->top++;return0;}/*----------操作数栈顶插入新元素----------*/intPush2(Stack2*s,intch){*s->top=ch;s->top++;return0;}/*----------删除运算符栈顶元素------------*/charPop(Stack*s){charp;s->top--;p=*s->top;returnp;}/*----------删除操作数栈顶元素------------*/intPop2(Stack2*s){intp;s->top--;p=*s->top;returnp;}/*-----------返回运算符栈顶元素-----------*/charGetTop(Stacks){charp=*(s.top-1);returnp;}/*-----------返回操作数栈顶元素-----------*/intGetTop2(Stack2s){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]);//返回运算符}/*----------------操作函数----------------*/intOperate(inta,charop,intb){switch(op){case'+':return(a+b);case'-':return(a-b);case'*':return(a*b);case'/':return(a/b);}return0;}/*-------------返回操作数长度-------------*/intnum(intn){charp[10];itoa(n,p,10);//把整型转换成字符串型n=strlen(p);returnn;}/*--------------主要操作函数--------------*/intEvalE*pr(){charc,theta,*;intn,m;inta,b;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'=':*=Pop(&OPTR);c=*ptr++;break;case'>':theta=Pop(&OPTR);b=Pop2(&OPND);a=Pop2(&OPND);Push2(&OPND,Operate(a,theta,b));break;}}returnGetTop2(OPND);}/*-----------------主函数-----------------*/intmain(){printf("请输入正确的表达式以'*'结尾:");do{gets(e*pr);}while(!*e*pr);InitStack(&OPTR);//初始化运算符栈Push(&OPTR,'*');//将*压入运算符栈InitStack2(&OPND);//初始化操作数栈printf("表达式结果为:%d\n",EvalE*pr());return0;}