西工大数据结构实验报告 算术表达式求值报告

1、数据结构实验报告一实验题目表达式求值设计一个程序，演示用算符优先法对算术表达式求值的过程。测试数据：3*（7-2）2*（6+2*（3+6*（6+6）+（6+6）*3+28/（9-9）(一) 需求分析1.本程序需要编写这样一个程序：（1）开始（2）首先要建立两个栈：运算数栈和运算符栈；（3）向运算符站中存入“n”（也可以是#）这个优先级最低的元素；（4）输入运算表达式；（5）分析数据，如果输入的是运算数，则储存，如果输入的是运算符，则与运算符栈的栈顶元素比较：（1）如果栈顶元素的优先级低于当前运算符，则将它读入运算符栈；（2）在栈顶元素的优先级等于当前运算符时，则删除栈顶元素并返回其值，（这种情

2、况只有输入结束或两个括号相遇时才会出现）分析下一个数据运算符；（3）当栈顶元素的优先级小于当前运算符时，删除栈顶元素并返回其值，然后用栈顶元素与其前后的元素进行运算，并将运算后的结果储存在运算数栈中；（6）输出运算结果；（7）结束(二) 概要设计这个程序的核心是栈的应用。1. 基本操作：typedef structchar *base; char *top;int stacksize; SqStack_Symbol;操作结果：对运算符号栈进行定义；typedef structfloat *base;float *top; /运算数栈int stacksize;SqStack_Number;操作

3、结果：对运算数栈进行定义；void InitStack_Symbol(SqStack_Symbol *S)操作结果：创建运算符栈；void InitStack_Number(SqStack_Number *S)操作结果：创建运算数栈；int GetTop_Symbol(SqStack_Symbol *S) 操作结果：返回栈顶运算符元素；float GetTop_Number(SqStack_Number *S)操作结果：返回栈顶运算数元素；char Push_Symbol(SqStack_Symbol *S,char e)操作结果：插入栈顶运算符元素；float Push_Number(SqS

4、tack_Number *S,float e)操作结果：插入栈顶运算数元素；char Pop_Symbol(SqStack_Symbol *S)操作结果：删除栈顶运算数元素，并返回其值；float Pop_Number(SqStack_Number *S)操作结果：删除栈顶运算数元素，并返回其值；char T8="+-*/()n"操作结果：定义运算符号；char Prior77 = / 运算符优先级表 / '+' '-' '*' '/' '(' ')' 'n' /

5、*'+'*/'>','>','<','<','<','>','>', /*'-'*/'>','>','<','<','<','>','>', /*'*'*/'>','>','>'

6、,'>','<','>','>', /*'/'*/'>','>','>','>','<','>','>', /*'('*/'<','<','<','<','<','=',' ', /*

7、')'*/'>','>','>','>',' ','>','>', /*'n'*/'<','<','<','<','<',' ','=', ;操作结果：运算符优先级比较列表char Precede(char a,char b)操作结果：判断运算符优先级；float Operat

8、e(float a,char optr,float b)操作结果：计算两个操作数；2.本程序包含五个模块：主程序，操作数栈及相关函数，操作符栈及相关函数，运算符列表及优先级表，运算符优先级判断函数和计算函数。（三）详细设计1.结构体定义typedef structchar *base; /运算符栈char *top;int stacksize;SqStack_Symbol;typedef structfloat *base;float *top; /运算数栈int stacksize;SqStack_Number;2. 每个模块的分析：（1）主程序模块：int main()SqStack_Sy

9、mbol OPTR;SqStack_Number OPND;float a,b,i,m,n;char optr,c,x;InitStack_Symbol(&OPTR); /创操作符栈Push_Symbol(&OPTR,'n'); /以“n”开始InitStack_Number(&OPND); /创建操作数栈printf("输入表达式并以'回车'结尾:n");c=getchar(); if(c=35|(c>=40&&c<=43)|c=45|(c>=47&&c<=57

10、) /输入数据限定为“n”,“+”,“-”,“*”,“/”“()”和“0-9”while(c!='n'|GetTop_Symbol(&OPTR)!='n') /当输入不是n运算符时 if(c>=48&&c<=57)while(c>=48&&c<=57) i=i*10+(float)c-48;c=getchar(); Push_Number(&OPND,i);elseswitch(Precede(GetTop_Symbol(&OPTR),c) ) /比较优先级case'<

11、':Push_Symbol(&OPTR,c); /栈顶元素的优先级低，则当前运算符进栈，读入下一字符c=getchar();break;case'=':x=Pop_Symbol(&OPTR); /栈顶元素与当前运算符优先级相等，删除，并读入下一字符c=getchar();break;case'>':optr=Pop_Symbol(&OPTR);b=Pop_Number(&OPND); /栈顶元素优先级高，运算，结果进入运算数栈 a=Pop_Number(&OPND);Push_Number(&OPND

12、,Operate(a,optr,b); break; m=GetTop_Number(&OPND);n=GetTop_Number(&OPND);if(n=int(m)printf("运算结果：%dn",int(m); /若是整数，则以整数输出else printf("%fn",n);else printf("输入错误!n");return 0;（2）运算符栈及相关函数typedef structchar *base; /定义运算符栈char *top;int stacksize;SqStack_Symbol;void

13、 InitStack_Symbol(SqStack_Symbol *S) /创建运算符栈(*S).base=(char *)malloc(STACK_INIT_SIZE*sizeof(char);if(!(*S).base) exit(OVERFLOW);(*S).top=(*S).base;(*S).stacksize=STACK_INIT_SIZE;int GetTop_Symbol(SqStack_Symbol *S) /返回栈顶运算符元素char e;if(*S).top=(*S).base) return ERROR;e= *(*S).top-1);return e;char Pus

14、h_Symbol(SqStack_Symbol *S,char e) /插入栈顶元素if(*S).top-(*S).base>=(*S).stacksize)(*S).base= (char*) realloc (*S).base , (*S).stacksize + STACKINCREMENT)*sizeof(char); /空间不足则增加空间分配if(!(*S).base) exit(OVERFLOW);(*S).top=(*S).base+(*S).stacksize;(*S).stacksize+=STACKINCREMENT;*(*S).top)+=e;return OK;c

15、har Pop_Symbol(SqStack_Symbol *S) /删除栈顶元素char e;if(*S).top=(*S).base) return ERROR;e=*(-(*S).top);return e;（3）运算数栈及相关函数typedef structfloat *base;float *top; /运算数栈int stacksize;SqStack_Number;void InitStack_Number(SqStack_Number *S) /创建运算数栈(*S).base=(float *)malloc(STACK_INIT_SIZE*sizeof(float);if(!(

16、*S).base) exit(OVERFLOW);(*S).top=(*S).base;(*S).stacksize=STACK_INIT_SIZE;float GetTop_Number(SqStack_Number *S) /返回栈顶运算数元素 float e;if(*S).top=(*S).base) return ERROR;e=*(*S).top-1);return e;float Push_Number(SqStack_Number *S,float e) /插入栈顶元素if( (*S).top-(*S).base >= (*S).stacksize) (*S).base=

17、(float*) realloc (*S).base , (*S).stacksize + STACKINCREMENT)*sizeof(float); /空间不足则增加空间分配if(!(*S).base) exit(OVERFLOW);(*S).top=(*S).base+(*S).stacksize;(*S).stacksize+=STACKINCREMENT;*(*S).top)+=e;return OK;float Pop_Number(SqStack_Number *S) /删除栈顶元素，并返回其值float e;if(*S).top=(*S).base) return ERROR;

18、e=*(-(*S).top); return e;（4）运算符表及优先级表char T8="+-*/()n"char Prior77 = / 运算符优先级表 / '+' '-' '*' '/' '(' ')' 'n' /*'+'*/'>','>','<','<','<','>','>', /*&#

19、39;-'*/'>','>','<','<','<','>','>', /*'*'*/'>','>','>','>','<','>','>', /*'/'*/'>','>','>',&#

20、39;>','<','>','>', /*'('*/'<','<','<','<','<','=',' ', /*')'*/'>','>','>','>',' ','>','>', /*'n

21、'*/'<','<','<','<','<',' ','=',;（5）判断优先级并计算har Precede(char a,char b)int i=0,j=0; /判断运算符优先级while(Ti!=a)i+; while(Tj!=b)j+;return(Priorij); /返回在运算符优先级表中的比较结果float Operate(float a,char optr,float b) /运算函数float m;switch(optr)cas

22、e'+':m=a+b;break;case'-':m=a-b;break;case'*':m=a*b;break;case'/':if(b!=0) m=a/b;else printf("输入错误!");break;return m;（四）程序使用说明及测试结果1程序使用说明（1）本程序的运行环境为VC6.0。（2）进入演示程序后即显示提示信息：输入表达式并以回车结尾：输入后显示：运算结果：2测试结果输入表达式：3*（7-2）输出结果：15输入表达式; 2*（6+2*（3+6*（6+6）+（6+6）*3+2输出结

23、果：350（五）、实验总结(实验心得)1.你在编程过程中花时多少？答：从周五实验课到周日晚完成实验报告，一共用了约八个小时。2.多少时间在纸上设计？答：两个小时3.多少时间上机输入和调试？答：编程与调试用的时间最长，大概六个小时。 4.多少时间在思考问题？答：从编程到调试的八个小时里，面对对我来说困难的程序，和不断涌现的各种错误，我一直在思考怎样解绝这个问题。5.遇到了哪些难题？你是怎么克服这些困难的？答：在做这项作业时。我可以说自己遇到了无数难题，以为我的C语言成绩并不好，栈的熟悉度恐怕只有10%。因此完成这项作业的过程可谓艰辛。首先遇到的困难就是设计程序。去年C语言学得很不扎实，

24、我对链表的结构都不甚了解，更别说运用与之相关的算法了。在周五下午数据结构的实验课上，我花了半个小时重新回顾C语言教科书栈上的基础知识，好在数据结构书上有创建栈的程序。由于知识的匮乏，我只能先将书上的栈的定、创建、进栈、出栈函数敲到电脑上， 然后在纸上设计相应的流程。最后凭借自己脑海里仅存的知识，并利用同学的帮助，磕磕绊绊地编写了主函数。接下来的困难，也就是最大，最麻烦，解决起来最耗费脑力，最枯燥乏味的问题调试程序。最初的程序编译之后，问题触目惊心，我根据系统的提示，首先补上了缺失的间隔符，又定义了遗漏的变量，再次编译，错误有所减少，但依然多，我又重新修改。接下来的错误越来越“高级”，

25、数据类型，返回类型，函数类型等有关。我便循环往复，不厌其烦地修改，每当减少一个错误，我都会有几分高兴，而有的时候，修改后会产生更多的错误。就这样一遍又一遍，终于系统显示没有错误和警告了。我运行了程序。当我按照自己的设想将输入数据时，敲下回车键后结果却令我傻了眼。屏幕上没有任何显示。，原来许多错误是编译器没有检测出来。知道第二天，我参考了网上的一些算法又请教了同学，才知道自己犯了哪些低级的错误。比如说指针的地址和指针所指向的对象的值没有区分清楚；函数的返回值应为链表的首结点，而不是函数中指向该链表的指针。后来又经过了几个小时的修改和编译调试，我最终才完成了完整地程序。但后来更可怕的事发生了，我不

26、知怎么竟然丢失了自己编写的程序！只能凭借记忆重新编写。知识掌握的不牢固，我又耗费了大量时间，还犯了许多低级错误，最终凭借努力终于完成了程序。  6你的收获有哪些？答：首先，我对栈不分的知识有了更多了解破除了错误的认识。其次，通过这次作业，我掌握了几种与栈有关的算法。最后，我还温习了有关C语言的许多知识。 附：完整程序 #include <stdio.h>#include <stdlib.h>#define OK 1 #define ERROR 0#define OVERFLOW 0#define STACK_INIT_SIZE 100#define STACK

27、INCREMENT 10 typedef structchar *base; /运算符栈char *top;int stacksize;SqStack_Symbol;typedef structfloat *base;float *top; /运算数栈int stacksize;SqStack_Number;void InitStack_Symbol(SqStack_Symbol *S) /创建运算符栈(*S).base=(char *)malloc(STACK_INIT_SIZE*sizeof(char);if(!(*S).base) exit(OVERFLOW);(*S).top=(*S)

28、.base;(*S).stacksize=STACK_INIT_SIZE;void InitStack_Number(SqStack_Number *S) /创建运算数栈(*S).base=(float *)malloc(STACK_INIT_SIZE*sizeof(float);if(!(*S).base) exit(OVERFLOW);(*S).top=(*S).base;(*S).stacksize=STACK_INIT_SIZE;int GetTop_Symbol(SqStack_Symbol *S) /返回栈顶运算符元素char e;if(*S).top=(*S).base) ret

29、urn ERROR;e= *(*S).top-1);return e; float GetTop_Number(SqStack_Number *S) /返回栈顶运算数元素 float e;if(*S).top=(*S).base) return ERROR;e=*(*S).top-1);return e;char Push_Symbol(SqStack_Symbol *S,char e) /插入栈顶元素if(*S).top-(*S).base>=(*S).stacksize)(*S).base= (char*) realloc (*S).base , (*S).stacksize + S

30、TACKINCREMENT)*sizeof(char); /空间不足则增加空间分配if(!(*S).base) exit(OVERFLOW);(*S).top=(*S).base+(*S).stacksize;(*S).stacksize+=STACKINCREMENT;*(*S).top)+=e;return OK;float Push_Number(SqStack_Number *S,float e) /插入栈顶元素if( (*S).top-(*S).base >= (*S).stacksize) (*S).base= (float*) realloc (*S).base , (*S

31、).stacksize + STACKINCREMENT)*sizeof(float); /空间不足则增加空间分配if(!(*S).base) exit(OVERFLOW);(*S).top=(*S).base+(*S).stacksize;(*S).stacksize+=STACKINCREMENT;*(*S).top)+=e;return OK;char Pop_Symbol(SqStack_Symbol *S) /删除栈顶元素char e;if(*S).top=(*S).base) return ERROR;e=*(-(*S).top);return e;float Pop_Number

32、(SqStack_Number *S) /删除栈顶元素float e;if(*S).top=(*S).base) return ERROR;e=*(-(*S).top); return e;char T8="+-*/()n"char Prior77 = / 运算符优先级表 / '+' '-' '*' '/' '(' ')' 'n' /*'+'*/'>','>','<','&l

33、t;','<','>','>', /*'-'*/'>','>','<','<','<','>','>', /*'*'*/'>','>','>','>','<','>','>', /*&#

34、39;/'*/'>','>','>','>','<','>','>', /*'('*/'<','<','<','<','<','=',' ', /*')'*/'>','>','>','>

35、;',' ','>','>', /*'n'*/'<','<','<','<','<',' ','=' ; char Precede(char a,char b)int i=0,j=0; /判断运算符优先级while(Ti!=a)i+; while(Tj!=b)j+;return(Priorij); /返回在运算符优先级表中的比较结果float Operate(float a,char optr,float b) /运算函数float m;switch(optr)case'+':m=a+b;break;case'-':m=a-b;break;ca