20.有效的括号（附带源码）

目录

一、思路

二、源码

一、思路

左括号入栈，遇到右括号则出栈进行匹配。

1、如果不匹配，false

2、如果匹配完，栈不空，false

3、如果栈空，但是还有右括号，false

二、源码

// 支持动态增长的栈
typedef int STDataType;
typedef struct Stack
{
	STDataType* a;
	int top;		// 栈顶
	int capacity;  // 容量 
}Stack;

// 初始化栈 
void StackInit(Stack* ps);
// 入栈 
void StackPush(Stack* ps, STDataType data);
// 出栈 
void StackPop(Stack* ps);
// 获取栈顶元素 
STDataType StackTop(Stack* ps);
// 获取栈中有效元素个数 
int StackSize(Stack* ps);
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
int StackEmpty(Stack* ps);
// 销毁栈 
void StackDestroy(Stack* ps);
// 初始化栈 
void StackInit(Stack* ps)
{
	STDataType* temp = (STDataType*)malloc(sizeof(STDataType) * 4);
	if (temp == NULL)
	{
		perror("malloc fail \n");
		exit(-1);
	}
	ps->a = temp;
	ps->capacity = 4;
	ps->top = -1;
}
// 入栈 
void StackPush(Stack* ps, STDataType data)
{
	assert(ps);
	if (ps->capacity == ps->top + 1)
	{
		STDataType* temp = (STDataType*)realloc(ps->a, sizeof(STDataType) * ps->capacity * 2);
		if (temp == NULL)
		{
			perror("realloc fail \n");
			exit(-1);
		}
		ps->a = temp;
		ps->capacity *= 2;
	}
	ps->a[ps->top + 1] = data;
	ps->top++;
}
// 出栈 
void StackPop(Stack* ps)
{
	assert(ps);
	if (ps->top == -1)
	{
		return ;
	}
	ps->top--;
}
// 获取栈顶元素 
STDataType StackTop(Stack* ps)
{
	assert(ps);
	if (ps->top == -1)
	{
		return -1;
	}
	return ps->a[ps->top];
}

// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
int StackEmpty(Stack* ps)
{
	assert(ps);
	if (ps->top == -1)
		return 1;
	else
		return 0;
}
// 销毁栈 
void StackDestroy(Stack* ps)
{
	free(ps->a);
	ps->a = NULL;
	ps->capacity = 0;
	ps->top = 0;
	printf("destory success!\n");
}


bool isValid(char* s) {
	Stack st;
	StackInit(&st);
	
	while (*s)
	{
		//左括号入栈
		if (*s == '[' || *s == '{' || *s == '(')
		{
			StackPush(&st,*s);
		}
		else//右括号，出栈比较
		{
			if (StackEmpty(&st))//栈空，右括号数量多
			{
				return false;
			}
			else
			{
				char top = StackTop(&st);
				StackPop(&st);
				if ((top == '[' && *s != ']')
					|| (top == '{' && *s != '}')
					|| (top == '(' && *s != ')'))
				{
					return false;
				}
				
			}
		}
		++s;
	}
	//运行到这里，说明顺序都匹配
	//再进行数量匹配，如果不为空，则左括号多
	int ret = StackEmpty(&st);
	StackDestroy(&st);
	return ret;//空为真，不空为假
}