《中缀表达式转后缀表达式》由会员分享，可在线阅读，更多相关《中缀表达式转后缀表达式（7页珍藏版）》请在金锄头文库上搜索。
1、昆明理工大学信息工程与自动化学院学生实验报告（20112012 学年 第 1 学期）课程名称：数据结构 开课实验室：信自楼 442 2011 年 11 月 04 日年级、专业、班 学号 姓名 成绩实验项目名称 中缀表达式转后缀表达式 指导教师教师评语教师签名：年 月 日1、程序功能：（1）.中缀表达式转换为后缀表达式的主要函数设置如下：主程序：main()struct node *top,*head;int m;top=Initialization();/建立一个链栈，并返回栈顶指针printf(请输入表达式：);head=assort(top);/中缀转化为后缀表达式calcolate(he
2、ad);/后缀表达式的计算（2）.程序代码如下：#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 *Initialization()/初始化栈链,链栈不带头结点struct node *top;top=(struct node *)malloc(sizeof(struct node);top-da
3、ta=;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;idata=a;p-next=top;top=p;break;case *:case /:string2j= ;j+;if(top-data=*)|(top-data=/)string2j=top-data;j+; /比其高，现将栈顶运算符出栈，再进栈。top-data
4、=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-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 ):str
5、ing2j= ;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-data!=)string2j=top-data;j+;p=top;top=top-next;free(p);string2j=#;printf(转化后的后缀表达式为:%sn,string2);return top;struct node *calcolate(struct nod
6、e *s)struct node *top,*p;char *q;int x,y,a;int i,n;top=s;/指向栈顶的指针for(i=0;i=0&string2i=0n+)p=(struct node *)malloc(sizeof(struct node );p-num=a;p-next=top;top=p;i=n-1;elseif(string2i=#) /遇#号结束标志，输出栈中的最后计算结果printf(计算结果为:%dn,top-num);elseif(string2i= )elsey=top-num;p=top;top=top-next;free(p);x=top-num;
7、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=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
8、=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();/建立一个链栈，并返回栈顶指针printf(请输入表达式：);head=assort(top);/中缀转化为后缀表达式calcolate(head);/后缀表达式的计算2、实验报告：(1).运行截图如下： (2).算法分析(3).原理分析把运算符放在参与运算的
9、两个操作数中间的算术表达式称为中缀表达式；把运算符放在参与运算的两个操作数后面的算术表达式称为后缀表达式。转换时，从左往右扫描中缀表达式，用栈来存放表达式中的运算符、开括号以及在此括号后暂不确定计算次序的其他符号。当输入的数是操作数时，直接输出到后缀表达式序列；当遇到开括号时，也把它压入栈内；start读入字符串 string1,i=0string1i?=0;String1i是否为数字String2 中存放转化好的后缀表达式z后缀表达式结果的计算 calcolate（）输出运算结果end直接存入字符串 string2 中先向 string2 中存入一个空格，再判断该字符类型。为减价乘除号，判断
10、栈顶元素优先级，比其高，先将栈顶元素出栈到 string2 中，再将其入栈。为开阔号，直接进栈。为闭括号，将栈顶元素依次弹出存入 string2 中，直至遇到开阔号。i+当输入遇到闭括号时，先判断栈是否为空，若为空（括号不匹配） ，应该作为错误异常处理，清栈退出。若非空，则把栈中元素依次弹出，直到遇到第一个开括号为止，将弹出的元素输出到后缀表达式序列中（弹出的开括号不放到序列中） ，若没有遇到开括号，说明括号不匹配，做异常处理，清栈退出。当输入为运算符（四则运算+-*/之一）时，分情况：若栈顶非空并且栈顶不是开括号并且栈顶的运算符优先级不低于输入的运算符的优先级时，反复操作将栈顶元素输出，放到
11、后缀表达式序列中；否则，将运算符压入栈内。最后，当中缀表达式的符号全部读入时，若栈内仍有元素，把他们全部依次弹出，放在后缀表达式序列的尾部。若弹出的元素遇到开括号，则说明括号不匹配，做异常处理清栈退出。(4).总结通过这该程序的编写，我发现了学习上的挺多问题，尤其在遇到指针的问题的时候，很茫然，以后在学习中要多注意指针的使用，以达到熟练掌握的程度，平时的学习中一定要多写程序，多写一些才回把知识用得自然。其实大一就开始学习 C 语言，可是，当时学的时候就觉得语言好像是学会了，可是一遇到编程的问题还是头大，总感觉没有什么思路，而这次作业，给自己一个不得不动手操作的机会，复习了以前学过的 C 的基本知识，然后一点一点的摸索，遇到了错误和同学一起讨论，有问题自己想办法解决，最后程序调试出来的时候，会觉得真的很高兴。我知道，我们现在的水平还很差，要想学习好这门课，在以后就要多动手操作，书上的例题或算法，最好都自己编写程序实现，那样可以加深对算法的理解，也可以提高我编程的水平。我觉得老师说的很对，要学好编程先从书本上的程序开始，读懂代码是第一步，上机实践是第二步，另外背一些代码是很有必要的，不会写但可以通过别人的东西来充实自己，为自己积累知识质的积累导致量的飞跃。
