括号匹配问题使用c语言用栈实现，算法中左括号和匹配两种情况有问题，求助

#include<stdio.h>
#include<stdlib.h>

#define  Stack_init_size   10
#define  Stackmaxsize   5

#define   status  char
#define   SElemType   char

#define  Ok   1
#define  Error   0

typedef  struct
{    /*建立一个栈的首结点*/
SElemType  * base;
SElemType  * top;
int     stacksize;
}Spstack;

status   Initstack(Spstack *s)
{     /*建立空的栈并返回首地址*/
     s->base=((SElemType*)malloc(Stack_init_size*sizeof(SElemType)));
if(!s->base)
return  Error;
s->top=s->base;
s->stacksize=Stack_init_size;
return  Ok;
}

status  Stackempty(Spstack *s)
{    /*判断栈是否为空*/
if(s->top==s->base)
return  Ok;
else
return  Error;
}

status  Push(Spstack *s,SElemType  e)
{     /*往栈顶插入元素即进栈*/
if(s->top-s->base>=s->stacksize)
{   /*判断是否栈满*/
s->base=((SElemType*)realloc(s->base,(s->stacksize+Stackmaxsize)*sizeof(SElemType)));
   if(!s->base)
    return  Error;
   s->top=s->base+s->stacksize;
   s->stacksize+=Stackmaxsize;
}
*s->top++=e;
return  Ok;
}

status  Pop(Spstack *s,SElemType  *e)
{    /*让栈顶元素依次输出即出栈*/
if(Stackempty(s))
return  Error;
*e=*--s->top;
return  Ok;
}

status  Count(Spstack *s,char  e)
{
Initstack(s);
while((e=getchar())!='\n')
{
switch(e)
{     /*输入得左括号*/
case  '(':
case  '[':
case  '{':
{
Push(s,e);
break;
}
case  ')':
{
if(*--s->top=='('&&(*s->top)!=0)
{
Pop(s,&e);
}
else
printf("右括号多余\n");

break;
}
case  ']':
{
if(*--s->top=='['&&(*s->top)!=0)
{

Pop(s,&e);
}
else
printf("右括号多余\n");

break;
}

case  '}':
{
if(*--s->top=='{'&&(*s->top)!=0)
{

Pop(s,&e);
}
else
printf("右括号多余\n");
break;
}
}
}
if(*s->base==*s->top)
{
printf("括号完全匹配\n");
}

     if(*s->top>0)
     printf("左括号多余\n");
return  Ok;

}

int  main()
{
char e;
Spstack  s;
printf("输入你要输入的括号\n");
Count(&s,e);
return  0;
}

5 个解决方案

#1

本帖最后由 thefirstz 于 2012-10-17 13:55:43 编辑

你的匹配函数有问题。没有考虑如果左右不匹配或者先输入右括号的情况。如下修改了你的代码，加上了比较括号是否是同一类的方法。以及如果是先输入右括号，则栈为空的可能性。

#include<stdio.h>
#include<stdlib.h>

#define Stack_init_size 10
#define Stackmaxsize 5

#define status char
#define SElemType char

#define Ok 1
#define Error 0
#define Err 2

typedef struct
{ /*建立一个栈的首结点*/
 SElemType * base;
 SElemType * top;
 int stacksize;
}Spstack;

status Initstack(Spstack *s)
{ /*建立空的栈并返回首地址*/
   s->base=((SElemType*)malloc(Stack_init_size*sizeof(SElemType)));
 if(!s->base)
 return Error;
 s->top=s->base;
 s->stacksize=Stack_init_size;
 return Ok;
}

status Stackempty(Spstack *s)
{ /*判断栈是否为空*/
 if(s->top==s->base)
return Ok;
 else
return Error;
}

status Push(Spstack *s,SElemType e)
{ /*往栈顶插入元素即进栈*/
 if(s->top-s->base>=s->stacksize)
 { /*判断是否栈满*/
s->base=((SElemType*)realloc(s->base,(s->stacksize+Stackmaxsize)*sizeof(SElemType)));
 if(!s->base)
 return Error;
 s->stacksize+=Stackmaxsize;
 s->top=s->base+s->stacksize;
 }
 *s->top++=e;
 return Ok;
}

status Pop(Spstack *s,SElemType *e)
{ /*让栈顶元素依次输出即出栈*/
 if(Stackempty(s))
 return Error;
  *e=*(--s->top);
 return Ok;
}
status Comp(char a,char b)
{
    if((a=='('&&b!=')')||(a=='['&&b!=']')||(a=='{'&&b!='}'))

    {
        printf("左右括号不匹配\n");
        return Error;
    }
       else return Ok;
}

status Count(Spstack *s)
{
    char e[Stack_init_size];
    char e1;
      int i=0;
     Initstack(&s);
     gets(e);
     for(i=0;e[i]!='\0';i++)
     {

         switch(e[i])
           { /*输入得左括号*/
              case '(':
              case '[':
              case '{':
             {
                Push(&s,e[i]);
                break;
              }
            case ')':
            case ']':
            case '}':
            {
              if(Stackempty(&s))
                {
                   printf("右括号多余\n");
                  exit(Error);
                }
               else Pop(&s,&e1);

                 if (Comp(e1,e[i]));

                else{
                    printf("左右匹配出错\n");
                   exit(Error);
                    }


                    }
                }

               }
          if(!Stackempty(&s))
            printf("左括号多余\n");

           else printf("匹配正确\n");

}

int main()
{

  Spstack s;
  Count(&s);
 return 0;
  }

#2

谢谢，看明白了，多谢啊

#3

将1楼代码略改进：

#include<stdio.h>
#include<malloc.h>
#include<string.h>
#define STACK_INIT_SIZE 10
#define STACK_GROW_SIZE 5
#define ELEMTYPE char
#define OK 1
#define ERROR 0
typedef struct { /*建立一个栈的首结点*/
    ELEMTYPE * base;
    ELEMTYPE * top;
    int stacksize;
} SpStack;
int InitStack(SpStack *s) { /*建立空的栈并返回首地址*/
    s->base=((ELEMTYPE*)malloc(STACK_INIT_SIZE*sizeof(ELEMTYPE)));
    if (!s->base) return ERROR;
    s->top=s->base;
    s->stacksize=STACK_INIT_SIZE;
    return OK;
}
int StackEmpty(SpStack *s) { /*判断栈是否为空*/
    if (s->top==s->base) return OK;
    else                 return ERROR;
}
int Push(SpStack *s,ELEMTYPE e) { /*往栈顶插入元素即进栈*/
    if (s->top-s->base>=s->stacksize) { /*判断是否栈满*/
        s->base=((ELEMTYPE*)realloc(s->base,(s->stacksize+STACK_GROW_SIZE)*sizeof(ELEMTYPE)));
        if (!s->base) return ERROR;
        s->stacksize+=STACK_GROW_SIZE;
        s->top=s->base+s->stacksize;
    }
    *s->top++=e;
    return OK;
}
int Pop(SpStack *s,ELEMTYPE *e) { /*让栈顶元素依次输出即出栈*/
    if (StackEmpty(s)) return ERROR;
    *e=*(--s->top);
    return OK;
}
int Comp(ELEMTYPE a,ELEMTYPE b) {
    if ((a=='('&&b!=')')
      ||(a=='['&&b!=']')
      ||(a=='{'&&b!='}')) {
        return ERROR;
    } else return OK;
}
int Count(SpStack *s) {
    ELEMTYPE e[STACK_INIT_SIZE*2];
    ELEMTYPE e1;
    int i;

    InitStack(s);
    fgets(e,STACK_INIT_SIZE*2,stdin);
    if ('\n'==e[strlen(e)-1]) e[strlen(e)-1]=0;
    printf("%s\n",e);
    for (i=0;e[i]!='\0';i++) {
        switch (e[i]) {
        case '(':
        case '[':
        case '{':
            Push(s,e[i]);
            break;
        case ')':
        case ']':
        case '}':
            if (StackEmpty(s)) {
                printf("%*s↖右括号多余\n",i+1,"");
                return(ERROR);
            } else Pop(s,&e1);
            if (!Comp(e1,e[i])) {
                printf("%*s↖左右匹配出错\n",i+1,"");
                return(ERROR);
            }
        }
    }
    if (!StackEmpty(s)) {
        printf("%*s↖左括号多余\n",i,"");
        return(ERROR);
    } else {
        printf("匹配正确\n");
        return(OK);
    }
}
void main() {
    SpStack s;
    Count(&s);
    free(s.base);
}

#4

恩恩，不错啊，谢谢啊

#5

这是我看完后写的，为什么运行不了啊，求大神指教，以及调试了好久了还是不行括号匹配问题使用c语言用栈实现，算法中左括号和匹配两种情况有问题，求助

#include<stdio.h>
#include<stdlib.h>

#define STACKINCREMENT 10
#define OVERFLOW -1
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define SElemType char
#define Status char

typedef struct{
SElemType *base;
SElemType *top;
int stacksize;
}SqStack;/*结构体*/

Status InitStack( SqStack &S)/*创建空栈*/
{
S.base=((SElemType*)malloc(100*sizeof(SElemType)));
if(!S.base)
exit(OVERFLOW);
S.top=S.base;
S.stacksize=100;
return OK;
}

Status Push(SqStack &S,SElemType e){

*S.top++=e;
return OK;}
/*插入数字*/
Status cmp(char n,char m)
    {
        if((n == '('&&m == ']')||(n == '['&&m == ')'))
       {
       printf("no");
          return 0;
   }
        else
        return  1;
    }
Status Pop(SqStack &S,SElemType&e)
{
if(S.top==S.base) return ERROR;
e=*--S.top;
return OK;
}
/* run this program using the console pauser or add your own getch, system("pause") or input loop */

int main(int argc, char *argv[]) {
int n,i,b=0;
char e[9];

printf("输入次数 ");
scanf("%d",&n) ;
for(i=0;i<n;i++){

SqStack S;
InitStack(S);

scanf("%c",&e[b]) ;
Push( S, e[b]);
while(e[b]!='E')
    {  b++;
scanf("%c",&e[b]);
Push( S,e[b]);
  if(!cmp( e[b],*S.top))
  Pop(S,e[b]);
  }
}
return 0;
}

#1