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

1、题目：中缀表达式转化为后缀表达式算法及其后缀表达式计算算法的实现。内容：掌握栈的存储结构的C语言描述。 掌握中缀表达式和后缀表达式的存储结构。 掌握后缀表达式算法的实现。string1i?=0;读入字符串string1,i=0start流程图：YString1i是否为数字NString2中存放转化好的后缀表达式z后缀表达式结果的计算calcolate（）i+先向string2中存入一个空格，再判断该字符类型。为减价乘除号，判断栈顶元素优先级，比其高，先将栈顶元素出栈到string2 中，再将其入栈。为开阔号，直接进栈。为闭括号，将栈顶元素依次弹出存入string2 中，直至遇到开阔号。直接存入

2、字符串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 *n

3、ext;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;

4、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=+|

5、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;f

6、ree(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(str

7、ing2i=#) /遇#号结束标志，输出栈中的最后计算结果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 *to