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

学生课程设计题目：表达式求值问题姓名：赵旺学号：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的数字为浮点型，以便运算大数字。再给存储的数据个数加个上制。具体结构定义如下：#defineMAXSIZE100typedefstruct{chardata[MAXSIZE];/*字符型，存储运算符*/inttop;}charSeqStack,*charPSeqStack;typedefstruct{doubledata[MAXSIZE];/*浮点型，存储数字*/inttop;}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()三.程序代码#includestdio.h#includestdlib.h#includemath.h#defineMAXSIZE100typedefstruct{doubledata[MAXSIZE];inttop;}SeqStack,*PSeqStack;typedefstruct{chardata[MAXSIZE];inttop;}charSeqStack,*charPSeqStack;/*定义栈，两个不同的存储类型*/PSeqStackInit_SeqStack(void){PSeqStackS;S=(PSeqStack)malloc(sizeof(SeqStack));if(S)S-top=-1;returnS;}charPSeqStackcharInit_SeqStack(void){charPSeqStackS;S=(charPSeqStack)malloc(sizeof(charSeqStack));if(S)S-top=-1;returnS;}/*栈的初始化函数*/intEmpty_SeqStack(PSeqStackS){if(S-top==-1)return1;elsereturn0;}intcharEmpty_SeqStack(charPSeqStackS){if(S-top==-1)return1;elsereturn0;}/*判断栈空函数*/intPush_SeqStack(PSeqStackS,doublex){if(S-top==MAXSIZE-1)return0;else{S-top++;S-data[S-top]=x;return1;}}intcharPush_SeqStack(charPSeqStackS,charx){if(S-top==MAXSIZE-1)return0;else{S-top++;S-data[S-top]=x;return1;}}/*入栈函数*/intPop_SeqStack(PSeqStackS,double*x){if(Empty_SeqStack(S))return0;else{*x=S-data[S-top];S-top--;return1;}}intcharPop_SeqStack(charPSeqStackS,char*x){if(charEmpty_SeqStack(S))return0;else{*x=S-data[S-top];S-top--;return1;}}/*出栈函数*/intGetTop_SeqStack(PSeqStackS,double*x){if(Empty_SeqStack(S))return0;else*x=S-data[S-top];return1;}intcharGetTop_SeqStack(charPSeqStackS,char*x){if(charEmpty_SeqStack(S))return0;else*x=S-data[S-top];return1;}/*取栈顶函数*/voidDestroy_SeqStack(PSeqStack*S){if(*S)free(*S);*S=NULL;return;}voidcharDestroy_SeqStack(charPSeqStack*S){if(*S)free(*S);*S=NULL;return;}/*销毁栈*/intisnum(charc)/*判断字符是否为操作符*/{if(c='0'&&c='9')return1;elsereturn0;}intpriority(charop)/*求运算符的优先级*/{switch(op){case'=':return1;case')':return2;case'+':case'-':return3;case'*':case'/':return4;case'(':return5;default:return0;}}doubleinfix_value(char*infix)/*表达式求值函数，infix为表达式字符串*/{charPSeqStackS1;PSeqStackS2;/*S1为算符栈，S2为数字栈*/charc,w,tope;doublen,num,m,result,s1,s2;S2=Init_SeqStack();S1=charInit_SeqStack();/*初始化栈*/if(!S1){printf(栈初始化失败);return0;}if(!S2){printf(栈初始化失败);return0;}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);/*两括号相遇，销毁，读下一个字符*/}elseif((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!='#')*/returnresult;}voidmain(){charnumber[MAXSIZE];/*存储表达式*/doubleresult;/*表达式结果*/gets(number);/*输入表达式*/result=infix_value(number);printf(%lf\n,result);/*输出结果*/getch();}四.运行与测试五.设计心得表达式求值是当初老师在教栈这个内容时经常提到的问题，并且也在黑板上演示过，所以在设计思想上基本已经有了框架，写起来也就方便多了，但依然也有些问题不断的出现。首先就是存运算符和数字的问题了，我不知在入栈和出栈时如何能将它们的类型合理的转化，所以只好定义两个栈，以至于这个程序看起来太“啰嗦”。在运行调试时曾遇见一个大问题，程序读不了10以上的数字，很快便找到了问题所在，在功能函数里，它每读一个数字便直接入栈，下一个若是数字便存在栈的下一个地址内了。于是我以while循环控制它何时入栈，将大数计算好了再入栈。在调试过程中还曾遇见了一个问题，就是出栈运算时将两个数字前后弄反了，应该是后出栈的-‘运算符’-前出栈的。