栈及其应用-表达式求值.doc

《栈及其应用-表达式求值.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、#include#include#include#include#include#include#include#include//函数结果状态代码#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1#defineStack_Init_Size10#defineStackIncrement2//#defineOVERFLOW-1//在math.h中已定义

2、OVERFLOW等于3typedefintStatus;typedefintBoolean;typedefintSElemType;typedefstructsqstack//结构体{SElemType*base;SElemType*top;intstacksize;//栈的大小}SqStack,*PSqStack;StatusInit(SqStack&S){//初始化栈S.base=(SElemType*)malloc(Stack_Init_Size*sizeof(SElemType));if(!S.base)exit(OVERFLOW);//内存分配不足S.top=S.ba

3、se;//栈为空S.stacksize=Stack_Init_Size;returnOK;}StatusDestoryStack(SqStack&S){//销毁栈free(S.base);S.base=NULL;//预防野指针的出现S.top=NULL;//预防野指针的出现S.stacksize=0;returnOK;}StatusStackEmpty(SqStackS){//判断栈是否为空，若空返回TRUE否则返回FALSEif(S.base==S.top)returnTRUE;elsereturnFALSE;}StatusStackClear(SqStack&S){//清空

4、栈S.top=S.base;returnOK;}StatusGetTop(SqStackS,SElemType&e){//若栈不为空，则e返回栈顶元素的值，返回值为OK，否则返回值为ERRORif(S.top==S.base)returnERROR;e=*(S.top-1);returnOK;}StatusPush(SqStack&S,SElemTypee){//入栈操操作,入栈元素为eif(S.top-S.base>=S.stacksize)//栈满了的时候{S.base=(SElemType*)realloc(S.base,(S.stacksize+StackIncreme

5、nt)*sizeof(SElemType));if(!S.base)exit(OVERFLOW);S.top=S.base+S.stacksize;S.stacksize=S.stacksize+StackIncrement;}*(S.top)=e;//栈没满的时候S.top++;returnOK;}StatusPop(SqStack&S,SElemType&e){//若栈不空，则删除栈顶元素，用e返回，返回值为OK，否则返回ERRORif(S.top==S.base)returnERROR;S.top--;//top里面没元素e=*(S.top);}voidStackTrav

6、erse(SqStackS){SElemType*p=S.top-1;//if(S.top==S.base);while(p>=S.base){printf("%d",*p);p--;}}//以上是栈的基本操作//下面的是对表达式的基本操作charPrecede(SElemTypet1,SElemTypet2){//判断t1，t2的优先级('#'代替'')，t1、t2是两个运算符charf;switch(t2){case'+':case'-':if(t1=='('

7、

8、t1=='')f='<';//t1';//t1>t2break;case'*':c

9、ase'/':if(t1=='*'

10、

11、t1=='/'

12、

13、t1==')')f='>';//t1>t2elsef='<';//t1';//t