【数据结构与算法 经典例题】括号匹配问题

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

// 支持动态增长的栈
typedef char STDataType;//对数据类型重命名，方便后期修改类型
typedef struct Stack
{
	STDataType* a;
	int top;		// 栈顶
	int capacity;  // 容量 
}Stack;//定义结构同时重命名

// 初始化栈 
void StackInit(Stack* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->top = ps->capacity = 0;
}

// 入栈 
void StackPush(Stack* ps, STDataType data)
{
	assert(ps);
	//判断是否需要扩容
	if (ps->top == ps->capacity)
	{
		int newcapa = ps->capacity == 0 ? 4 : 2 * (ps->capacity);
		STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newcapa);
		if (tmp == NULL)
		{
			perror("realloc\n");
			exit(1);
		}
		ps->a = tmp;
		ps->capacity = newcapa;
	}
	//确定空间足够之后再插入数据
	ps->a[ps->top] = data;
	ps->top++;
}

// 出栈 
void StackPop(Stack* ps)
{
	assert(ps);
	assert(ps->top);

	ps->top--;
}

// 获取栈顶元素 
STDataType StackTop(Stack* ps)
{
	assert(ps);
	assert(ps->top);
	return ps->a[ps->top-1];
}

// 获取栈中有效元素个数 
int StackSize(Stack* ps)
{
	assert(ps);

	return ps->top;
}

// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
int StackEmpty(Stack* ps)
{
	assert(ps);

	return ps->top == 0;
}

// 销毁栈 
void StackDestroy(Stack* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->top = ps->capacity = 0;
}

//括号匹配问题
bool isValid(char* s)
{
	Stack st;
	StackInit(&st);//创建一个栈的结构体变量
	char* p = s;
	while (*p)
	{
		if (*p == '(' || *p == '[' || *p == '{')//左括号入栈
		{
			StackPush(&st,*p);
		}
		if (*p == ')' || *p == ']' || *p == '}')//右括号进行判断
		{
			if (StackEmpty(&st))//此时栈空，可直接判定false
			{
				StackDestroy(&st);
				return false;
			}
			else
			{
				char tmp = StackTop(&st);
				StackPop(&st);//栈顶元素出栈
				if ((*p == ')' && tmp != '(' )//判断顺序是否匹配
					|| (*p == ']' && tmp != '[' )
					|| (*p == '}' && tmp != '{'))
					return false;
			}
		}
		p++;
	}
	if (StackEmpty(&st))//判断数量是否匹配
		return true;
	else
		return false;
}