【数据结构】之栈的应用——有效的括号

有效的括号

原题链接：有效的括号


详解栈的链接
这道题可以利用栈来解决

1.左括号入栈
2.右括号与出栈顶左括号匹配

//创建一个动态的栈
typedef char STDateType;
typedef struct Stack
{
	STDateType* a;//储存指定数据类型的数组
	int top;//栈顶
	int capacity;//栈的容量
}ST;

//栈的初始化和销毁
void STInit(ST* pst);
void STDestroy(ST* pst);

//入栈和出栈
void STPush(ST* pst, STDateType x);
void STPop(ST* pst);

//返回栈顶数据
STDateType STTop(ST* pst);

//判空
bool STEmpty(ST* pst);

//栈数据个数
int STSize(ST* pst);

//栈的初始化
void STInit(ST* pst)
{
	assert(pst);
	pst->a = NULL;
	//指向栈顶元素的下一个位置
	pst->top = 0;

	//指向栈顶元素
	//pst->top = -1;

	pst->capacity = 0;
}

//栈的销毁
void STDestroy(ST* pst)
{
	assert(pst);
	free(pst->a);
	pst->a = NULL;
	pst->top = 0;
	pst->capacity = 0;
}

//入栈
void STPush(ST* pst, STDateType x)
{
	assert(pst);
	//如果容量不够,需要扩容
	if (pst->top == pst->capacity)
	{
		int newcapacity = pst->capacity == 0 ? 4 : 2 * pst->capacity;
		STDateType* tmp = (STDateType*)realloc(pst->a, newcapacity * sizeof(ST));
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		pst->a = tmp;
		pst->capacity = newcapacity;
	}
	//储存数据
	pst->a[pst->top++] = x;
}

//出栈
void STPop(ST* pst)
{
	assert(pst);
	assert(pst->top > 0);
	pst->top--;
}

//返回栈顶数据
STDateType STTop(ST* pst)
{
	assert(pst);
	assert(pst->top > 0);
	return pst->a[pst->top - 1];
}

//判空
bool STEmpty(ST* pst)
{
	assert(pst);
	return pst->top == 0;
}

//栈数据个数
int STSize(ST* pst)
{
	assert(pst);
	return pst->top;
}

bool isValid(char* s)
{
    //定义一个栈
    ST st;
    STInit(&st);
    while(*s)
    {
        //左括号入栈
        if(*s == '(' || *s == '[' || *s == '{')
        {
            STPush(&st,*s);
        }
        //右括号与出栈的左括号匹配
        else
        {
            if(STSize(&st) == 0)
            {
                STDestroy(&st);
                return false;
            }
            char top = STTop(&st);
            STPop(&st);
            if((top == '(' && *s != ')') ||( top == '[' && *s != ']') || (top == '{' && *s != '}'))
            {
                STDestroy(&st);
                return false;
            }
        }
        s++;
    }
    //出循环后有两种情况：
    //左括号 == 右括号    
    //左括号的数量多于右括号的数量
    bool ret = STEmpty(&st);
    STDestroy(&st);
    return ret;

}