中缀表达式求值实验报告

中缀表达式求值实验报告一、需求分析（要实现的功能描述）1．问题描述：在计算机中，算术表达式由常量、变量、运算符和括号组成。由于不同的运算符具有不同的优先级，又要考虑括号，因此，算术表达式的求值不可能严格地从左到右进行。因而在程序设计时，借助栈实现。2．实现功能：算法输入：一个算术表达式，由常量、变量、运算符和括号组成（以字符串形式输入）。为简化，规定操作数只能为正整数，操作符为“+、-、*、/”。算法运行：将输入的中缀表达式改为后缀表达式，并进行运算。算法输出：输出后缀表达式和表达式运算结果。3．测试数据：（1）、1+3*4-（5/5）；一位数运算（2）、45-5*（1+2）/5;多位数运算二、概要设计整个程序包含功能模块及模块间的调用关系(1)、structnode创建结构体，被主函数调用(2)、structnode*Initialization()创建栈链，被主函数调用(3)、structnode*assort(structnode*s)将中缀表达式转换为后缀表达式并存在s2中被主函数调用(4)、structnode*calcolate(structnode*s)求出表达式的值，被主函数调用(5)、voidmain()主函数，调用所有函数三、详细设计抽象数据类型中定义的各种操作算法实现（用N-S图描述）四、调试分析1．程序在调式过程中出现的问题及解决方法一开始选用直接运算方式运用两个栈来存放数字和操作符，后来写着确实不行然后直接转用转为后缀表达式再进行计算。在写将多位数（比如123*12）存放字符串中时，一开始我想着直接转换成数字存入数组中，但一直不成功，只能将第一个多位数转换成功；后来在和同学之间交流并且百度搜索后改为直接存入字符串中，再存入字符串过程中，我发现几个数字之间可能没法区分是前一个数字的还是后一个数字的，于是我在扫描字符串过程中在扫描到操作字符时将存入数字的那个字符串s2空出一位，用以区分前后两个数字，如12+45*，如果直接存入字符串中会是s2：1245*+；但加空格后为s2：12（空格）45*+；这样后面运算时就好区分两多位数字。………2．心得体会在写程序之前要选择适合自己的算法即自己熟悉的能编出的算法，这样后续的编程会简便多了。对于一个要实现的功能，会有很多不同的算法，当你一个算法用不了时，可以换一个算法编程，目的是死的，人是活的，算法是活的，程序也是活的！开始输入中缀表达式将中缀表达式转换成后缀表达式并存入s2中计算结果输出结果输出后缀表达式结束五、用户手册该软件的操作方法简介输入一个算术表达式，由常量、变量、运算符和括号组成（以字符串形式输入）。为简化，规定操作数只能为正整数，操作符为“+、-、*、/”，按回车结束输入。程序运行输出输出后缀表达式和表达式运算结果。六、测试结果根据已提供的测试数据得到什么样的结果（可以截屏）（1）、1+3*4-（5/5）；（2）、45-5*（1+2）/5;七、程序清单#includestdio.h#includemalloc.h#includestring.h#includestdlib.h#defineMAX60#defineRIGHT1#defineWRONG0#defineDEMAX15#defineNULL0chars1[MAX];chars2[MAX];intj=0;structnode//定义结构体。{chardata;intnum;structnode*next;};structnode*Initialization()//初始化栈链,链栈不带头结点{structnode*top;top=(structnode*)malloc(sizeof(structnode));top-data=';';top-num=0;top-next=NULL;returntop;}structnode*assort(structnode*s)//输入字符串{structnode*p,*top;inti;top=s;intm;chara;m=strlen(s1);for(i=0;i=m;i++){a=s1[i];if('0'=s1[i]&&s1[i]='9'){s2[j]=s1[i];j++;}else{switch(a){case'(':{p=(structnode*)malloc(sizeof(structnode));p-data=a;p-next=top;top=p;break;}case'*':case'/':s2[j]='';j++;if((top-data=='*')||(top-data=='/')){s2[j]=top-data;j++;//比其高，现将栈顶运算符出栈，再进栈。top-data=a;break;}else{p=(structnode*)malloc(sizeof(structnode));//否，直接进栈p-data=a;p-next=top;top=p;break;}case'+':case'-':{s2[j]='';j++;if(top-data=='+'||top-data=='-'||top-data=='*'||top-data=='/'){s2[j]=top-data;j++;top-data=a;break;}else{p=(structnode*)malloc(sizeof(structnode));p-data=a;p-next=top;top=p;break;}}case')':{s2[j]='';j++;if(top-data==';'){printf(inputerror);break;}while(top-data!='('){s2[j]=top-data;j++;p=top;top=top-next;free(p);}p=top;top=top-next;free(p);break;}}}}while(top-data!=';'){s2[j]=top-data;j++;p=top;top=top-next;free(p);}s2[j]=';';printf(后缀表达式为:);for(i=0;ij;i++)if(s2[i]!='')printf(%c,s2[i]);printf(\n);returntop;}structnode*calcolate(structnode*s)//计算表达式的值{structnode*top,*p;char*q;intx,y,a;inti,n;top=s;//指向栈顶的指针for(i=0;i=j;i++)//遍历字符串s2{if(s2[i]='0'&&s2[i]='9'){q=&s2[i];a=atoi(q);for(n=i;s2[n]='0'&&s2[n]='9';n++){}p=(structnode*)malloc(sizeof(structnode));p-num=a;p-next=top;top=p;i=n-1;}elseif(s2[i]==';')//遇；号结束标志，输出栈中的最后计算结果printf(计算结果为:%d\n,top-num);else{if(s2[i]==''){}else{y=top-num;p=top;top=top-next;free(p);x=top-num;p=top;top=top-next;free(p);switch(s2[i]){case'+':{a=x+y;p=(structnode*)malloc(sizeof(structnode));p-num=a;p-next=top;top=p;break;}case'-':{a=x-y;p=(structnode*)malloc(sizeof(structnode));p-num=a;p-next=top;top=p;break;}case'*':{a=x*y;p=(structnode*)malloc(sizeof(structnode));p-num=a;p-next=top;top=p;break;}case'/':{a=(float)x/y;p=(structnode*)malloc(sizeof(structnode));p-num=a;p-next=top;top=p;break;}}}}}return0;}voidmain(){structnode*top,*head;top=Initialization();printf(请输入表达式（运算符号可以为：+、-、*、/、(、)）：\n);gets(s1);head=assort(top);calcolate(head);}