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;
}
```