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

1、用栈实现括号匹配的检验 修改(2008-11-14 19:06:31)标签：c语言编程 turbo c2.0环境实现 栈 括号匹配 it 分类：C语言编程例子数据结构C语言版括号匹配问题是编译程序时经常遇到的问题，用以检测语法是否有错。本文前些天写的用栈实现括号匹配的检验的代码中，其中用了更少变量的代码二有些错误，使得结果总是match，经过修改，现将正确的代码写出，如下#include<stdlib.h>#include<stdio.h>#define OVERFLOW -1#define OK 1#define ERROR 0#define STACK_INIT_S

2、IZE 100#define STACKINCREMENT 10#define NULL 0typedef char SElemType;typedef int Status;typedef structSElemType *base;SElemType *top;int stacksize;SqStack;Status InitStack(SqStack *S)(*S).base=(SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType);if(!(*S).base) exit(OVERFLOW);(*S).top=(*S).base;(*

3、S).stacksize=STACK_INIT_SIZE;return OK;Status DestroyStack(SqStack *S)free(*S).base);(*S).base=NULL;(*S).top=NULL;(*S).stacksize=0;return OK;Status StackEmpty(SqStack *S)if(*S).top=(*S).base) return OK;else return ERROR;Status Push(SqStack *S,SElemType e)if(*S).top-(*S).base>=(*S).stacksize)(*S).

4、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;return OK;Status Pop(SqStack *S,SElemType *e)if(*S).top=(*S).base) return ERROR;*e=*-S->top;return OK;m

5、ain()SqStack S;SElemType elem;char e,a20;int i=0;int flag=1;clrscr();if( InitStack(&S)printf("kongjian yijing zhunbei hao!n"); else printf("there is not enough room!n");printf("input the kuohao (<=20 ge) and press '#' to show the end:n");doscanf("%c&

6、quot;,&e);ai=e;i+;while(e!='#');i=0;e=ai;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;els

7、e flag=0;break;case '': if(!StackEmpty(&S) Pop(&S,&e);if(e!='') flag=0;else flag=0;break;case '':if(!StackEmpty(&S) Pop(&S,&e);if(e!='') flag=0;else flag=0;break;i+;e=ai;if(!StackEmpty(&S) flag=0;if(flag)printf("MATCH!n");else pri

8、ntf("MIS MATCH!n");if(DestroyStack(&S)printf("the stack is already destroyed!n"); else printf("destroy error!n");printf("press any key to continue!n");getch();表达式求值 算符优先法C 语言编程(2008-11-14 19:10:49)标签：if 运算符 表达式 数据结构c语言 turbo c2.0 分类：C语言编程例子数据结构C语言版表达式求值是实现

9、程序设计语言的基本问题之一，也是栈的应用的一个典型例子。设计一个程序，用算符优先法对表达式求值。以字符序列的形式从终端输入语法正确的、不含变量的整数表达式/用栈实现表达式求值 个位数的混合运算#include<stdlib.h>#include<stdio.h>#define OVERFLOW -1#define OK 1#define TRUE 1#define FALSE 0#define ERROR 0#define STACK_INIT_SIZE 100#define STACKINCREMENT 10#define NULL 0typedef char SEl

10、emType;typedef int Status;typedef structSElemType *top;SElemType *base;int stacksize;SqStack;Status InitStack(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;return OK;Status DestroyS

11、tack(SqStack *S)free(*S).base);(*S).base=NULL;(*S).top=NULL; /开辟空间(*S).stacksize=0;return OK;Status StackEmpty(SqStack *S)if(*S).top=(*S).base) return OK;else return ERROR;Status Push(SqStack *S,SElemType e) /插入为新的栈顶元素 if(*S).top-(*S).base>=(*S).stacksize) /栈满追加存储空间 (*S).base=(SElemType *)realloc

12、(*S).base,(*S).stacksize+STACKINCREMENT)*sizeof(SElemType); if(!(*S).base) exit(OVERFLOW); /存储分配失败 (*S).top=(*S).base+(*S).stacksize;(*S).stacksize+=STACKINCREMENT;*S->top+=e;return OK;Status Pop(SqStack *S,SElemType *e)if(*S).top=(*S).base) return ERROR;*e=*-S->top;return OK;int Transfor(char

13、 c) /返回字符c对应优先关系表中的行列号int k;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;return k;char Precede(char c1,char c2) /判断 c1与 c2的位序关系,优先的返回'=',非

14、 '<',其他还有 '='和' ' int i,j;char a77= '>','>','<','<','<','>','>','>','>','<','<','<','>','>','>','>

15、9;,'>','>','<','>','>','>','>','>','>','<','>','>','<','<','<','<','<','=','','>','

16、;>','>','>','','>','>','<','<','<','<','<','','='i=Transfor(c1);j=Transfor(c2);return(aij);Status In(char c,char OP) /判断字符 c 是否算符，是 ok非 errorint i;for(i=0;i<=6;i+)if(c

17、=OPi) return TRUE;return FALSE; /全判定完还没有则返回 falsechar Operate(char a,SElemType theta,char b) /数值计算int z;switch(theta) case '+':z=a+b;break;case '-':z=b-a;break; /被减数先进栈，故交换所取值case '*':z=a*b;break;case '/':z=b/a;break;return z;SElemType GetTop(SqStack *S) /若栈不空,用e 返回栈顶

18、元素和 OK,否则 ERRORSElemType e;if(*S).top=(*S).base) return ERROR;e=*(*S).top-1);return e;main() SElemType c,elem; /运算符SqStack OPTR,OPND; /运算符栈和运算数栈int a,b,thera; /运算数int optag=FALSE;char OP7='+','-','*','/','(',')','#'OPTR.top=NULL;OPTR.base=NULL;

19、OPND.top=NULL;OPND.base=NULL; clrscr();/初始化运算符栈if( InitStack(&OPTR)printf("kongjian OPTR yijing zhunbei hao!n"); else printf("there is not enough room for OPTR!n");/初始化运算数栈Push(&OPTR,'#');if(InitStack(&OPND)printf("kongjian OPND yijing zhunbei hao!n"

20、); else printf("there is not enough room for OPND!n");printf("input the expression_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'

21、Push(&OPND,c);else Push(&OPND,c-'0');optag=TRUE;scanf("%c",&c); /不是运算符则进栈elseif(!optag&&c='-')Push(&OPND,0);switch(Precede(GetTop(&OPTR),c)case '<': /栈顶元素优先权低Push(&OPTR,c);scanf("%c",&c);optag=FALSE;break;case '=&

22、#39;: /脱括号并接受下一个字符Pop(&OPTR,&elem);scanf("%c",&c);optag=FALSE;break;case '>': /退栈并将运算结果入栈Pop(&OPTR,&elem);thera=elem;Pop(&OPND,&elem);a=elem;Pop(&OPND,&elem);b=elem;Push(&OPND,Operate(a,thera,b);break;/switchelem=GetTop(&OPND);printf(&

23、quot;jisuan jiguo wei : %dn",elem);if(DestroyStack(&OPTR)printf("stack optr (yunsuanfuzhan) destroyed!n"); else printf("not destroyed!n");if(DestroyStack(&OPND)printf("stack opnd (caozuoshuzhan) destroyed!n"); else printf("not destroyed!n");printf

24、("press any key to continue:n");getch();实验六：实现串的基本操作（2学时）用堆分配存储表示实现Hstring串类型的最小操作子集的基础上，实现串抽象数据类型的其余基本操作（不使用C语言本身提供的串函数）。代码一如下：#include<stdio.h>#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2typedef int Status;typedef structchar *ch;i

25、nt length;HString;Status StrAssign(HString *t,char *chars)int i,j;char *c;if(t->ch) free(t->ch);for(i=0,c=chars;ci!='0'i+);if(!i) t->ch=NULL;t->length=0; else t->ch=(char *)malloc(i *sizeof(char); if(!(t->ch)exit(OVERFLOW);for(j=0;j<i;j+)t->chj=charsj;t->length=i;r

26、eturn OK;Status DestroyString(HString *s)free(s->ch);s->ch=NULL;s->length=0;return OK;void print(HString T)int i;for(i=0;i<T.length;i+)printf("%c",T.chi);printf("n");int StrLength(HString S)return S.length;Status ClearString(HString *s)if(s->ch) free(s->ch);s-&g

27、t;ch=NULL; s->length=0;return OK;Status Concat(HString *t,HString S1,HString S2)int i;ClearString(t);t->ch=(char *)malloc(S1.length+S2.length) *sizeof(char);if(!(t->ch)exit(OVERFLOW);for(i=0;i<S1.length;i+)t->chi=S1.chi;t->length=S1.length+S2.length;for(i=0;i<t->length;i+)t-&

28、gt;chS1.length+i=S2.chi;return OK;Status SubString(HString *sub,HString S,int pos,int len)int i;if(pos<1|pos>S.length|len<0|len>S.length-pos+1) return ERROR;if(sub->ch) free (sub->ch);if(!len) sub->ch=NULL;sub->length=0; elsesub->ch=(char *)malloc(len *sizeof(char); for(i=

29、0;i<len;i+)sub->chi=S.chpos-1+i;sub->length=len;return OK;int StrCompare(HString S,HString T)int i;for(i=0;i<S.length&&i<T.length;+i)if(S.chi!=T.chi)return S.chi-T.chi;return S.length-T.length;int Index(HString S,HString T,int pos)int i,m,n;HString Sub,*sub=&Sub;Sub.ch=NUL

30、L;if(pos>0)n=StrLength(S);m=StrLength(T);i=pos;while(i<=n-m+1)SubString(sub,S,i,m);if(StrCompare(Sub,T)!=0) +i;else return i;return 0;Status StrInsert(HString *s,int pos,HString T)int i;if(pos<1|pos>s->length+1) return ERROR;if(T.length)s->ch=(char *)realloc(s->ch,(s->length+

31、T.length) *sizeof(char); if(!s->ch) exit(OVERFLOW);for(i=s->length-1;i>=pos-1;-i)s->chi+T.length=s->chi;for(i=0;i<=T.length-1;i+)s->chpos-1+i=T.chi;s->length+=T.length;return OK;Status StrDelete(HString *s,int pos,int len)int i;if(pos<1|pos>s->length) return ERROR;fo

32、r(i=pos+len-1;i<s->length;i+)s->chi-len=s->chi;s->length-=len;return OK;Status Replace(HString *s,HString T,HString V)int i,n,d;n=StrLength(T);dod=Index(*s,T,1);StrDelete(s,d,n);StrInsert(s,d,V);while(Index(*s,T,1);return OK;main()int i;HString S,S1,S2,S3,T,U,V,W,*s;clrscr();S.ch=NULL

33、;S1.ch=NULL;S2.ch=NULL;S3.ch=NULL;T.ch=NULL;U.ch=NULL;V.ch=NULL;W.ch=NULL; s=&S1;StrAssign(s,"THIS IS A BOOK"); s=&S2;StrAssign(s,"ESE ARE");s=&U;StrAssign(s,"XYXYXYXYXYXY"); s=&S;StrAssign(s,"S");s=&W;StrAssign(s,"W");s=&S3;S

34、ubString(s,S1,3,7);s=&V;SubString(s,U,6,3);s=&T;Concat(s,S1,S);Replace(s,S3,S2);s=&U;Replace(s,V,W);printf("S1=");print(S1);printf("T=");print(T);printf("U=");print(U);DestroyString(&S);DestroyString(&S1);DestroyString(&S2);DestroyString(&S3)

35、;DestroyString(&T);DestroyString(&U);DestroyString(&V);DestroyString(&W);getch();代码段二用选择顺序实现用户的需要#include<stdio.h>#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2typedef int Status;typedef structchar *ch;int length;HString;void me

36、nu() clrscr();printf("* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *n");printf("n* StrAssign-1 Destroy-2 Print-3 Concat-4 Substring-5 Replace-6 Quit-7 *n");printf("n* * * * * * * * * * * * * * * * * * * * * * * * * *n"); gotoxy(15,10);printf

37、("Operation: n");gotoxy(1,20);printf("n* * * * * * * * * * * * * * * * * * *n"); printf("n* Enter a operation code:1,2,3,4,5,6,7 *n");printf("n* * * * * * * * * * * * * * *n");gotoxy(26,10);Status StrAssign(HString *t,char *chars)int i,j;char *c;if(*t).ch) fre

38、e(*t).ch);for(i=0,c=chars;ci!='0'i+);if(!i) (*t).ch=NULL;(*t).length=0;else (*t).ch=(char *)malloc(i*sizeof(char);if(!(*t).ch)exit(OVERFLOW);for(j=0;j<i;j+)(*t).chj=charsj;(*t).length=i;return OK;Status DestroyString(HString *p)if(p->ch=NULL)return ERROR;free(p->ch);p->ch=NULL;p-

39、>length=0;return OK;int StrLength(HString S)return S.length;void Print(HString T)int i;if(T.length=0)printf("null string!n");for(i=0;i<=T.length-1;i+)printf("%c",T.chi);printf("n");Status ClearString(HString *p)if(p->ch) free(p->ch);p->ch=NULL;p->lengt

40、h=0;return OK;Status ConCat(HString *t,HString S1,HString S2)int i;ClearString(t);(*t).ch=(char *)malloc(S1.length+S2.length) *sizeof(char); if(!(*t).ch)exit(OVERFLOW);for(i=0;i<S1.length;i+)(*t).chi=S1.chi;(*t).length=S1.length+S2.length;for(i=0;i<(*t).length;i+)(*t).chS1.length+i=S2.chi;retu

41、rn OK;Status SubString(HString *sub,HString S,int pos,int len)int i;if(pos<1|pos>S.length|len<0|len>S.length-pos+1) return ERROR;if(*sub).ch) free (*sub).ch);if(!len) (*sub).ch=NULL;(*sub).length=0;else(*sub).ch=(char *)malloc(len *sizeof(char);for(i=0;i<len;i+)(*sub).chi=S.chpos-1+i;

42、(*sub).length=len;return OK;int StrCompare(HString S,HString T)int i;for(i=0;i<S.length&&i<T.length;+i)if(S.chi!=T.chi)return S.chi-T.chi;return S.length-T.length;int Index(HString S,HString T,int pos)int i,m,n;HString Sub,*sub=&Sub;Sub.ch=NULL;if(pos>0)n=StrLength(S);m=StrLengt

43、h(T);i=pos;while(i<=n-m+1)SubString(sub,S,i,m);if(StrCompare(Sub,T)!=0) +i;else return i;return 0;Status StrInsert(HString *p,int pos,HString T)int i;if(pos<1|pos>p->length+1) return ERROR;if(T.length)p->ch=(char *)realloc(p->ch,(p->length+T.length) *sizeof(char); if(!p->ch)

44、exit(OVERFLOW);for(i=p->length-1;i>=pos-1;-i)p->chi+T.length=p->chi;for(i=0;i<=T.length-1;i+)p->chpos-1+i=T.chi;p->length+=T.length;return OK;Status StrDelete(HString *p,int pos,int len)int i;if(pos<1|pos>p->length) return ERROR;for(i=pos+len-1;i<p->length;i+)p-&g

45、t;chi-len=p->chi;p->length-=len;return OK;Status Replace(HString *p,HString T,HString V)int i,n,d;n=StrLength(T);dod=Index(*p,T,1);StrDelete(p,d,n);StrInsert(p,d,V);while(Index(*p,T,1);return OK;main()int i,ch; int pos,len;HString T,M1,M2,M3,M4,*p;T.ch=NULL;M1.ch=NULL;M2.ch=NULL;M3.ch=NULL;M4.

46、ch=NULL;p=NULL; ch=1;clrscr();while(ch) menu();scanf("%d",&ch);switch(ch)case 1:clrscr();printf("input the mather string(press 'Enter' to shou the end) :n");scanf("%s",p);if(StrAssign(&M1,p) printf("Assign string mather success!n");else printf(

47、"Assign string mather fail!n");printf("input the chile string(press 'Enter' to shou the end) :n");scanf("%s",p);if(StrAssign(&M2,p) printf("Assign string child success!n");else printf("Assign string child fail!n");printf("press any key to continue !n");getch();break;case 2:clrscr();p=&M1;if(DestroyString(p)prin