力扣（LeetCode) ——有效的括号(C语言）

题目：有效的括号

示例1：

输入： s = “()”
输出： true

示例2：

输入： s = “()[]{}”
输出： true

解题思路：

本题的要求是判断一个括号左右两边是否是对应的。根据这个思路我们可以使用栈的结构来实现遇到左括号就入栈，遇到右括号就判断栈顶的括号是否是相对应的另一半括号，不是就返回false。

最终代码：

typedef char STDataType;

typedef struct Stack
{
	STDataType* a;
	int top;
	int capacity;
}ST;

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

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

//入栈
void STPush(ST* pst, STDataType x)
{
	assert(pst);
	if (pst->capacity == pst->top)
	{
		int newcapacity = pst->top == 0 ? 4 : 2 * pst->capacity;
		STDataType* newnode = (STDataType*)realloc(pst->a, newcapacity * sizeof(STDataType));
		if (newnode == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		pst->a = newnode;
		pst->capacity = newcapacity;
	}
	pst->a[pst->top] = x;
	pst->top++;
}

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

//取栈顶数据
STDataType STTop(ST* pst)
{
	assert(pst && 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(STEmpty(&st))
      		{
        		STDestroy(&st);
        		return false;
     		}
      		char arr = STTop(&st);
      		STPop(&st);
      		if((arr == '(' && *s != ')') || (arr == '[' && *s != ']') || (arr =='{' && *s != '}'))
      		{
        		STDestroy(&st);
        		return false;
      		}
    	}
    	*s++;
    }
    bool ret = STEmpty(&st);
    STDestroy(&st);
    return ret;
}