数据结构算法：中缀表达式转化为后缀表达式

题目：中缀表达式转化为后缀表达式算法及其后缀表达式计算算法的实现。内容：掌握栈的存储结构的C语言描述。掌握中缀表达式和后缀表达式的存储结构。掌握后缀表达式算法的实现。流程图：YNYNcalcolate（）：依次扫描string2中的字符，遇到数字则将其转化为整型数据存入栈中，遇运算符则将栈中栈顶的两个元素取出参与运算，并将计算结果放入栈中，如此直到运算符全部用完，最后一次运算结果即为后缀表达式的计算结果。程序代码：#includestdio.h#includemalloc.h#includestring.h#includestdlib.h#defineMAX60#defineDEMAX15#defineNULL0charstring1[MAX];charstring2[MAX];intj=0;structnode{start读入字符串string1[],i=0string1[i]?='\0';String1[i]是否为数字直接存入字符串string2中先向string2中存入一个空格，再判断该字符类型。为减价乘除号，判断栈顶元素优先级，比其高，先将栈顶元素出栈到string2中，再将其入栈。为开阔号，直接进栈。为闭括号，将栈顶元素依次弹出存入string2中，直至遇到开阔号。i++String2中存放转化好的后缀表达式z后缀表达式结果的计算calcolate（）输出运算结果endchardata;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++){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;break;}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(转化后的后缀表达式为:%s\n,string2);returntop;}structnode*calcolate(structnode*s){structnode*top,*p;char*q;intx,y,a;inti,n;top=s;//指向栈顶的指针for(i=0;i=j;i++)//遍历字符串string2{if(string2[i]='0'&&string2[i]='9'){q=&string2[i];a=atoi(q);for(n=i;string2[n]='0'&&string2[n]='9';n++){}p=(structnode*)malloc(sizeof(structnode));p-num=a;p-next=top;top=p;i=n-1;}elseif(string2[i]=='#')//遇#号结束标志，输出栈中的最后计算结果printf(计算结果为:%d\n,top-num);else{if(string2[i]==''){}else{y=top-num;p=top;top=top-next;free(p);x=top-num;p=top;top=top-next;free(p);switch(string2[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;}main(){structnode*top,*head;intm;top=Initialization();//建立一个链栈，并返回栈顶指针printf(请输入表达式：);head=assort(top);//中缀转化为后缀表达式calcolate(head);//后缀表达式的计算}运行结果：