1、表达式的值基本操作:键入表达式,开始计算,计算过程和结果记录在文档中难点:括号的处理、乘除的优先级高于加减1前言在计算机中,算术表达式由常量、变量、运算符和括号组成。由于不同的运算符具有不同的优先级,又要考虑括号,因此,算术表达式的求值不可能严格地从左到右进行。因而在程序设计时,借助栈实现。算法输入:一个算术表达式,由常量、变量、运算符和括号组成(以字符串形式输入)。为简化,规定操作数只能为正整数,操作符为+、-*、/、=,用#表示结束。算法输出:表达式运算结果。算法要点:设置运算符栈和运算数栈辅助分析算符优先关系。在读入表达式的字符序列的同时,完成运算符和运算数的识别处理,以及相应运算。2概
2、要设计 数据结构设计任何一个表达式都是由操作符,运算符和界限符组成的。我们分别用顺序栈来寄存表达式的操作数和运算符。栈是限定于紧仅在表尾进行插入或删除操作的线性表。顺序栈的存储结构是利用一组连续的存储单元依次存放自栈底到栈顶的数据元素,同时附设指针top指示栈顶元素在顺序栈中的位置,base为栈底指针,在顺序栈中,它始终指向栈底,即top=base可作为栈空的标记,每当插入新的栈顶元素时,指针top增1,删除栈顶元素时,指针top减1。 算法设计为了实现算符优先算法。可以使用两个工作栈。一个称为OPTR,用以寄存运算符,另一个称做OPND,用以寄存操作数或运算结果。1.首先置操作数栈为空栈,表
3、达式起始符”#”为运算符栈的栈底元素;2.依次读入表达式,若是操作符即进OPND栈,若是运算符则和OPTR栈的栈顶运算符比较优先权后作相应的操作,直至整个表达式求值完毕(即OPTR栈的栈顶元素和当前读入的字符均为”#”)。 ADT描述ADT Stack数据对象:D= |ElemSet,i=1,2,,n, n0R1=|,i=2,,n约定端为栈顶,端为栈底。 InitStack(&S) 操作结果:构造一个空栈S。 GetTop(S) 初始条件:栈S已存在。用P返回S的栈顶元素。 Push(&S,ch)插入元素ch为新的栈顶元素。 Pop(&删除S的栈顶元素。In(ch)操作结果:判断字符是否是运算
4、符,运算符即返回1。 Precede(c1, c2) 初始条件:c1,c2为运算符。判断运算符优先权,返回优先权高的。Operate(a,op,b)a,b为整数,op为运算符。a与b进行运算,op为运算符,返回其值。num(n)返回操作数的长度。EvalExpr()输入表达式合法。返回表达式的最终结果。ADT Stack 功能模块分析1.栈的基本功能。InitStack(Stack *s) 和InitStack2(Stack2 *s)分别构造运算符栈与构造操作数栈,Push(Stack *s,char ch) 运算符栈插入ch为新的栈顶元素,Push2(Stack2 *s,int ch) 操作
5、数栈插入ch为新的栈顶元素,Pop(Stack *s) 删除运算符栈s的栈顶元素,用p返回其值,Pop2(Stack2 *s)删除操作数栈s的栈顶元素,用p返回其值,GetTop(Stack s)用p返回运算符栈s的栈顶元素,GetTop2(Stack2 s) 用p返回操作数栈s的栈顶元素。2.其它功能分析。 (1)In(char ch) 判断字符是否是运算符功能,运算符即返回1,该功能只需简单的一条语句即可实现,return(ch=+|ch=-*/()#)。 (2) Precede(char c1,char c2) 判断运算符优先权功能,该函数判断运算符c1,c2的优先权,具体优先关系参照表
6、1。 (3) Operate(int a,char op,int b)操作数用对应的运算符进行运算功能。运算结果直接返回。(4) num(int n) 求操作数的长度功能,需要用itoa函数把int型转换成字符串型,strlen函数可求字符长度。(5) EvalExpr()主要操作函数运算功能。分析详细见“3.详细设计”。3详细设计 数据存储结构设计 因为表达式是由操作符,运算符和界限符组成的。如果只用一个char类型栈,不能满足2位以上的整数,所以还需要定义一个int类型的栈用来寄存操作数。/* 定义字符类型栈 */struct stacklifei1 if(cri-19|i=0|cri+1
7、) error=1;break; else k=1;h=10; else flag=1;j=j*h; sum=sum*k+(cri-48)/j; i+; 对函数表达式每个字符的操作switch(cri) case :if(cri-1=|i=0)fuhao=1;i+;行成功后界面。2.输入正确的表达式后。3.更改表达式,带括号输出 5心得体会这次课程设计让我再一次加了解大一学到的C和这个学期学到的数据结构。课设题目要求不仅要求对课本知识有较深刻的了解,同时要求程序设计者有较强的思维和动手能力和更加了解编程思想和编程技巧。这次课程设计让我有一个深刻的体会,那就是细节决定成败,编程最需要的是严谨,如
8、何的严谨都不过分,往往检查了半天发现错误发生在某个括号,分号,引号,或者数据类型上。就一点小小的错误也耽误了我几十分钟,所以说细节很重要。 程序设计时,也不要怕遇到错误,在实际操作过程中犯的一些错误还会有意外的收获,感觉课程设计很有意思。在具体操作中这学期所学的数据结构的理论知识得到巩固,达到课程设计的基本目的,也发现自己的不足之出,在以后的上机中应更加注意,同时体会到C语言具有的语句简洁,使用灵活,执行效率高等特点。发现上机的重要作用,特别算术表达式有了深刻的理解。 最后,感谢老师在这门数据结构课程的悉心指导,祝老师和助教身体健康,万事如意!【参考文献】1.数据结构(C语言版) 严蔚敏 清华
9、大学出版社2.C程序设计 谭浩强 清华大学出版社【附 录】程序源代码:#include lfn,*); fprintf(file,%.6lfn return ; void main() char cr60; char c=a; file=fopen(outfile,w+); /使用提示 printf(*n*李斐计算器*n四则简易计算器nn输入表达式例如 2+4= nn最后按 # 键 则会退出保存nn谢谢使用nn-n*n /循环输入表达式,按键退出 while(c!= error=0; printf(输入表达式:n gets(cr);表达式:%sn,cr); qiuzhi(cr);任意键继续,按 # 键退出: c=getch(); fclose(file);