《中缀表达式转后缀表达式报告.doc》由会员分享，可在线阅读，更多相关《中缀表达式转后缀表达式报告.doc（11页珍藏版）》请在三一办公上搜索。
1、目录1.课题分析111设计目的112主要内容1121中缀表达式转换为后缀表达式1122后缀表达式求值213设计要求22.总体设计221数据类型的定义222主程序的流程33详细设计（源代码）54调试分析1441问题11442问题21543问题3155测试结果156心得体会167参考文献161. 课题分析11设计目的（1）掌握栈“后进先出”的特点。（2）掌握栈的典型应用中缀表达式转后缀表达式，并利用后缀表达式求值。（3）掌握串或者数组的相关操作。12主要内容121中缀表达式转换为后缀表达式（1）定义一个运算符栈，并输入一个中缀表达式（运算对象存在多位整数，运算符为+、-、*、/、%及括号），然后从
2、中缀表达式中自左至右依次读入各个字符。（2）如果是第一次读入运算对象，也是直接输出到后缀表达式；如果不是第一次读入运算对象，并且前一个读入的字符是运算对象，也是直接输出到后缀表达式；如果不是第一次读入运算对象，并且前一个读入的字符是运算符，则先输出逗号作为分隔符，然后再将该运算对象输出到后缀表达式。（3）如果读入的是运算符，并且运算符栈为空，则将该运算符直接进栈；如果栈不为空，则比较该运算符和栈顶运算符的优先级。 若该运算符高于栈顶运算符的优先级，则将该运算符直接进栈；若该运算符低于或等于栈顶运算符的优先级，则将栈中高于或等于该运算符优先级的元素依次出栈，然后再将该运算符进栈。每出栈一个运算符
3、时，先输出一个逗号到后缀表达式作为分隔符，然后再将出栈运算符输出到后缀表达式。（4）如果读入的是开括号“（”，则直接进栈；如果读入的是闭括号“）”，则一直出栈并输出到后缀表达式，知道遇到一个开括号“（”为止。开括号“（”和闭括号“）”均不输出到后缀表达式。（5）重复、步，知道中缀表达式结束，然后将栈中剩余的所有运算符依次出栈。每出栈一个运算符时，先输出一个逗号到后缀表达式作为分隔符，然后再将出栈运算符输出到后缀表达式。（6）给后缀表达式加上0作为字符串结束标志。122后缀表达式求值（1）定义一个double型的运算数栈，将中缀表达式转换得到的后缀表达式字符串自左向右依次读入。（2）如果读入的是
4、运算对象，则将该运算对象串（下一个逗号分隔符前的部分所构成的数字字符串）转换为对应的多位整数值，然后将该整数值（将自动类型转换为double型）直接进入运算数栈。（3）如果读入的是运算符，则立即从运算数栈中弹出两个运算数，计算两个运算数运算后的值（运算时先出栈的元素放在运算符后面，后出栈的元素放在运算符前面），并将计算结果存回运算数栈。（4）重复、步，直到后缀表达式结束，最后栈中保存的那个数即为该后缀表达式的计算结果。（5）和手工计算的结果进行比较，检验程序运行结果的正确性。假设输入中缀表达式为：（123+32）/5*2-15*18/（2+4）/15-7。转换后的后缀表达式为：123，32，+
5、，5，/，2，*，15，18，*，2，4，+，/，15，/，-，7，-。后缀表达式求得的值为：52。13设计要求（1）运算对象存在多位整数。（2）遇到除数为0的情况，应能给出相应提示，并提醒重新输入中缀表达式。（3）%运算符左右遇到非整数时，应能自动对其进行取整；%运算符左右遇到负数时，应能给出相应提示，并提醒重新输入中缀表达式。（4）如果有两个同学同时完成该课题，要求分别采用顺序和链式结构实现其栈。2.总体设计21数据类型的定义calcolate（）：依次扫描string2中的字符，遇到数字则将其转化为整型数据存入栈中，遇运算符则将栈中栈顶的两个元素取出参与运算，并将计算结果放入栈中，如此直
6、到运算符全部用完，最后一次运算结果即为后缀表达式的计算结果。end输出运算结果后缀表达式结果的计算calcolate（）String2中存放转化好的后缀表达式zi+先向string2中存入一个空格，再判断该字符类型。为减价乘除号，判断栈顶元素优先级，比其高，先将栈顶元素出栈到string2 中，再将其入栈。为开阔号，直接进栈。为闭括号，将栈顶元素依次弹出存入string2 中，直至遇到开阔号。直接存入字符串string2中String1i是否为数字string1i?=0;读入字符串string1,i=0start22主程序的流程 先把算术表达式转化成后缀表达式，在对后缀表达式进行计算。首先建立
7、一个符号栈，用于存放字符和字符的优先级别；然后在建立一个数栈，用于辅助后缀表达式的计算；最后在定义一个字符串数组，用于存放后缀表达式。建立一个计算的函数，该函数用于两个数的计算，在调用这个函数的时候，传入三个参数，两个浮点型参数和一个字符型参数，根据不同的符号进行不同的计算。定义一个判断优先级别的函数，用于判断两个操作符的优先级别，在根据优先级的不同决定不同的操作。后缀表达式的取得，对算术表达式字符串进行挨个的扫描，如果是数字或者是小数点，则将数字或者小数点存放到字符数组中，每取完一个数字，则在后面用“|”隔开，如果是操作符，则和栈中得操作符进行比较，若扫描到的符号优先级比栈里的符号优先级低，
8、则栈中元素出栈并存放到字符数组中。每出一个字符到字符数组中就在后面加“|”分隔。继续检查栈顶比较优先级，直到栈中元素优先级比扫描到的符号优先级低或者符号栈为空，则将此操作符入栈。若是“（”则无条件入字符栈，若是“）”则从字符栈中出字符直到遇到“（”为止。当字符数组扫描到最后的时候，计算并没有结束。然后得进行字符栈的判断，看是否已经为空栈，若不是空栈，则出栈字符，将字符存放到数组中。最后字符串数组中存放的就是后缀表达式。得到后缀表达式后，要用数栈进行后缀表达式的计算，后缀表达式的计算中，对新的数组进行从道到尾的扫描，如果遇到数字，以“|”为标记取出完整的操作数，用辅助数组存放，然后转化成浮点数存
9、放到数栈中，遇到“|”则直接将数组下标往后走。遇到字符，则从数栈取出两个数进行计算，将计算的结果从新存放到数栈中，循环直到接到结束。最后存放在数栈中的数就是计算的结果。最后在主函数中调用此函数，进行结果的输出。3详细设计（源代码）#include#include#include#include#define MAX 60#define DEMAX 15#define NULL 0char string1MAX;char string2MAX;int j=0;struct node char data;int num;struct node *next;struct node *Initiali
10、zation()/初始化栈链,链栈不带头结点struct node *top;top=(struct node *)malloc(sizeof(struct node);top-data=;top-num=0;top-next=NULL;return top;struct node *assort(struct node *s)/输入字符串struct node *p,*top;int i;top=s;int m;char a;gets(string1);m=strlen(string1); for(i=0;i=m;i+)a=string1i;if(0=string1i&string1idat
11、a=a;p-next=top; top=p; break; case *: case /:string2j= ;j+;if(top-data=*)|(top-data=/)string2j=top-data;j+; /比其高，现将栈顶运算符出栈，再进栈。top-data=a;break;elsep=(struct node *)malloc(sizeof(struct node);/否，直接进栈p-data=a;p-next=top;top=p;break; case +: case -:string2j= ;j+;if(top-data=+|top-data=-|top-data=*|top
12、-data=/)string2j=top-data;j+;top-data=a;break;else p=(struct node *)malloc(sizeof(struct node);p-data=a;p-next=top;top=p;break; case ):string2j= ;j+;if(top-data=)printf(input error);break;while(top-data!=()string2j=top-data;j+;p=top;top=top-next;free(p); p=top;top=top-next;free(p);break;while(top-da
13、ta!=)string2j=top-data;j+;p=top;top=top-next;free(p);string2j=#; printf(转化后的后缀表达式为:%sn,string2);return top;struct node *calcolate(struct node *s)struct node *top,*p;char *q;int x,y,a;int i,n;top=s;/指向栈顶的指针for(i=0;i=0&string2i=0&string2nnum=a;p-next=top;top=p;i=n-1;elseif(string2i=#) /遇#号结束标志，输出栈中的最后
14、计算结果printf(计算结果为:%dn,top-num);elseif(string2i= )elsey=top-num;p=top;top=top-next;free(p);x=top-num;p=top;top=top-next;free(p);switch(string2i)case +:a=x+y; p=(struct node *)malloc(sizeof(struct node); p-num=a;p-next=top;top=p; break; case -:a=x-y; p=(struct node *)malloc(sizeof(struct node ); p-num=
15、a;p-next=top;top=p; break; case *:a=x*y; p=(struct node *)malloc(sizeof(struct node ); p-num=a;p-next=top;top=p; break; case /:a=(float)x/y; p=(struct node *)malloc(sizeof(struct node ); p-num=a;p-next=top;top=p; break;return 0;main()struct node *top,*head;int m;top=Initialization();/建立一个链栈，并返回栈顶指针p
16、rintf(请输入表达式：);head=assort(top);/中缀转化为后缀表达式calcolate(head);/后缀表达式的计算4调试分析41问题1l 从字符数组中截取出数字的操作，并转化成浮点型的数不正确。计算的结果有时候是一个意想不到的很大的数。解决方法：从字符数数组中将数字截取出来就是为了能进行计算，而数字是单个字符的形式存在，必须把一个完整的数从算术表达式中截取出来，如果遇到数字的字符就是一个数字的入口，然后循环取出直到遇到不是数字或者小数点为止。而这些取出的数字是一堆离散的数字字符。这时候就需要建立一个辅助的数组来存放这些数字字符以组成一个数字的字符。用一个辅助的索引将数字的
17、组成字符一个一个从数组中取出来，存放到新的数组中，以得到一个字符串的数字。从数组中截取出一个数后，将取出的数用atof 函数进行转化成浮点型的数。在把浮点型的数存放到数栈中，在后面的计算中取出。在调试中第一个取出的浮点型数是正确的，当遇到后面截取的数的长度比第一个数短的时候，发现取出的数和第一个数的位数相同了。经过分析，每次截取完数字后并没有对辅助数组进行重新的初始化，数组中宗存放着前一个字符，一旦遇到数字比前面的数字短的的情况，后面的数字只覆盖了前面的数字的前几位，后面的几位都是原先的数字。造成取出的结果是错误的。解决问题的方法可以在每次存放数字之前，把辅助数组进行初始化，结果能正确计算表达
18、式。42问题2l 如何生成后缀表达式，将数与字符存放在一个字符串中。解决方法：想把数字从字符数组中取出来，然后再存入后缀表达式中，从字符数组中取出是很容易的，但是在把这些数字和操作符进行存入一个后缀表达式数的时候出现了问题，因为c 语言中没有这样的字符数组，所以取出的数字根本没法和操作符一块存到一个数组中去。改变一种想问题的方法，就是不把字符数组的数字都截取出来，而是把数字进行一个分割，让数字还依旧存放在数组中，只是在每个数字的后面都加上一个分割符号“|”，然后要是遇到操作符也将操作符存放到这个数组中并且也加入分隔符，这样就组成了一个全新的数组，也即是后缀表达式。这里的修改是遇到数字，边走边存
19、，一个数字取完后就在数字的后面加分隔符。如果是操作符，则进行优先级的判断，根据判断的结果把操作符加入到数组中，以生成后缀表达式。对新生成的后缀表达式数组在进行计算，在后缀表达式中将数字截取出来，这样子做的效果比原先就截取出来好实现。通过扫面后缀表达式，根据分隔符可以很简单的就截取出一个数字字符串，再把字符串数字转化成浮点数存放到数栈中，遇到操作符就计算，从数栈中取出两个数字，连同操作一起调用函数进行计算。循环扫描，直到扫描到“0”，最后将结果从数栈中取出作为结果返回给主函数。43问题3l 问题3：如何解决除数是零的问题解决方法：在进行除法运算的时候，遇到除数为 0 的情况肯定是特殊处理的，但是
20、该如何让程序在遇到这个问题的时候退出程序，并输出提示错误的信息。这时候需要用到一个c 语言里面自带的一个函数，如果是除数为零的情况就调用函数exit（-1），给赋值为-1的时候就能正确低从程序中跳出来，只要在跳出之前打印错误的信息就可以达到想要的效果了。5测试结果6心得体会通过这该程序的编写，我发现了学习上的挺多问题，尤其在遇到指针的问题的时候，很茫然，以后在学习中要多注意指针的使用，以达到熟练掌握的程度，平时的学习中一定要多写程序，多写一些才回把知识用得自然。其实大一就开始学习C语言，可是，当时学的时候就觉得语言好像是学会了，可是一遇到编程的问题还是头大，总感觉没有什么思路，而这次作业，给自
21、己一个不得不动手操作的机会，在十一的这几天中，复习了以前学过的C的基本知识，然后一点一点的摸索，遇到了错误和同学一起讨论，有问题自己想办法解决，最后程序调试出来的时候，会觉得真的很高兴。我知道，我们现在的水平还很差，要想学习好这门课，在以后就要多动手操作，书上的例题或算法，最好都自己编写程序实现，那样可以加深对算法的理解，也可以提高我们编程的水平。同时，很多的东西，理解了，可是在实现的时候还是有很多的错误发生，在以后的练习和实践中，应该多动手，遇到问题多思考，即使方案不是最优的也要想办法自己解决，然后和好的方案进行比较，从中找出自己的差距在哪里。7参考文献1陈元春 王中华 张亮 王勇编著，实用数据结构基础（第三版），2011年2月，中国铁道出版社。2谭浩强 编著，C程序设计（第四版），2010年6月，清华大学出版社。
