资源描述
题目:中缀表达式转化为后缀表达式算法及其后缀表达式计算算法的实现。内容:掌握栈的存储结构的C语言描述。 掌握中缀表达式和后缀表达式的存储结构。 掌握后缀表达式算法的实现。string1i?=0;读入字符串string1,i=0start流程图:YString1i是否为数字NString2中存放转化好的后缀表达式z后缀表达式结果的计算calcolate()i+先向string2中存入一个空格,再判断该字符类型。为减价乘除号,判断栈顶元素优先级,比其高,先将栈顶元素出栈到string2 中,再将其入栈。为开阔号,直接进栈。为闭括号,将栈顶元素依次弹出存入string2 中,直至遇到开阔号。直接存入字符串string2中YN输出运算结果endcalcolate():依次扫描string2中的字符,遇到数字则将其转化为整型数据存入栈中,遇运算符则将栈中栈顶的两个元素取出参与运算,并将计算结果放入栈中,如此直到运算符全部用完,最后一次运算结果即为后缀表达式的计算结果。程序代码:#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-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&string1idata=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-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-data!=)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=#) /遇#号结束标志,输出栈中的最后计算结果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=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();/建立一个链栈,并返回栈顶指针printf(请输入表达式:);head=assort(top);/中缀转化为后缀表达式calcolate(head);/后缀表达式的计算运行结果:
展开阅读全文