用栈实现括号匹配的检验-修改

用栈实现括号匹配的检验修改(2008-11-1419:06:31)标签：c语言编程turboc2.0环境实现栈括号匹配it分类：C语言编程例子数据结构C语言版括号匹配问题是编译程序时经常遇到的问题，用以检测语法是否有错。本文前些天写的用栈实现括号匹配的检验的代码中，其中用了更少变量的代码二有些错误，使得结果总是match，经过修改，现将正确的代码写出，如下#includestdlib.h#includestdio.h#defineOVERFLOW-1#defineOK1#defineERROR0#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10#defineNULL0typedefcharSElemType;typedefintStatus;typedefstruct{SElemType*base;SElemType*top;intstacksize;}SqStack;StatusInitStack(SqStack*S){(*S).base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));if(!(*S).base)exit(OVERFLOW);(*S).top=(*S).base;(*S).stacksize=STACK_INIT_SIZE;returnOK;}StatusDestroyStack(SqStack*S){free((*S).base);(*S).base=NULL;(*S).top=NULL;(*S).stacksize=0;returnOK;}StatusStackEmpty(SqStack*S){if((*S).top==(*S).base)returnOK;elsereturnERROR;}StatusPush(SqStack*S,SElemTypee){if((*S).top-(*S).base=(*S).stacksize){(*S).base=(SElemType*)realloc((*S).base,((*S).stacksize+STACKINCREMENT)*sizeof(SElemType));if(!(*S).base)exit(OVERFLOW);(*S).top=(*S).base+(*S).stacksize;(*S).stacksize+=STACKINCREMENT;}*S-top++=e;returnOK;}StatusPop(SqStack*S,SElemType*e){if((*S).top==(*S).base)returnERROR;*e=*--S-top;returnOK;}main(){SqStackS;SElemTypeelem;chare,a[20];inti=0;intflag=1;clrscr();if(InitStack(&S))printf(kongjianyijingzhunbeihao!\n);elseprintf(thereisnotenoughroom!\n);printf(inputthekuohao(=20ge)andpress'#'toshowtheend:\n);do{scanf(%c,&e);a[i]=e;i++;}while(e!='#');i=0;e=a[i];while(e!='#'&&flag){switch(e){case'(':Push(&S,e);break;case'[':Push(&S,e);break;case'{':Push(&S,e);break;case')':if(!StackEmpty(&S)){Pop(&S,&e);if(e!='(')flag=0;}elseflag=0;break;case']':if(!StackEmpty(&S)){Pop(&S,&e);if(e!='[')flag=0;}elseflag=0;break;case'}':if(!StackEmpty(&S)){Pop(&S,&e);if(e!='{')flag=0;}elseflag=0;break;}i++;e=a[i];}if(!StackEmpty(&S))flag=0;if(flag)printf(MATCH!\n);elseprintf(MISMATCH!\n);if(DestroyStack(&S))printf(thestackisalreadydestroyed!\n);elseprintf(destroyerror!\n);printf(pressanykeytocontinue!\n);getch();}表达式求值算符优先法C语言编程(2008-11-1419:10:49)标签：if运算符表达式数据结构c语言turboc2.0分类：C语言编程例子数据结构C语言版表达式求值是实现程序设计语言的基本问题之一，也是栈的应用的一个典型例子。设计一个程序，用算符优先法对表达式求值。以字符序列的形式从终端输入语法正确的、不含变量的整数表达式//用栈实现表达式求值个位数的混合运算#includestdlib.h#includestdio.h#defineOVERFLOW-1#defineOK1#defineTRUE1#defineFALSE0#defineERROR0#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10#defineNULL0typedefcharSElemType;typedefintStatus;typedefstruct{SElemType*top;SElemType*base;intstacksize;}SqStack;StatusInitStack(SqStack*S){(*S).base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));//开辟空间if(!(*S).base)exit(OVERFLOW);//存储分配失败(*S).top=(*S).base;(*S).stacksize=STACK_INIT_SIZE;returnOK;}StatusDestroyStack(SqStack*S){free((*S).base);(*S).base=NULL;(*S).top=NULL;(*S).stacksize=0;returnOK;}StatusStackEmpty(SqStack*S){if((*S).top==(*S).base)returnOK;elsereturnERROR;}StatusPush(SqStack*S,SElemTypee)//插入为新的栈顶元素{if((*S).top-(*S).base=(*S).stacksize)//栈满追加存储空间{(*S).base=(SElemType*)realloc((*S).base,((*S).stacksize+STACKINCREMENT)*sizeof(SElemType));if(!(*S).base)exit(OVERFLOW);//存储分配失败(*S).top=(*S).base+(*S).stacksize;(*S).stacksize+=STACKINCREMENT;}*S-top++=e;returnOK;}StatusPop(SqStack*S,SElemType*e){if((*S).top==(*S).base)returnERROR;*e=*--S-top;returnOK;}intTransfor(charc){//返回字符c对应优先关系表中的行列号intk;switch(c){case'+':k=0;break;case'-':k=1;break;case'*':k=2;break;case'/':k=3;break;case'(':k=4;break;case')':k=5;break;case'#':k=6;break;}returnk;}charPrecede(charc1,charc2){//判断c1与c2的位序关系,优先的返回'=',非'',其他还有'='和''inti,j;chara[7][7]={{'','','','','','',''},{'','','','','','',''},{'','','','','','',''},{'','','','','','',''},{'','','','','','=',''},{'','','','','','',''},{'','','','','','','='}};i=Transfor(c1);j=Transfor(c2);return(a[i][j]);}StatusIn(charc,charOP[]){//判断字符c是否算符，是ok非errorinti;for(i=0;i=6;i++)if(c==OP[i])returnTRUE;returnFALSE;//全判定完还没有则返回false}charOperate(chara,SElemTypetheta,charb){//数值计算intz;switch(theta){case'+':z=a+b;break;case'-':z=b-a;break;//被减数先进栈，故交换所取值case'*':z=a*b;break;case'/':z=b/a;break;}returnz;}SElemTypeGetTop(SqStack*S){//若栈不空,用e返回栈顶元素和OK,否则ERRORSElemTypee;if((*S).top==(*S).base)returnERROR;e=*((*S).top-1);returne;}main(){SElemTypec,elem;//运算符SqStackOPTR,OPND;//运算符栈和运算数栈inta,b,thera;//运算数intoptag=FALSE;charOP[7]={'+','-','*','/','(',')','#'};OPTR.top=NULL;OPTR.base=NULL;OPND.top=NULL;OPND.base=NULL;clrscr();//初始化运算符栈if(InitStack(&OPTR))printf(kongjianOPTRyijingzhunbeihao!\n);elseprintf(thereisnotenoughroomforOPTR!\n);//初始化运算数栈Push(&OPTR,'#');if(InitStack(&OPND))printf(kongjianOPNDyijingzhunbeihao!\n);elseprintf(thereisnotenoughroomforOPND!\n);printf(inputtheexpression_r:\n);scanf(%c,&c);elem=GetTop(&OPND);while(c!='#'||GetTop(&OPTR)!='#'){if(!In(c,OP))//不是运算符则进操作数栈{if(optag){Pop(&OPND,&elem);elem=elem*10+c-'0';Push(&OPND,c);}elsePush(&OPND,c-'0');optag=TRUE;scanf(%c,&c);}//不是运算符则进栈else{if(!optag&&c=='-')Push(&OPND,0);switch(Precede(GetTop(&OPTR),c)){case''://栈顶元素优先权低Push(&OPTR,c);scanf(%c,&c);optag=FALSE;break;case'='://脱括号并接受下一个字符Pop(&OPTR,&elem);scanf(%c,&c);optag=FALSE;bre