数据结构代码 中缀转后缀表达式算法及源代码.doc

#include#include#include#define MAX 100 /* 表达式最大长度 */#define true 1#define false 0 /* 定义数据栈 */typedef struct LinkStack1 float data; struct LinkStack1 *next;LinkStack1,*Top1;int initStack1(Top1 *t) /*数据栈初始化*/ *t=NULL; return true;int push1(Top1 *t,float val) /*数据栈插入元素*/ Top1 p=(Top1)malloc(sizeof(LinkStack1);/* 开内存 */ if(p=NULL) return false; p-data=val; p-next=*t; *t=p; return true;float getTop1(Top1 *t) /*取数据栈元素*/ return (*t)-data;int pop1(Top1 *t,float *val) /*推出数据栈元素并存到*val中*/ Top1 p=*t; if(p=0) return false; *t=p-next; *val=p-data; free(p); /* 释放所占内存 */ return true; /* 定义操作符栈 */typedef struct LinkStack2 int data; struct LinkStack2 *next;LinkStack2,*Top2;int initStack2(Top2 *t) /*数据栈初始化*/ *t=NULL; return true;int push2(Top2 *t,char val) /*操作符栈插入元素*/ Top2 p=(Top2)malloc(sizeof(LinkStack2); /* 开内存 */ if(p=0) return false; p-data=val; p-next=*t; *t=p; return true;int getTop2(Top2 *t) /*取操作符栈元素*/ return (*t)-data;int pop2(Top2 *t,char *val) Top2 p=*t; if(p=0) return false; *t=p-next; *val=p-data; free(p); /* 释放所占内存 */ return true; /* 计算 */float calc(float a, char op, float b) int d,e; switch(op) case +:return a+b; /* 计算+ */ case -:return a-b; /* 计算- */ case *:return a*b; /* 计算* */ case /: /* 计算/，若被除数为零，报错 */ if(b=0) printf(Error Divisor is 0n); return false; return a/b; case %: /* 计算%，若被取余数为零报错 */ d=(int)a; e=(int)b; if(e=0) printf(Error Divisor is 0n); return false; return (float)(d%e); default:printf(Error ! not opratern); /* 非操作符报错 */ return false; /* 判断操作符优先级 */char priority(char a,char b) if(a=&b=n)return*; /* * 表示结束 */ if(a=(&b=)return#; /* # 表示左右括号相遇 */* 、= 分别表示优先级：小于、大于、相等 */ if(a=)return; if(a=)return; if(a=()return; if(b=()return; if(a=+|a=-)&(b=/|b=*|b=%)return; if(a=+|a=-)&(b=+|b=-)return=; if(a=*|a=/|a=%)&(b=*|b=/|b=%)return=;/* 是否操作符 */int isOp(char m) if(m=*|m=/|m=%|m=(|m=)|m=+|m=-|m=n) return true; return false; /* 中缀变后缀 */void Infix(char a,char b) char c,p,x; int i=0,j=0; Top2 op; initStack2(&op); /*初始化操作符栈*/ push2(&op,=); /* =作为栈底元素 */ while(ai!=0) if(!isOp(ai) /*是操作数，直接输出*/ bj+=ai; else bj+= ; /* 数字和数字用空格隔开 */ switch(priority(getTop2(&op),ai) /*比较两个算符的优先级*/ case: case=: while(priority(getTop2(&op),ai)=) |(priority(getTop2(&op),ai)=) pop2(&op,&c); /*当前算符优先级低，则取栈顶*/ bj+=c; if(priority(getTop2(&op),ai)=data!=)/* 字符栈元素全都放到b数组中 */ pop2(&op,&p); bj+=p; i+; for(i=0;i=0&a*i=0&a*i=9) x=x*10+a*i-0; (*i)+; k+; /*记录多少小数位数*/ while(k!=0) x=x/10; k=k-1; return x;/* 第一种：后缀表达式计算 */float the_fir_Exp(char c) int i=0; float a,b,n; Top1 dig; initStack1(&dig); /*初始化操作数栈*/ push1(&dig,0); while(ci!=0) /*为表达式的结束标志*/ if(!isOp(ci)&ci!= ) /*为操作数*/ n=charToNum(c,&i); i=i-1; /*转换后 i值应该减一 否则丢掉一个字符*/ push1(&dig,n); else if(isOp(ci) /*为操作符*/ pop1(&dig,&a);/*取一操作数*/ pop1(&dig,&b); /*取另一操作数*/ push1(&dig,(calc(b,ci,a); /*计算，并压入栈*/ i+; return getTop1(&dig); /* 第二种计算方法 */float the_sec_Exp(char a) int i=0,j; char bMAX,c; float m,n; Top2 op; Top1 dig; initStack2(&op); /*初始化操作符栈*/ push2(&op,=); initStack1(&dig); /*初始化操作数栈*/ push1(&dig,0); while(ai!=0) if(!isOp(ai) /*是操作数*/ j=0; for(;!isOp(ai)&ai!=0;i+) bj+=ai; bj=+; /*+结束*/ j=0; push1(&dig,(charToNum(b,&j); /*转换，并压入栈*/ else switch(priority(getTop2(&op),ai)/*比较两个算符的优先级*/ case: case=: pop2(&op,&c); /*取出操作符*/ pop1(&dig,&m);/*取一操作数*/ pop1(&dig,&n); /*取另一操作数*/ push1(&dig,(calc(n,c,m); /*计算，并压入栈*/ break; case#: pop2(&op,&c); i+; break; case*: break; pop2(&op,&c); /*取出操作符*/ while(c!=) /*=为操作符栈的结束标志*/ pop1(&dig,&m); /*取一操作数*/ pop1(&dig,&n); /*取另一操作数*/ push1(&dig,(calc(n,c,m); /*计算，并压入栈*/ pop2(&op,&c); /*取出操作符*/ return getTop1(&dig); /*返回值为数字栈栈顶*/* 主函数 */void main() loop: /* 确定再次输入数据计算，及输入错误时 循环 */ int i,k,j; int zMAX,yMAX; char aMAX=,bMAX,ch; float m; zMAX=;yMAX=; /* 初始化a/,z,y*/ printf(nInput:); scanf(%s,&a); /* 输入表达式 */ /* 容错四种情况 */ for(i=0;ai!=0;i+) if(!(ai=0&ai=9|isOp(ai)|ai=.)/* 1 非数字、小数点和操作符 */ printf(-); for(j=0;j=MAX-1) /* 2 表达式越界 */ printf(input too long! intput again.n); goto loop; for(i=0,j=0,k=0;ai!=0;i+) if(ai=() zk+=i; /*zk为记录（的位置 k表示（的数目*/ if(ai=) yj+=i; /*yk为记录）的位置 y表示 ）的数目*/ if(k!=j)/* 3 左右括号不相等 */ printf(-); if(kj) for(i=0;izk-1;i+) printf(-); else if(kj) for(i=0;iyj+) printf(-); for(i=0;izk-1;i+) printf(-); printf(n); printf(input wrong! )first then ( intput again:n); goto loop; /* 中缀变后缀,再计算 */ printf(postfix expressions is:); Infix(a,b); /* 中缀变后缀 */ m=the_fir_Exp(b); /* 后缀表达式计算 */ printf(nthe first method result is :%lfn,m); /* 直接计算 */ m=the_sec_Exp(a); printf(the second method result is