中缀表达式转后缀表达式报告

目录1.课题分析...................................................................11．1设计目的..........................................................11．2主要内容..........................................................11．2．1中缀表达式转换为后缀表达式............11．2．2后缀表达式求值....................................11．3设计要求..........................................................22.总体设计.....................................................................22．1数据类型的定义...............................................22．2主程序的流程...................................................33．详细设计（源代码）..............................................44．调试分析..................................................................44．1问题1...............................................................84．2问题2...............................................................84．3问题3...............................................................95．测试结果..................................................................96．心得体会................................................................107．参考文献................................................................10实用数据结构基础课程设计报告11.课题分析1．1设计目的（1）掌握栈“后进先出”的特点。（2）掌握栈的典型应用——中缀表达式转后缀表达式，并利用后缀表达式求值。（3）掌握串或者数组的相关操作。1．2主要内容1．2．1中缀表达式转换为后缀表达式（1）定义一个运算符栈，并输入一个中缀表达式（运算对象存在多位整数，运算符为+、-、*、/、%及括号），然后从中缀表达式中自左至右依次读入各个字符。（2）如果是第一次读入运算对象，也是直接输出到后缀表达式；如果不是第一次读入运算对象，并且前一个读入的字符是运算对象，也是直接输出到后缀表达式；如果不是第一次读入运算对象，并且前一个读入的字符是运算符，则先输出逗号作为分隔符，然后再将该运算对象输出到后缀表达式。（3）如果读入的是运算符，并且运算符栈为空，则将该运算符直接进栈；如果栈不为空，则比较该运算符和栈顶运算符的优先级。若该运算符高于栈顶运算符的优先级，则将该运算符直接进栈；若该运算符低于或等于栈顶运算符的优先级，则将栈中高于或等于该运算符优先级的元素依次出栈，然后再将该运算符进栈。每出栈一个运算符时，先输出一个逗号到后缀表达式作为分隔符，然后再将出栈运算符输出到后缀表达式。（4）如果读入的是开括号“（”，则直接进栈；如果读入的是闭括号“）”，则一直出栈并输出到后缀表达式，知道遇到一个开括号“（”为止。开括号“（”和闭括号“）”均不输出到后缀表达式。（5）重复②、③、④步，知道中缀表达式结束，然后将栈中剩余的所有运算符依次出栈。每出栈一个运算符时，先输出一个逗号到后缀表达式作为分隔符，然后再将出栈运算符输出到后缀表达式。（6）给后缀表达式加上‘\0’作为字符串结束标志。1．2．2后缀表达式求值（1）定义一个double型的运算数栈，将中缀表达式转换得到的后缀表达式字符串自左向右依次读入。（2）如果读入的是运算对象，则将该运算对象串（下一个逗号分隔符前的部分所构成的数字字符串）转换为对应的多位整数值，然后将该整数值（将自动类型转换为double型）直接进入运算数栈。（3）如果读入的是运算符，则立即从运算数栈中弹出两个运算数，计算两个运实用数据结构基础课程设计报告2算数运算后的值（运算时先出栈的元素放在运算符后面，后出栈的元素放在运算符前面），并将计算结果存回运算数栈。（4）重复②、③步，直到后缀表达式结束，最后栈中保存的那个数即为该后缀表达式的计算结果。（5）和手工计算的结果进行比较，检验程序运行结果的正确性。假设输入中缀表达式为：（123+32）/5*2-15*18/（2+4）/15-7。转换后的后缀表达式为：123，32，+，5，/，2，*，15，18，*，2，4，+，/，15，/，-，7，-。后缀表达式求得的值为：52。1．3设计要求（1）运算对象存在多位整数。（2）遇到除数为0的情况，应能给出相应提示，并提醒重新输入中缀表达式。（3）%运算符左右遇到非整数时，应能自动对其进行取整；%运算符左右遇到负数时，应能给出相应提示，并提醒重新输入中缀表达式。（4）如果有两个同学同时完成该课题，要求分别采用顺序和链式结构实现其栈。2.总体设计2．1数据类型的定义calcolate（）：依次扫描string2中的字符，遇到数字则将其转化为整型数据存入栈中，遇运算符则将栈中栈顶的两个元素取出参与运算，并将计算结果放入栈中，如此直到运算符全部用完，最后一次运算结果即为后缀表达式的计算结果。实用数据结构基础课程设计报告32．2主程序的流程先把算术表达式转化成后缀表达式，在对后缀表达式进行计算。首先建立一个符号栈，用于存放字符和字符的优先级别；然后在建立一个数栈，用于辅助后缀表达式的计算；最后在定义一个字符串数组，用于存放后缀表达式。建立一个计算的函数，该函数用于两个数的计算，在调用这个函数的时候，传入三个参数，两个浮点型参数和一个字符型参数，根据不同的符号进行不同的计算。定义一个判断优先级别的函数，用于判断两个操作符的优先级别，在根据优先级的不同决定不同的操作。后缀表达式的取得，对算术表达式字符串进行挨个的扫描，如果是数字或者是小数点，则将数字或者小数点存放到字符数组中，每取完一个数字，则在后面用“|”隔开，如果是操作符，则和栈中得操作符进行比较，若扫描到的符号优先级比栈里的符号优先级低，则栈中元素出栈并存放到字符数组中。每出一个字符到字符数组中就在后面加“|”分隔。继续检查栈顶比较优先级，直到栈中元素优先级比扫描到的符号优先级低或者符号栈为空，则将此操作符入栈。若是“（”则无条件入字符栈，若是“）”则从字符栈中出字符直到遇到“（”为止。当字符数组扫描到最后的时候，计算并没有结束。然后得进行字符栈的判断，看是否已经为空栈，若不是空栈，则出栈字符，将字符存放到数组中。最后字符串数组中存放的就是后缀表达式。得到后缀表达式后，要用数栈进行后缀表达式的计算，后缀表start读入字符串string1[],i=0string1[i]?='\0';String1[i]是否为数字直接存入字符串string2中先向string2中存入一个空格，再判断该字符类型。为减价乘除号，判断栈顶元素优先级，比其高，先将栈顶元素出栈到string2中，再将其入栈。为开阔号，直接进栈。为闭括号，将栈顶元素依次弹出存入string2中，直至遇到开阔号。i++String2中存放转化好的后缀表达式z后缀表达式结果的计算calcolate（）输出运算结果end实用数据结构基础课程设计报告4达式的计算中，对新的数组进行从道到尾的扫描，如果遇到数字，以“|”为标记取出完整的操作数，用辅助数组存放，然后转化成浮点数存放到数栈中，遇到“|”则直接将数组下标往后走。遇到字符，则从数栈取出两个数进行计算，将计算的结果从新存放到数栈中，循环直到接到结束。最后存放在数栈中的数就是计算的结果。最后在主函数中调用此函数，进行结果的输出。3．详细设计（源代码）#includestdio.h#includemalloc.h#includestring.h#includestdlib.h#defineMAX60#defineDEMAX15#defineNULL0charstring1[MAX];charstring2[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;gets(string1);m=strlen(string1);for(i=0;i=m;i++)实用数据结构基础课程设计报告5{a=string1[i];if('0'=string1[i]&&string1[i]='9’){string2[j]=string1[i];j++;}else{switch(a){case'(':{p=(structnode*)malloc(sizeof(structnode));p-data=a;p-next=top;top=p;break;}case'*':case'/':string2[j]='';j++;if((top-data=='*')||(top-data=='/')){string2[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'-':{string2[j]='';j++;if(top-data=='+'||top-data=='-'||top-data=='*'||top-data=='/'){string2[j]=top-data;j++;;top-data=a;实用数据结构基础课程设计报告6break;}else{p=(structnode*)malloc(sizeof(structnode));p-data=a;p-next=top;top=p;break;}}case')':{string2[j]='';j++;if(top-data=='@'){printf(inputerror);break;}while(top-data!='('){string2[j]=top-data;j++;p=top;top=top-next;free(p);}p=top;top=top-next;free(p);break;}}}}while(top-data!='@'){string2[j]=top-data;j++;p=top;top=top-next;free(p);}string2[j]='#';printf(转化后的后缀表达式为