数据结构课程设计之表达式求值.doc

学生课程设计题 目： 表达式求值问题 姓名： 赵旺 学 号：124090102042 所在院(系)： 计算机与信息科学学院 专 业： 2012级计算机科学与技术 班 级： (2）班 指导教师： 冯韵 2014年9月24日一问题描述要求对包含加、减、乘、除、括号运算符的任意整型表达式进行求解。二设计思路这个程序的关键是对数字与运算符的判断和运算符优先级的判断，以及出栈的运算。建立两个栈，分别存储数字与运算符，栈1存运算符，栈2存数字。依次读取表达式的字符串，先判断是数字还是运算符，如果是数字不能马上压入栈2，因为可能是大于10的数字，应该继续循环，如果还是数字，则利用计算保存数值，直到指到运算符时停止，将计算后的数字压入栈2。压入运算符之前先将要压入的与栈顶的运算符优先级相比较，如果栈顶是（而当前不是），则不需比较优先级，直接压入；如果栈顶是（，当前是），则抵消（弹出（，指向表达式下一个字符）；若当前的运算符优先级大于栈顶的，则压入；若当前的运算符优先级小于栈內时，弹出栈顶的运算符，同时弹出两组数字，经过运算符的运算后再重新压到栈内。为了方便判断运算结束，在存储运算符之前先将#压入栈1中，在输入表达式时以“#”结束，所以可以以运算符=#并且栈1顶=#来结束运算，弹出栈2的数值，即为表达式求值的最终结果。上述操作的算法步骤：（1） 初始化算符S1,数字栈S2;，将#压入算符栈S1中。（2） 读表达式字符=w。（3） 当栈顶为#并且w也是#时结束；否则循环做下列步骤：（3-1）如果w是数字，存储到m，再经过计算存储到num中。m=w-0;num=num*pow(10,n)+m;n+;读下一个字符=w，如果是运算符，则跳出循环；转3-2。（3-2）w若是运算符，则：（3-2-1）如果栈顶为（并且w为）则（出栈，读下一个字符=w；转（3）。（3-2-2）如果栈顶为（或者栈顶优先级小于w优先级，则w入栈，读下一个字符=w；转（3）。否则：从算符栈中出栈，并从数字栈中弹出两组数字进行运算，将结果重新压入数字栈，转（3）。2.1数据结构设计前面提到，要用栈存储数据，由于一个数字一个运算符，所以要定义两个不同的栈，栈1的运算符为字符型；栈2的数字为浮点型，以便运算大数字。再给存储的数据个数加个上制。具体结构定义如下：#define MAXSIZE 100typedef structchar dataMAXSIZE; /*字符型，存储运算符*/int top;charSeqStack,*charPSeqStack;typedef structdouble dataMAXSIZE; /*浮点型，存储数字*/int top;SeqStack,*PSeqStack;2.2功能函数设计（1）判断操作数的函数isnum()判断当前所指字符是否属于数字，是就返回1，不是返回0。（2）求运算符优先级函数priority()为了方便判断运算符优先级，先利用switch函数将不同的运算符返回不同的整型数字，再根据数字的大小判断优先级。+、-优先级相同，返回相同数字，*、/也是。（3）表达式求值函数infix_value()此函数是直接按照设计思路完成问题要求的函数，其中要调用到判断操作符的函数isnum()和求运算符优先级的函数priority()。循环结束弹出栈2的数值，并返回。（4） 主函数main()定义一个数组存储表达式整个字符串，将返回的数值直接赋到浮点型的result，输出result。（5） 两个栈的函数设计：栈的初始化函数charInit_SeqStack()Init_SeqStack() 判栈空 Empty_SeqStack()charEmpty_SeqStack()入栈函数 Push_SeqStack()charPush_SeqStack()出栈函数 Pop_SeqStack()charPop_SeqStack()取栈顶函数 GetTop_SeqStack() charGetTop_SeqStack()销毁栈 Destroy_SeqStack()charDestroy_SeqStack()三.程序代码#include#include#include#define MAXSIZE 100typedef structdouble dataMAXSIZE;int top;SeqStack,*PSeqStack;typedef structchar dataMAXSIZE;int top;charSeqStack,*charPSeqStack; /*定义栈，两个不同的存储类型*/ PSeqStack Init_SeqStack(void)PSeqStack S;S=(PSeqStack)malloc(sizeof(SeqStack);if(S)S-top=-1;return S;charPSeqStack charInit_SeqStack(void)charPSeqStack S;S=(charPSeqStack)malloc(sizeof(charSeqStack);if(S)S-top=-1;return S; /*栈的初始化函数*/int Empty_SeqStack(PSeqStack S)if(S-top=-1)return 1;elsereturn 0;int charEmpty_SeqStack(charPSeqStack S)if(S-top=-1)return 1;elsereturn 0; /*判断栈空函数*/int Push_SeqStack(PSeqStack S,double x)if(S-top=MAXSIZE-1)return 0;elseS-top+;S-dataS-top=x;return 1;int charPush_SeqStack(charPSeqStack S,char x)if(S-top=MAXSIZE-1)return 0;elseS-top+;S-dataS-top=x;return 1; /*入栈函数*/int Pop_SeqStack(PSeqStack S,double *x)if(Empty_SeqStack(S)return 0;else*x=S-dataS-top;S-top-;return 1;int charPop_SeqStack(charPSeqStack S,char *x)if(charEmpty_SeqStack(S)return 0;else*x=S-dataS-top;S-top-;return 1; /*出栈函数*/int GetTop_SeqStack(PSeqStack S,double *x)if(Empty_SeqStack(S)return 0;else*x=S-dataS-top;return 1;int charGetTop_SeqStack(charPSeqStack S,char *x)if(charEmpty_SeqStack(S)return 0;else*x=S-dataS-top;return 1; /*取栈顶函数*/void Destroy_SeqStack(PSeqStack *S)if(*S)free(*S);*S=NULL;return;void charDestroy_SeqStack(charPSeqStack *S)if(*S)free(*S);*S=NULL;return; /*销毁栈*/int isnum(char c) /*判断字符是否为操作符*/if(c=0&c=9)return 1;else return 0; int priority(char op) /*求运算符的优先级*/switch(op)case=:return 1;case):return 2;case+:case-:return 3;case*:case/:return 4;case(:return 5;default:return 0;double infix_value(char *infix) /*表达式求值函数，infix为表达式字符串*/charPSeqStack S1;PSeqStack S2; /*S1为算符栈，S2为数字栈*/char c,w,tope;double n,num,m,result,s1,s2;S2=Init_SeqStack();S1=charInit_SeqStack(); /*初始化栈*/if(!S1)printf(栈初始化失败);return 0;if(!S2)printf(栈初始化失败);return 0;charPush_SeqStack(S1,#); /*先将#压入算符栈，便于判断结束*/w=*infix; /*读表达式字符*/while(charGetTop_SeqStack(S1,&c),c)!=#|w!=#)num=n=0;while(isnum(w) m=w-0;num=num*pow(10,n)+m; /*求出正确的数字*/w=*(+infix);n+; /*n要不断自加*/if(n!=0)Push_SeqStack(S2,num); /*若读过数字，则将num值压入数字栈*/if(charGetTop_SeqStack(S1,&c),c)=(&w=)charPop_SeqStack(S1,&tope);w=*(+infix); /*两括号相遇，销毁，读下一个字符*/else if(charGetTop_SeqStack(S1,&c),c)=(|priority(charGetTop_SeqStack(S1,&c),c)priority(w)/*比较运算符*/charPush_SeqStack(S1,w);w=*(+infix); else charPop_SeqStack(S1,&tope);Pop_SeqStack(S2,&s2);Pop_SeqStack(S2,&s1);switch(tope)case+ : num=s1+s2;break;case- : num=s1-s2;break;case* : num=s1*s2;break;case/ : num=s1/s2;break; /*弹出运算符的同时进行运算*/Push_SeqStack(S2,num); /*将运算结果重新压入栈2*/ /*while(charGetTop_SeqStack(S1,&c),c)!=#|w!=#)*/return result;void main()char numberMAXSIZE; /*存储表达式*/double result; /*表达式结果*/gets(number); /*输入表达式*/result=infix_value(number);printf(%lfn,result); /*输出结果*/getch();四.运行与测试五.设计心得表达式求值是当初老师在教栈这个内容时经常提到的问题，并且也在黑板上演示过，所以在设计思想上基本已经有了框架，写起来也就方便多了，