Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Note that an empty string is also considered valid.

bool isValid(char* s) 
{
    int sLen=strlen(s);
    if(sLen%2!=0)
    {
        return false;
    }
    int *map=(int *)malloc(sizeof(int)*(sLen/2+1));
    int a[126]={0};
    a['(']=1;
    a['[']=1;
    a['{']=1;
    a[')']='(';
    a[']']='[';
    a['}']='{';
    int count=0;
    for(int i=0;i<sLen;i++)
    {
        if(a[s[i]]==1) 
        {
            map[count++]=s[i];
        }
        else
        {
            if(count!=0 && a[s[i]]==map[count-1])
            {
                count--;
            }
            else
            {
                return false;
            }
        }
        
        if(count>sLen/2)
        {
            return false;
        }
    }
    
    if(count!=0)
    {
        return false;
    }
    
    return true;
}

C语言中自己实现栈,相应的解决方案:

/*定义栈的初始大小*/
#define STACK_INITSIZE   100
/*定义增幅*/
#define STACK_INCREMENT  100
typedef int ElemType;

int realsize = STACK_INITSIZE;
/*顺序栈的实现*/
typedef struct SqStack
{
    /*指向申请的内存,用于存储栈数据结构*/
    ElemType *data;
    int top;
}SqStack;

/*栈的初始化*/
int initstack(SqStack * s)
{
    /*入参为NULL,返错*/
    if(NULL == s)
        return -1;
    s->top = -1;
    s->data = (ElemType *)malloc(STACK_INITSIZE * sizeof(ElemType));
    /*申请内存失败,返错*/
    if(NULL == s->data)
        return -1;
    
    return 0;
}

/*判断栈空*/
bool stackempty(SqStack *s)
{
    if(NULL == s)
        return true;
    
    if(-1 == s->top)
        return true;
    else
        return false;
}

/*入栈操作*/
int push(SqStack *s,ElemType x)
{
    if(NULL == s)
        return -1;
    
    /*栈满,再分配STACK_INCREMENT个元素*/
    if(realsize-1 == s->top)
    {
        realsize += STACK_INCREMENT;
        s->data = (ElemType *)realloc(s->data,realsize*sizeof(ElemType));
        /*申请内存失败,返错*/
        if(NULL == s->data)
            return -1;
    }
    
    s->top += 1;
    s->data[s->top] = x;
    
    return 0;
}
/*出栈操作*/
int pop(SqStack *s,ElemType *x)
{
    if(NULL == s)
        return false;
    
    if(stackempty(s))
        return -1;
    
    *x = s->data[s->top];
    s->top--;
    return 0;
}
/*获取栈顶元素*/
int gettop(SqStack *s,ElemType *x)
{
    if(stackempty(s))
        return -1;
    *x = s->data[s->top];
    return *x;
}
/*清空栈,只是将top设置为-1,没有释放申请的内存*/
void clearstack(SqStack *s)
{
    if(stackempty(s))
        return;
    s->top = -1;
}
void destorystack(SqStack *s)
{
    if(NULL == s)
        return;
    
    if(s->data != NULL)
        free(s->data);
    s->top = -1;
}

bool isValid(char* s) 
{
    /*申请栈*/
    SqStack stack;
    initstack(&stack);
    
    int ele = 0;
    int len = strlen(s);
    if(len%2!=0)
    {
        return false;
    }
    for(int i=0;i<len;i++)
    {
        if(s[i]=='(' || s[i]=='[' ||s[i]=='{')
        {
            push(&stack,s[i]);
        }
        else if(s[i]==')')
        {
            if(gettop(&stack,&ele) != '(')
                return false;
            else
                pop(&stack,&ele);
        }
        else if(s[i]==']')
        {
            if(gettop(&stack,&ele) != '[')
                return false;
            else
                pop(&stack,&ele);
        }
        else if(s[i]=='}')
        {
            if(gettop(&stack,&ele) != '{')
                return false;
            else
                pop(&stack,&ele);
        }
        else
        {
            return false;
        }
            
    }

    int ret = stackempty(&stack);
    destorystack(&stack);
    return ret;
}

相应的栈实现参考之前文章中的实现:栈操作C语言实现