算术表达式的求解-数据结构课程设计报告.doc_第1页
算术表达式的求解-数据结构课程设计报告.doc_第2页
算术表达式的求解-数据结构课程设计报告.doc_第3页
算术表达式的求解-数据结构课程设计报告.doc_第4页
算术表达式的求解-数据结构课程设计报告.doc_第5页
已阅读5页,还剩12页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

课程设计报告题目:算术表达式求值一、需求分析1、设计要求:给定一个算术表达式,通过程序求出最后的结果1、从键盘输入要求解的算术表达式;2、采用栈结构进行算术表达式的求解过程;3、能够判断算术表达式正确与否;4、对于错误表达式给出提示;5、对于正确的表达式给出最后的结果;2、设计构想:为了实现算符优先算法使用两个工作栈,一个称作OPTR,以寄存运算符;另一个称作OPND,用以寄存操作数或运算结果。在操作数和操作符入栈前,通过一个函数来判别,输入的是操作数还是操作符,操作数入OPND,操作符入OPTR。在输入表达式的最后输入#,设定#的优先级最低,代表表达式输入结束。在表达式输入过程中,遇操作数则直接入栈,遇到运算符则与栈顶运算符比较优先级,若当前运算符优先级高,则当前运算符入栈,扫描下一符号;否则栈顶运算符出栈,两操作数出栈,进行运算,所得结果入数栈,重新比较当前运算符与新栈顶运算符。如此重复直到栈顶运算符与当前符号均为#,运算结束。二、概要设计1、本程序包含的模块:(1)栈模块实现栈抽象数据类型(2)运算模块实现数据表达式的运算(3)主程序模块算术运算式的求解栈模块主函数模块main运算模块初始化栈定义栈结构出栈入栈取栈顶元素判断输入字符类型判断符号优先级基础运算函数运算函数三、详细设计(1)栈模块1、定义栈结构struct Sqstackelemtype *top;/栈顶元素elemtype *base; /栈底元素int stacksize;/栈的大小 ;2、栈的基本操作初始化栈status initstack(struct Sqstack &s)s.base=(elemtype *)malloc(stack_size*sizeof(elemtype);if(!s.base)return OVERFLOW;s.top=s.base;s.stacksize=stack_size;return OK;入栈status push(struct Sqstack &s,elemtype e)if(s.top-s.base=s.stacksize) s.base=(elemtype*)realloc(s.base,(s.stacksize+stack_increasement)*sizeof(elemtype);if(!(s.base)return OVERFLOW;s.top=s.base+s.stacksize;s.stacksize+=stack_increasement;* s.top+=e;return OK;出栈elemtype pop(struct Sqstack &s)elemtype e;if(s.top= =s.base)return ERROR;e=*-s.top;return e;取栈顶元素elemtype gettop(struct Sqstack &s)elemtype e;if(s.top=s.base)return ERROR;e=*(s.top-1);return e;(2)运算模块1、判断输入字符c是否为操作符:若是,则返回1;否则,返回0 int In(int c) char p10=+-*/()#; int i=0; while(pi!=0) if(pi=c) return 1;i+; return 0;2、判断运算符的优先级 char precede(char top,char c)/该函数为判断当前运算符与前一个运算符的优先级,前一个运算符高于或等于当前运算符的优先级则返回, 前一个运算符小于当前运算符的优先级则返; break; case +: case -: if(top=#|top=() result=; break; case *: case /: if(top=*|top=/|top=) result=; else result=; else result=; break; case (: result=; break; case : result=; break; default: printf(操作符输入错误!n); return result;3、运算函数 基础运算函数:实现相应的加、减、乘、除、乘方及带小括号的基本数学运算并返回结果,其中a,b为两个操作数,theta为操作符elemtype operate(elemtype a,char theta,elemtype b) elemtype result; switch(theta) case +: result=a+b; break; case -: result=a-b; break; case *: result=a*b; break; case /: if(b=0) printf(nn输入错误!分母不能为0!n); result=0; else result=a/b;break; case %: if(b=0|b=NULL) printf(nn输入错误!n);return 0;break; else result=a%b;break; case : result=(int)pow(double)a,(double)b); break; default: printf(操作符输入错误!n); return result; 运算函数elemtype evaluate(struct Sqstack opnd,struct Sqstack optr)/该函数为求表达式的值的整个操作过程,通过调用相应的函数实现遇到运算符则与栈顶运算符比较优先级,/若当前运算符优先级高(前面的运算还不应执行)则当前运算符入栈,扫描下一符号;否则栈顶运算符出栈,同时两操作数出栈,进行运算,所得结果入数栈,/重新比较当前运算符(注意当前运算符未变)与新栈顶运算符。如此重复直到栈顶运算符与当前符号均为#,运算结束。/若操作数为个位数,则直接将输入的字符减48后入栈,若为多位数,则通过flag来实现。若输入字符c为操作数且flag=1(即操作数为多位数),则将操作数栈的栈顶元素出栈后乘以10,然后加上,(c-48)然后将二者的和入操作数栈。 elemtype a,b,c,theta,e; initstack(optr); push(optr,#); initstack(opnd); c=getchar(); int flag=0;/当输入操作数时flag=1;当输入操作符时flag=0;/当前输入为操作数且flag=1时,将操作数栈的栈顶元素出栈,然后将其和当前输入转换成相应的int类型 while(c!=#|gettop(optr)!=#) if(!In(c) /c若为操作数则入opnd栈 if(flag=1) e=pop(opnd); / 取栈顶元素 push(opnd,(e*10+(c-48);/将输入数在转化为int型,并将上次输入数*10并与当前操作数相加,将结果如操作数栈 else push(opnd,c-48); flag=1; c=getchar(); else flag=0;/当前字符为操作符,则入操作符栈,并将flag置为0 switch(precede(gettop(optr),c)/ 判断当前操作数与操作符栈中的栈顶元素的优先级 case : theta=pop(optr); b=pop(opnd); a=pop(opnd); push(opnd,operate(a,theta,b); break;/ 若当前操作符的优先级低于操作符栈的栈顶元素,则将操作符栈栈顶元素出栈,并将操作数栈的栈顶两个元素出栈,计算两个元素间以操作符栈栈顶元素为运算符的数学运算 /switch/if /while return pop(opnd);(3)主程序模块1、main函数 void main(int argc,char *argv) struct Sqstack opnd; /操作数栈 struct Sqstack optr;/操作符栈initstack(opdn);initstack(optr); elemtype result; printf(*n); printf(算术运算式的求解); printf(n*n); printf(n请输入算术运算表达式(以#结尾):n); printf(n); result=evaluate(opnd,optr); printf(n*n); printf(nn运算的结果是 :n n%dn,result); printf(n*n); 四、调试分析1、测试结果 1 测试数据:3+7*2-1# 测试结果: 2 测试数据:(3+7)*2-1# 测试结果: 3 测试数据: 1/0# 测试结果: 2、程序时间复杂度为O(n);3、设计中出现的问题:在开始的设计中没有注意除数不能为0 ,后来加入if(b=0) printf(分母为0,the result is errorn); result=0; else result=a/b;break;来判断除数是否为04、算法改进:1输入的操作数和操作码由于是字符串类型的,在原设计中实现的操作都是对个位数实现的,实用性不大,故在后来的设计中,通过一个标志flag实现了标志操作数的连续输入的判别,继而实现了多位数的表达式运算2开始只实现了加、减、乘、除及带小括号的数学运算,考虑到实用性,在后来的设计中引入pow函数,实现了乘方的运算,调整结果如下:3最初设计的运行界面过于单调,不够友好,改进时加入一些*调整调整结果如下:五、课程设计总结 本学期是我第一次接触课程设计,发现了很多学习上的问题,也有

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论