数据结构两种方式实现表达式的计算.doc

用两种方式实现表达式自动计算一、设计思想一直接计算结果的设计思想：此种算法最主要是用了两个栈：操作符栈和操作数栈，以及一个数组，用来存放用户输入的表达式。从数组中获取元素，如果是操作数，则直接进操作数栈，但如果获取的是操作符，则要分情况讨论，如下：（这里讨论优先级时暂不包括“（”和“）”的优先级）1.如果获取的操作符a的优先级高于操作符栈栈顶元素b的优先级，则a直接入操作符栈;2.如果获取的操作符a的优先级低于操作符栈栈顶元素b的优先级，则b出栈，a进栈，并且取出操作数栈的栈顶元素m，再取出操作数栈新的栈顶元素n，如果b为+，则用n+m，若为减号，则n-m，依此类推，并将所得结果入操作数栈；3.如果获取的是“（”，则直接进操作符栈；4.如果获取的是“）”，则操作符栈的栈顶元素出栈,做类似于情况2的计算，之后把计算结果入操作数栈，再取操作符栈顶元素，如果不是“（”，则出栈，重复操作，直到操作符栈顶元素为“（”，然后“（”出栈；5.当表达式中的所有元素都入栈后，看操作符栈中是否还有元素，如果有，则做类似于情况2 的计算，并将结果存入操作数栈，则操作数栈中最终的栈顶元素就是所要求的结果。二中缀转后缀及对后缀表达式计算的设计思想：中缀转后缀时主要用了一个操作符栈和两个数组（用数组一用来存用户输入的表达式，用数组二来存后缀表达式），从数组一中依次获取元素，如果获取的是操作数，则直接存入数组二中，如果获取的是操作符也需分情况讨论，如下：（这里讨论优先级时暂不包括“（”和“）”的优先级）1. 如果获取的操作符a的优先级高于操作符栈栈顶元素b的优先级，则a直接入操作符栈;2. 如果获取的操作符a的优先级低于操作符栈栈顶元素b的优先级，则b出栈，a进栈，并且将b存入到数组二中；3.如果获取的是“（”，则直接进操作符栈；4.如果获取的是“）”，则操作符栈的栈顶元素出栈,并依次存入到数组二中，直到操作符栈栈顶元素为“（”，然后将“（”出栈；5.当表达式中的所有元素都入栈或存入到数组二之后，看操作符栈中是否还有元素，如果有，则依次出栈，并且依次存入到数组二中，最后打印数组二中的字符串，则此字符串即为要求的后缀表达式。对后缀表达式的计算方法：主要用到了一个操作数栈，从数组二中依次取出元素，如果是操作数，则进栈，如果是操作符，则从操作数栈中依次取出两个栈顶元素a1和a2,如果操作符是“/”,则计算a2/a1,将计算结果再次进栈，依此类推，最终栈顶元素即为计算的最终结果。在这两种算法中，应该特别注意一点：人的习惯，用户在输入表达式时，容易这样输入，如：3*4（3+2），这样是不可取的，应必须要用户输入3*4*（3+2），这是在设计思想上错误提示的很重要一点，否则计算不全面！二、算法流程图第一个图是直接计算的流程图，图中反应除了这种方法的大致设计思路，但是有些细节没有反映出来，比如说，怎样把字符型数据转换为浮点型数据，就没有反映出来。特别说明的是棱形左边代表Y，右边代表N，具体流程图如下：开始用户输入表达式将表达式存入到数组expr构造两个栈从expr中获取元素是否为数数入操作数栈是否为或优先级是否高于操作符栈栈顶元素优先级进符号栈操作符栈里栈顶元素出栈，并做相应的计算，将结果再入操作数栈，从数组里取的元素入操作符栈是否为“（”进操作符栈操作符栈里元素出栈，做相应操作直到栈顶元素为“（”，“（”出栈数组内元素是否取尽操作符栈内元素全部出栈，做相应计算，所得结果进操作数栈，即为最终结果结束图1 、直接计算算法流程图第二个图是对后缀表达式的求值的算法流程图，同样，棱形左边代表Y，右边代表N，怎样把字符型数据转换为浮点型数据，也同样没有反映出来。具体图如下：开始从后缀数组中获取元素是否为数存入操作数栈中为操作符，则从操作数栈中取值作相应操作后缀数组中是否还有元素栈里最终栈顶元素即为最终结果结束图2 、后缀表达式计算的流程图第三个图是从中缀表达式转为后缀表达式算法的流程图，同样的，棱形左边代表Y，右边代表N，在我的具体代码中，用户输入表达式时是要求以#结尾的，这些在流程图中均省略了，细节的处理，流程图中没有反映出来，主要就表现主要的思路算法。具体的流程图如下：开始用户输入表达式将表达式存入到数组expr构造一个操作符栈和一个存放后缀表达式的数组从expr中获取元素是否为数存入后缀数组中是否为或优先级是否高于操作符栈栈顶元素优先级进操作数栈操作符栈里栈顶元素出栈，并存入到后缀数组中，然后从数组里取的元素入操作符栈是否为“（”进操作符栈操作符栈里元素出栈，并依次存入到后缀数组中，直到栈顶元素为“（”，“（”出栈数组内元素是否取尽操作符栈内元素全部出栈，并依次存入到后缀数组中，则得后缀表达式结束图3 、中缀转后缀的流程图三、源代码一下面给出的是用直接计算算法实现的程序的源代码：#include#include#include/*将字符串转换成浮点数*/#define MAX 100typedef struct /*定义一个存放操作符的栈*/ char * base; char * top;/*栈顶指针*/ int stacksize;SqStack1;typedef struct /*定义一个存放操作数的栈*/ float * base; float * top; int stacksize;/*栈的大小*/SqStack2;char InitStack1(SqStack1 *s)/*构造一个空栈，放操作符*/ s-base=(char *)malloc(MAX*sizeof(char);/*分配内存区域*/ if(!s-base) exit(-1); s-top=s-base; s-stacksize=MAX;/*栈的大小*/ return 1;float InitStack2(SqStack2 *s)/*构造一个空栈，放操作数*/ s-base=(float *)malloc(MAX*sizeof(float); if(!s-base) exit(-1); s-top=s-base;/*空栈*/ s-stacksize=MAX; return 1;int StackEmpty1(SqStack1 *s) /* 判断是否为空 */ if(s-top=s-base) return 1; else return 0;void Push1(SqStack1 *S,char x)/*入栈*/ if(S-top=S-base) S-base=(char *)realloc(S-base,(S-stacksize+10)*sizeof(char);/*追加空间*/ if(!S-base) exit(-1); S-top=S-base+S-stacksize; S-stacksize=S-stacksize+10;/*扩大栈*/ *S-top+=x; return 1;void Push2(SqStack2 *S,float x)/*入栈*/ if(S-top=S-base) S-base=(float *)realloc(S-base,(S-stacksize+10)*sizeof(float);/*追加空间*/ if(!S-base) exit(-1); S-top=S-base+S-stacksize; S-stacksize=S-stacksize+10;/*扩大栈*/ *S-top+=x; return 1; char Pop1(SqStack1 *S,char x)/*出栈*/ if(S-top=S-base) return 0; x=*(-S-top); return x;float Pop2(SqStack2 *S,float x)/*出栈*/ if(S-top=S-base) return 0; x=*(-S-top); return x; char GetTop1(SqStack1 *S,char x)/*获取栈顶元素*/ if(S-top=S-base) return 0; x=*(S-top-1); return x;int SelLeve(char c1) /*优先级的比较*/ if(c1=+| c1=-) return 1;/*将+-号的优先级置为1*/ else if (c1=*| c1=/ | c1=%) return 2; /*将*/%号的优先级置为2*/ else if(c1=() return 0;/*将（号的优先级置为0*/ float num1,num2,b;float Fenlei(float num1,float num2,char d)/*对数字的处理*/switch(d) case+:b=num2+num1;break;/*若是+，则用数2加上数1，下面的一次类推*/ case-:b=num2-num1;break; case*:b=num2*num1;break; case/:b=num2/num1;break; case%:b=(int)(num2)%(int)(num1);break; return b;/*返回计算结果*/void main() SqStack1 optr; SqStack2 opnd;/*optr为符号栈，opnd为数字栈*/ char expr100,c,zhh10,d,out;/*expr储存用户输入的表达式，zhh存储表达式中的数字和小数点以便于把字符型改为浮点型，out代表从符号栈中取出的栈顶元素,d便于观察符号栈中的栈顶元素*/ int i=0,m=0,dlevel;/*用dlevel表示符号栈栈顶元素的优先级*/ float shu,e,result; /*由shu代表转化之后的浮点数*/ InitStack1(&optr); Push1(&optr,#); /*初始化栈*/ InitStack2(&opnd); printf(plesae input the expression_r(end of #):);/*请用户输入表达式*/ getch(); gets(expr);/*将表达式存入数组中*/ rongcuo(expr);/*检验表达式是否正确*/ while(expri!=#&GetTop1(&optr,#) c=expri; if(c=48&c=57|expri+1=clevel)/*若栈顶的优先级比较高*/ out=Pop1(&optr,out);/*栈顶元素出栈并计算*/ num1=Pop2(&opnd,e); num2=Pop2(&opnd,e);/*将操作数栈的最顶层的两个数出栈*/ b=Fenlei(num1,num2,out);/*计算*/ Push2(&opnd,b);/*将计算结果入操作数栈*/ Push1(&optr,c);/*将从表达式中获取的符号入栈*/ i+; else Push1(&optr,c);/*如果从表达式中获取的元素比操作符栈中栈顶元素的优先级高，则直接入操作符栈*/ i+; else if(c=*|c=/|c=%)/*情况三：如果获取的字符表示乘除或者取模*/ int clevel=2;/*表示获取的符号的优先级*/ d=GetTop1(&optr,d); dlevel=SelLeve(d);/*用dlevel表示符号栈栈顶元素的优先级*/ if(d!=#&dlevel=clevel)/*若栈顶的优先级比较高*/ out=Pop1(&optr,out);/*栈顶元素出栈并计算*/ num1=Pop2(&opnd,e); num2=Pop2(&opnd,e);/*将操作数栈的最顶层的两个数出栈*/ b=Fenlei(num1,num2,out);/*计算*/ Push2(&opnd,b);/*将计算结果入操作数栈*/ Push1(&optr,c);/*将从表达式中获取的符号入栈*/ i+; else Push1(&optr,c);/*如果从表达式中获取的元素比操作符栈中栈顶元素的优先级高，则直接入操作符栈*/ i+; else if(c=()Push1(&optr,c);i+;/*情况四：获取的是左括号，则直接入符号栈*/ else if(c=)/*情况五：获取的是右括号*/ while(GetTop1(&optr,d)!=() out=Pop1(&optr,out);/*符号栈栈顶元素出栈*/ num1=Pop2(&opnd,e); num2=Pop2(&opnd,e);/*对操作数栈的栈顶元素计算*/ b=Fenlei(num1,num2,out); Push2(&opnd,b);/*将计算结果存入操作数中*/ Pop1(&optr,c);/*左括号出栈*/ i+; while(expri=#&!StackEmpty1(&optr)/*将用户输入的表达式全部存入到栈中后，如果操作符栈中还有操作符，则全部出栈计算*/ out=Pop1(&optr,out); num1=Pop2(&opnd,e); num2=Pop2(&opnd,e); b=Fenlei(num1,num2,out);/*计算*/ Push2(&opnd,b); result=Pop2(&opnd,result); printf(nthe result is %f,result);/*打印结果*/ getch();int rongcuo(char expr)/*用来检验表达式是否正确*/ int i=0,reset=1,l,p=0,q=0; l=strlen(expr);/*获取表达式的长度*/ for(i;i=48&expri=57&expri+1=()/*数与左括号之间必须有运算符，比如3(2+1)这种写法是错误的，而应写成3*(2+1)*/ printf(nBetween the number and (,you must input +-*/or%); reset=-1;/*一种标识*/ else if(expri=#)/*表达式中只能以#结尾，中间不能出现#*/ printf(nYou can not put the # in the middle except the last ! ); reset=-1; else if(expri=()p+;/*如果是(，p加1,用于括号匹配*/ else if(expri=)q+;/*如果是)，q加1,用于括号匹配*/ else if(expri+1=48&(expri=/|expri=%)/*/与%后面不能为0*/ printf(nBehind /and%,you put the zero!);reset=-1; if(p!=q)printf(nThe ( does not match the )!);reset=-1; /*括号不匹配*/if(reset=-1) while(reset=-1) printf(nPlesae input the expression_r again(end of #):);/*表达式输入有误，重新输入*/ getch(); reset=1; gets(expr);/*用expr存表达式*/ rongcuo(expr);/*继续检查表达式输入是否正确*/ else return;/*如果表达式输入正确，则返回主函数*/二下面给出的是用中缀转后缀算法实现的程序的源代码： #include#include#include/*将字符串转换成浮点数*/#define MAX 100typedef struct/*定义一个存放操作符的栈*/ char * base; char * top;/*栈顶指针*/ int stacksize;SqStack1;typedef struct/*定义一个存放操作数的栈*/ float * base; float * top; int stacksize;/*栈的大小*/SqStack2;char InitStack1(SqStack1 *s)/*构造一个空栈，放操作符*/ s-base=(char *)malloc(MAX*sizeof(char);/*分配内存区域*/ if(!s-base) exit(-1); s-top=s-base; s-stacksize=MAX;/*栈的大小*/ return 1;float InitStack2(SqStack2 *s)/*构造一个空栈，放操作数*/ s-base=(float *)malloc(MAX*sizeof(float); if(!s-base) exit(-1); s-top=s-base;/*空栈*/ s-stacksize=MAX; return 1;int StackEmpty1(SqStack1 *s) /* 判断栈是否为空 */ if(s-top=s-base) return 1; else return 0; void Push1(SqStack1 *S,char x)/*入栈*/ if(S-top=S-base) S-base=(char *)realloc(S-base,(S-stacksize+10)*sizeof(char);/*追加空间*/ if(!S-base) exit(-1); S-top=S-base+S-stacksize; S-stacksize=S-stacksize+10;/*扩大栈*/ *S-top+=x; return 1;void Push2(SqStack2 *S,float x)/*入栈*/ if(S-top=S-base) S-base=(float *)realloc(S-base,(S-stacksize+10)*sizeof(float);/*追加空间*/ if(!S-base) exit(-1); S-top=S-base+S-stacksize; S-stacksize=S-stacksize+10;/*扩大栈*/ *S-top+=x; return 1; char Pop1(SqStack1 *S,char x)/*出栈*/ if(S-top=S-base) return 0; x=*(-S-top); return x;float Pop2(SqStack2 *S,float x)/*出栈*/ if(S-top=S-base) return 0; x=*(-S-top); return x; char GetTop1(SqStack1 *S,char x)/*获取栈顶元素*/ if(S-top=S-base) return 0; x=*(S-top-1); return x;int SelLeve(char c1) /*优先级的比较*/ if(c1=+| c1=-) return 1;/*将+-号的优先级置为1*/ else if (c1=*| c1=/ | c1=%) return 2;/*将*/%号的优先级置为2*/ else if(c1=() return 0;/*将（号的优先级置为0*/void main() char expr100;/*用此数组存放表达式*/ printf(plesae input the expression_r(end of #):); gets(expr);/*将表达式存入数组中*/ rongcuo(expr);/*检验表达式是否正确*/ houzhui(expr);/*转后缀并计算*/int rongcuo(char expr)/*用来检验表达式是否正确*/ int i=0,reset=1,l,p=0,q=0; l=strlen(expr);/*获取表达式的长度*/ for(i;i=48&expri=48&c=57|expri+1=clevel)/*若栈顶的优先级比较高*/ hzn=Pop1(&optr,out);/*将此栈顶元素存入后缀数组中*/ n+; hzn=|;/*数与操作符之间用|隔开*/ n+; Push1(&optr,c);/*将+或者减号入操作符栈*/ else Push1(&optr,c);/*若获取的字符的优先级比操作符栈栈顶元素的优先级高，则直接入栈*/ i+; else if(c=*|c=/|c=%)/*情况三：如果获取的字符表示乘除或者取模*/ int clevel=2;/*表示获取的符号的优先级*/ d=GetTop1(&optr,d); dlevel=SelLeve(d);/*用dlevel表示符号栈栈顶元素的优先级*/ if(d!=#&dlevel=clevel)/*若栈顶的优先级比较高*/ hzn=Pop1(&optr,out);/*将此栈顶元素存入后缀数组中，并出栈*/ n+; hzn=|;/*数与操作符之间用|隔开*/ n+; Push1(&optr,c); else Push1(&optr,c);/*若获取的字符的优先级比操作符栈栈顶元素的优先级高，则直接入栈*/ i+; else if(c=()Push1(&optr,c);i+;/*情况四：获取的是左括号，则直接入符号栈*/ else if(c=)/*情况五：获取的是右括号*/ while(GetTop1(&optr,d)!=()/*如果栈顶的元素不是左括号，则栈内元素一直出栈，并依次存入到后缀数组中，直到栈顶元素为右括号为止*/ hzn=Pop1(&optr,out);/*存入数组，并出栈*/ n+; hzn=|; n+; Pop1(&optr,out);/*左括号出栈*/ i+; while(GetTop1(&optr,d)!=#&!StackEmpty1(&optr)/*将用户输入的表达式全存入数组或者入栈后，如果栈里还有操作符，则依次全部出栈，并依次存入到后缀数组中*/ hzn=Pop1(&optr,out); n+; hzn=|;/*操作符与操作符之间也用|隔开*/ n+; l=n;/*用l表示后缀式的长度(包括|)*/ printf(nhou zhui biao da shi :);/*打印后缀表达式*/ for(j=0;j=48&c=57|c=.)/*转换数的类型并将数入栈*/ zhhm=c; m+; if(hzi+1=|) zhhm=0; shu=atof(zhh);/*将字符串转换成浮点数*/ memset(zhh,0,sizeof(zhh);/*将字符串清空*/ m=0;/* m 初始化为0*/ Push2(&opnd,shu);/*将数入栈*/ i+; else i+; else/*如果从后缀表达式中得到的是操作符，则计算*/ num1=Pop2(&opnd,d);num2=Pop2(&opnd,d); b=Fenlei(num1,num2,c);/*调用函数计算*/ Push2(&opnd,b);/*将计算出的结果入操作数栈*/ i+; else if(hzi=|) i+;/*如果从后缀表达式中得到的是|，则直接丢弃*/ result=Pop2(&opnd,d); printf(n