括号匹配问题

问题描述：

假设表达式中允许包含两种括号：圆括号与方括号，其嵌套的顺序随意。如（【】（））或【（【】【】）】等为正确的匹配：而【（】）或者（【】（）或者（）（））均为错误的匹配。
现要求编写程序，判断输入的一行括号是否是匹配的，如果是匹配的，输出yes，否则输出no。

解题思路：

检验括号是否是匹配的方法可以用“期待的急迫程度”这个概念来描述。例如考虑虾类括号序列：
【（【 】【 】） 】
1 2 3 4 5 6 7 8
当计算机接受了第一个括号后，它期待着与其匹配的第八个括号的出现，然而等来的却是第二个括号，此时第一个括号只能靠边，而迫切等待着与第二个括号匹配的是第七个括号，然而等来的却是第三个，然后第二个再靠边。。。。以此类推。
由此可见，这个过程与栈结构类似。所以，在算法中建立空栈，每次读入一个括号，如果是左括号则入栈，否则出栈，最后通过栈的长度来判断是否匹配。

此次，通过使用两种栈的结构，链栈和顺序栈。

代码实现
//链栈

#include<stdio.h>
#include<malloc.h>

struct StackNode{
char data;
struct StackNode *next;
};

struct LinkStack{
struct StackNode *top;
int length;
};

struct LinkStack * InitStack ();
void Push(struct LinkStack * S,char e);
char  Pop(struct LinkStack *S);

int main()
{
struct LinkStack *S;
    S=InitStack();
int t=1;
char c,temp;
    c=getchar();
while(c!='#')
    {
if (c=='('||c=='[')
       {
           Push(S,c);
       }
else
       {
if(S->length==0)
           {
               t=0;
goto A;//长度为0时且输入的是右括号，此时一定是不匹配的
           }
           temp=Pop(S);
if((temp=='('&&c==')')||(temp=='['&&c==']'))
           {
               ;
           }
else
           {
               t=0;
           }
       }
       A:c=getchar();
    }

if (S->length!=0)//最后链栈的长度不为零说明不匹配
    {
        t=0;
    }

if (t==0)
printf("no");
else
printf("yes");
return 0;
}

struct LinkStack * InitStack ()
{
struct LinkStack *S;
    S=(struct LinkStack *)malloc(sizeof(struct LinkStack));
    S->top=NULL;
    S->length=0;
return S;
}

void Push(struct LinkStack * S,char e)
{
struct StackNode *p;
    p=(struct StackNode*)malloc(sizeof(struct StackNode));
    p->data=e;
    p->next=S->top;
    S->top=p;
    S->length++;
}

char  Pop(struct LinkStack *S)
{
char e;
    e=S->top->data;
struct StackNode *p;
    p=(struct StackNode*)malloc(sizeof(struct StackNode));
    p=S->top;
    S->top=S->top->next;
    S->length--;
free(p);
return e;
}

//顺序栈

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

struct Stack{
char  *base;
char *top;
int stacksize;
};

struct Stack InitStack();
void Push(struct Stack *S,char e);
char  Pop(struct Stack *S);

int main()
{
int t=1;
struct Stack S;
    S=InitStack();
char c,temp;
    c=getchar();
while(c!='#')
    {
if (c=='('||c=='[')
       {
           Push(&S,c);
       }
else
       {
               temp=Pop(&S);
if(((temp=='(')&&(c==')'))||((temp=='[')&&(c==']')))
           {
               ;
           }
else
           {
               t=0;
           }
       }
       c=getchar();
    }
if (S.base!=S.top)//通过栈的长度来判断是否匹配
        t=0;
if (t==0)
        printf("no");
else
        printf("yes");
return 0;
}

struct Stack InitStack()
{
struct Stack S;
    S.base=(char *)malloc(20*sizeof(char));
    S.top=S.base;
    S.stacksize=20;
return S;
}

void Push(struct Stack *S,char e)
{
if (S->top-S->base>=S->stacksize)
    {
        S->base=(char *)realloc(S->base,(S->stacksize+20)*sizeof(char ));
        S->top=S->base+S->stacksize;
        S->stacksize+=20;
    }
   *S->top++=e;
}

char  Pop(struct Stack *S)
{
char e;
    e=*--S->top;
return e;
}