2022年算术表达式求值演示程序 .pdf

《2022年算术表达式求值演示程序 .pdf》由会员分享，可在线阅读，更多相关《2022年算术表达式求值演示程序 .pdf（20页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数 理 学 院课程设计报告书课程名称数据结构课程设计设计题目算术表达式求值演示专业班级学号姓名指导教师2014 年12 月名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 20 页 - - - - - - - - - 1 设计时间2014 年 12 月 232014年 12 月 29 日2 设计目的设计一个程序，演示算符优先法对算术表达式求值的过程。利用算符优先关系，实现对算术四则混合运算表达式的求值。3 设计任务(1) 设置运算符栈和运算数栈辅助分析算符优先关系；(2)

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 . 栈的抽象数据类型定义：ADT Stack 数据对象： D=ai|ai

3、Char,i=1,2.,n,n0数据关系： R1=ai-1,ai|ai-1,aiD,i=2,3.n 约定 an端为栈顶， ai 端为栈底名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 20 页 - - - - - - - - - 4.2.2 基本操作： InitStack(&S) 操作结果：构造一个空栈S。 GetTop(S) 初始条件：栈 S已存在。操作结果：用 P返回 S的栈顶元素。 Push(&S，ch) 初始条件：栈 S已存在。操作结果：插入元素ch 为新的栈顶元

4、素。 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() 初始条件：输入表达式合法。操作结果：返回表达式的最终结果。ADT Stack 主程序的流程：名师资料总结 - - -精品资料欢迎下载 - - - -

5、 - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 20 页 - - - - - - - - - EvaluateExpression()函 数实 现了 对 表 达式 求值 的 功 能， main() 函数 直接 调 用EvaluateExpression()对输入的表达式求值输出。算法流程图4.2.3 函数的调用关系图main EvaluateExpression Push precede In Pop ReturnOpOrd Operat输出名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - -

6、- - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 20 页 - - - - - - - - - 4.3 详细设计4.3.1. Precede(char c1,char c2)判断运算符优先权，返回优先权高的。算符间的优先关系如下：+ - * / ( ) # + - * / ( # , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , !, , , , , , , , !, =; / 用一维数组存储 49 种情况switch(c1) /* i 为下面 array的横标 */ case +

7、 : i=0;break; case - : i=1;break; case * : i=2;break; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 20 页 - - - - - - - - - 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

8、- : j=1;break; case * : j=2;break; case / : j=3;break; case ( : j=4;break; case ) : j=5;break; case # : j=6;break; return (array7*i+j); /* 返回运算符 array7*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,

9、()4 #*( 4 6-2)# Push(OPND, 6)5 #*( 4 6 -2)# Push(OPNR, - )6 #*(- 4 6 2)# Push(OPND, 2)名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 20 页 - - - - - - - - - 7 #*(- 4 6 2 )# Operate( 6, -, 2)8 #*( 4 4 )# Pop(OPTR) 9 #* 4 4 # Operate( 4, *,4 )10 # 16 # Return(GetT

10、op2(OPND) 算法伪代码如下：int EvalExpr()/ 主要操作函数 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+; else switch(Precede(GetTop(OPTR),c) case :/退栈并将运算结果入栈theta=Pop(&OPTR); b=Pop2(&OPND); a=Pop2(&OPND); Pu

11、sh2(&OPND,Operate(a,theta,b); break; 4.3.2主函数和其他函数的伪码int main( ) printf( 请输入正确的表达式以 #结尾:); do gets(expr); while(!*expr); InitStack(&OPTR); /* 初始化运算符栈*/ Push(&OPTR,#); /* 将#压入运算符栈*/ InitStack2(&OPND); /* 初始化操作数栈*/ 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 2

12、0 页 - - - - - - - - - printf( 表达式结果为 :%dn, EvalExpr(); return 0; 4.3.3 函数的调用关系图调用关系图4.4 测试与分析4.4.1测试main EvaluateExpression Push precedIn Pop ReturnOpOrd Operat输出名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 20 页 - - - - - - - - - 4.4.2 实验分析：表达式求值程序是一个多次调用函数的过

13、程，且调用的过程较为复杂，调试花费时间较多。在while 循环时指针移动容易出错，因此多次出现内存错误，对于涉及的循环的操作开始和结束条件设置很关键。本次实验熟悉了栈数据结构的表示与实现方法。算法时间和空间分析：算法的运行时间主要花在while 循环上，它从头到尾扫描后缀表达式中的每一个数据（每个操作数或运算符均为一个数据），若后缀表达式由n 个数据组成，则此算法的时间复杂度为O(n)。此算法在运行时所占用的临时空间主要取决于栈S 的大小，显然，它的最大深度不会超过表达式中操作数的个数，因为操作数的个数与运算符（假定把 #也看作为一个特殊运算符，即结束运算符）的个数相等，所以此算法的空间复杂度

14、也同样为O(n)。4.5 附录源程序：#include #include #include #define NULL 0 #define OK 1 #define ERROR -1 #define STACK_INIT_SIZE 100 #define STACKINCREMENT 20 /* 定义字符类型栈*/ typedef struct int stacksize; char *base; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 20 页 - - - -

15、- - - - - char *top; Stack; /* 定义整型栈*/ typedef struct int stacksize; int *base; int *top; Stack2; /* - 全局变量 - */ Stack OPTR;/* 定义运算符栈 */ Stack2 OPND; /* 定义操作数栈*/ char expr255 = ; /* 存放表达式串*/ char *ptr = expr; int InitStack(Stack *s) /构造运算符栈 s-base=(char *)malloc(STACK_INIT_SIZE*sizeof(char); if(!s-b

16、ase) return ERROR; s-top=s-base; s-stacksize=STACK_INIT_SIZE; return OK; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 20 页 - - - - - - - - - int InitStack2(Stack2 *s) /构造操作数栈 s-base=(int *)malloc(STACK_INIT_SIZE*sizeof(int); if(!s-base) return ERROR; s-stack

17、size=STACK_INIT_SIZE; s-top=s-base; return OK; int In(char ch) /判断字符是否是运算符，运算符即返回1 return(ch=+|ch=-|ch=*|ch=/|ch=(|ch=)|ch=#); int Push(Stack *s,char ch) / 运算符栈插入 ch 为新的栈顶元素 *s-top=ch; s-top+; return 0; int Push2(Stack2 *s,int ch)/操作数栈插入 ch 为新的栈顶元素 *s-top=ch; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - -

18、 - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 20 页 - - - - - - - - - s-top+; return 0; char Pop(Stack *s) / 删除运算符栈 s 的栈顶元素，用 p 返回其值 char p; s-top-; p=*s-top; return p; int Pop2(Stack2 *s)/删除操作数栈 s的栈顶元素，用p 返回其值 int p; s-top-; p=*s-top; return p; char GetTop(Stack s)/ 用 p 返回运算符栈 s 的栈顶元素 char p=*(s.to

19、p-1); return p; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 20 页 - - - - - - - - - int GetTop2(Stack2 s) / 用 p 返回操作数栈 s的栈顶元素 int p=*(s.top-1); return p; /* 判断运算符优先权，返回优先权高的*/ char Precede(char c1,char c2) int i=0,j=0; static char array49= , , , , , , , , ,

20、, , , , , , , , , , , , , , , , , , , , , , , !, , , , , , , , !, =; switch(c1) /* i 为下面 array的横标 */ case + : i=0;break; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 20 页 - - - - - - - - - case - : i=1;break; case * : i=2;break; case / : i=3;break; case ( :

21、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 (array7*i+j); /* 返回运算符*/ /*操作函数*/ 名师资料总结 - - -精品资料欢迎下载 - - - - - - - -

22、 - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页，共 20 页 - - - - - - - - - int Operate(int a,char op,int b) switch(op) case + : return (a+b); case - : return (a-b); case * : return (a*b); case / : return (a/b); return 0; int num(int n)/ 返回操作数的长度 char p10; itoa(n,p,10);/把整型转换成字符串型n=strlen(p); return n

23、; int EvalExpr()/ 主要操作函数 char c,theta,x; int n,m; int a,b; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16 页，共 20 页 - - - - - - - - - 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=pt

24、r+n; c=*ptr+; else switch(Precede(GetTop(OPTR),c) case : theta=Pop(&OPTR); b=Pop2(&OPND); a=Pop2(&OPND); Push2(&OPND,Operate(a,theta,b); break; return GetTop2(OPND); int main( ) printf( 请输入正确的表达式以 #结尾:); do gets(expr); while(!*expr); InitStack(&OPTR); /* 初始化运算符栈*/ Push(&OPTR,#); /* 将#压入运算符栈*/ InitSt

25、ack2(&OPND); /* 初始化操作数栈*/ printf( 表达式结果为 :%dn, EvalExpr(); return 0; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 18 页，共 20 页 - - - - - - - - - 5 总结与展望这次课程设计让我更加了解大一学到的C和这个学期学到的数据结构。课设题目要求不仅要求对课本知识有较深刻的了解，同时要求程序设计者有较强的思维和动手能力和更加了解编程思想和编程技巧。程序设计时，也不要怕遇到错误， 在实际操作过程中犯

26、的一些错误还会有意外的收获，感觉课程设计很有意思。在具体操作中这学期所学的数据结构的理论知识得到巩固，达到课程设计的基本目的，也发现自己的不足之出，在以后的上机中应更加注意，同时体会到C 语言具有的语句简洁，使用灵活，执行效率高等特点。发现上机的重要作用，特别算术表达式有了深刻的理解。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 19 页，共 20 页 - - - - - - - - - 参考文献1 数据结构 (C 语言版 ) 严蔚敏 清华大学出版社2 C语言程序设计丁峻岭中国铁道出版社3 C程序设计谭浩强清华大学出版社成绩评定成绩教师签字名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 20 页，共 20 页 - - - - - - - - -