C语言用栈检测括号匹配问题,弄了半天没弄好,不知道哪里不对,求大神指导。
#include
#include
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;
typedef char SElemType;
typedef struct
{
SElemType base;
SElemType *top;
int stacksize;
}SqStack;
Status InitStack(SqStack *S)
{
S->base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
S->top=S->base;
S->stacksize=STACK_INIT_SIZE;
return OK;
}
Status StackEmpty(SqStack *S) //判断栈是否为空,若为空返回TURE,否返回FALSE
{
if(S->top!=S->base) return ERROR;
return OK;
}
Status Push(SqStack *S,SElemType e) //插入元素e为新栈顶元素
{
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;
return OK;
}
Status GetTop(SqStack *S,SElemType *e) //栈不空用e返回栈顶元素,并返回OK 否则返回ERROR
{
if(S->top==S->base) return ERROR;
*e=(S->top-1);
return OK;
}
Status Pop(SqStack S,SElemType*e) //栈不空删除S栈顶元素,用e返回其值,并返回OK,否则返回ERROR
{
if(S->top==S->base) return ERROR;
*e=--S->top;
return OK;
}
Status Bracket(SqStack *S,char *str) //检测括号匹配
{
int i=0,flag1=0,flag2;
SElemType e;
while(str[i]!='\0')
{
switch(str[i])
{
case '(':{Push(S,'(');break;}//入栈
case '[':{Push(S,'[');break;}
case '{':{Push(S,'{');break;}
case ')':{ if(GetTop(S,&e)=='(') //是否与栈顶元素相等
Pop(S,&e); //出栈
else
flag1=1;
break;
}
case ']':{ if(GetTop(S,&e)=='[')
Pop(S,&e);
else
flag1=1;
break;
}
case '}':{ if(GetTop(S,&e)=='{')
Pop(S,&e);
else
flag1=1;
break;
}
default: break;
}
if(flag1) break;
i++;
}
flag2=StackEmpty(S); //栈是否为空并将返回值值赋给flag2
if(!flag1 && flag2) printf("括号匹配正确!\n");
else printf("括号匹配失败!\n");
return OK;
}
int main()
{
char a,flag='y';
while(flag=='y')
{
char str[255];
SqStack S;
InitStack(&S);
printf("请输入带括号的表达式:\n");
scanf("%s",str);
scanf("%c",&a);
Bracket(&S,str);
printf("是否要再次输入?(Enter y again):\n ");
scanf("%c",&flag);
printf("\n");
}
printf("close.\n");
}
我已经自己弄明白了。哈哈哈
错误较多,见注释修改:
#include "stdio.h"
#include "stdlib.h"
#include "string.h"
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;
typedef char SElemType;
typedef struct
{
SElemType *base; //修改
SElemType *top;
int stacksize;
}SqStack;
Status InitStack(SqStack *S)
{
S->base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
S->top=S->base;
S->stacksize=STACK_INIT_SIZE;
return OK;
}
Status StackEmpty(SqStack *S) //判断栈是否为空,若为空返回TURE,否返回FALSE
{
if(S->top!=S->base) return ERROR;
return OK;
}
Status Push(SqStack *S,SElemType e) //插入元素e为新栈顶元素
{
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;//修改
return OK;
}
Status GetTop(SqStack *S,SElemType *e) //栈不空用e返回栈顶元素,并返回OK 否则返回ERROR
{
if(S->top==S->base) return ERROR;
*e=*(S->top-1);//修改
return OK;
}
Status Pop(SqStack *S,SElemType*e) //栈不空删除S栈顶元素,用e返回其值,并返回OK,否则返回ERROR
{
if(S->top==S->base) return ERROR;
*e=*(--(S->top));//修改
return OK;
}
Status Bracket(SqStack *S,char *str) //检测括号匹配
{
int i=0,flag1=0,flag2;
SElemType e;
while(str[i]!='\0')
{
switch(str[i])
{
case '(':{Push(S,'(');break;}//入栈
case '[':{Push(S,'[');break;}
case '{':{Push(S,'{');break;}
case ')':
GetTop(S,&e);//修改
if(e=='(') Pop(S,&e); //出栈
else flag1=1;
break;
case ']':
GetTop(S,&e);
if(e=='[') Pop(S,&e); //出栈
else flag1=1;
break;
case '}':
GetTop(S,&e);
if(e=='{') Pop(S,&e); //出栈
else flag1=1;
break;
default: break;
}
if(flag1) break;
i++;
}
flag2=StackEmpty(S); //栈是否为空并将返回值值赋给flag2
if(!flag1 && flag2) printf("括号匹配正确!\n");
else printf("括号匹配失败!\n");
return OK;
}
int main()
{
char a,flag='y';
while(flag=='y')
{
char str[255];
SqStack S;
InitStack(&S);
printf("请输入带括号的表达式:\n");
scanf("%s",str);
scanf("%c",&a);
Bracket(&S,str);
printf("是否要再次输入?(Enter y again):\n ");
scanf("%c",&flag);
printf("\n");
}
printf("close.\n");
}