typedef char STDataType;
//动态栈
#define allocator_may_return_null 1

typedef struct ST {
    STDataType* _a;
    int _top;//栈顶元素
    int _capacity;//最大容量
}Stack;
//初始化栈
void StackInit(Stack *pst);

//入栈
void StackPush(Stack* pst, STDataType x);

//出栈
void StackPop(Stack* pst);

//获取栈顶元素
STDataType StackTop(Stack* pst);


//判断栈是否为空，是返回1，非空返回0
bool StackEmpty(Stack* pst);

//打印栈
void StackPrint(Stack* pst);

//销毁栈
void StackDestory(Stack* pst);



//初始化栈
void StackInit(Stack* pst)
{
	assert(pst);
	pst->_a = NULL;
	pst->_top = 0;
	pst->_capacity = 0;
}
//入栈
void StackPush(Stack* pst, STDataType x)
{
	assert(pst);
	if (pst->_top == pst->_capacity)
	{
		int newcapacity = pst->_capacity == 0 ? 4 : (pst->_capacity * 2);
		STDataType* temp = (STDataType*)realloc(pst->_a, sizeof(STDataType) * newcapacity);
		if (temp == NULL)
		{
			printf("realloc fail\n");
			exit(1);
		}
		pst->_a = temp;
		pst->_capacity = newcapacity;
	}
	pst->_a[pst->_top] = x;
	pst->_top++;
}


//出栈
void StackPop(Stack* pst)
{
	assert(pst);
	assert(pst->_top > 0);
	pst->_top--;
}

//获取栈顶元素
STDataType StackTop(Stack* pst)
{
	assert(pst);
	assert(pst->_top>0);
	return pst->_a[pst->_top-1];
}

//获取栈的有效元素个数
int StackSize(Stack* pst)
{
	assert(pst);
	return pst->_top;
}

//判断栈是否为空，是返回1，非空返回0
bool StackEmpty(Stack* pst)
{
	assert(pst);
	if (pst->_top == 0)
		return true;
	else
		return false;
}

//打印栈
void StackPrint(Stack* pst)
{
	while (!StackEmpty(pst))
	{
		printf("%d\n", StackTop(pst));
		StackPop(pst);
	}
}


//销毁栈
void StackDestory(Stack* pst)
{
	assert(pst);
	free(pst->_a);
	pst->_a = NULL;
	pst->_top = pst->_capacity = 0;
}
#include "string.h"
bool isValid(char* s) {
    Stack st;
    StackInit(&st);

    
    int n=strlen(s);
    if(n%2!=0)
    return false;

    

    for(int i=0;i<n;i++,s++){
        switch(*s){
            case '(':
            {
                 StackPush(&st,*s);
            }
            break;
            case '[':
            {
                 StackPush(&st,*s);
            }
            break;
            case '{':
            {
                 StackPush(&st,*s);
            }
            break;
            
            case ')':
            {
                if(st._top==0)
                 return false;
                 char m=StackTop(&st);
                 StackPop(&st);
                 if(m!='(')
                 {
                    return false;
                 }
            }
            break;
            case '}':
            {
                if(st._top==0)
                 return false;
                 char m=StackTop(&st);
                 StackPop(&st);
                 if(m!='{')
                 {
                    return false;
                 }
            }
            break;
            case ']':
            {
                if(st._top==0)
                 return false;
                  char m=StackTop(&st);
                 StackPop(&st);
                 if(m!='[')
                 {
                    return false;
                 }
            }
            break;
        }
    }
        
       if(st._top>0)
        {
            return false;
        }
        
        if(StackEmpty(&st)&&*s!='\0')
        return false;
StackDestory(&st);
    return true;
}