栈的oj题解（有效的括号）

题目链接：有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
3. 每个右括号都有一个对应的相同类型的左括号。

示例 1：

输入：s = "()"
输出：true

示例 2：

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

示例 3：

输入：s = "(]"
输出：false

实现代码：

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdbool.h>
#include<string.h>
#include<assert.h>
#include<stdlib.h>
//栈的实现
typedef char STdatetype;
typedef struct Stack {
	STdatetype* phead;
	int size;
	int capacity;
}ST;
//栈的初始化
void STDInit(ST* tmp) {
	assert(tmp);
	tmp->phead = NULL;
	tmp->capacity = tmp->size = 0;
}
//栈的销毁
void STDdestroy(ST* tmp) {
	assert(tmp);
	free(tmp->phead);
	tmp->phead = NULL;
	tmp->capacity = tmp->size = 0;
}
//判栈是否满
bool IsFull(ST* tmp) {
	if (tmp->size == tmp->capacity) {
		return true;
	}
	return false;
}
//入栈
void push(ST* tmp, STdatetype date) {
	assert(tmp);
	if (IsFull(tmp)) {
		int newcapacity = tmp->capacity == 0 ? 4 : 2 * tmp->capacity;
		STdatetype* ptr = (STdatetype*)realloc(tmp->phead, newcapacity * sizeof(STdatetype));
		if (!ptr) {
			perror("push:relloc");
			return;
		}
		tmp->phead = ptr;
		tmp->capacity = newcapacity;
	}
	tmp->phead[tmp->size++] = date;
}
//出栈
void pop(ST* tmp) {
	assert(tmp);
	if (tmp->size != 0)
		tmp->size--;
	else {
		perror("pop");
	}
}
//实际作用函数
bool isValid(char* s) {
	size_t len = strlen(s);
	if (len % 2) {
		return false;
	}
	ST stack;
	STDInit(&stack);
	for (int i = 0; i < len; i++) {
		if (s[i] == '(' || s[i] == '[' || s[i] == '{') {
			push(&stack, s[i]);
		}
		if (s[i] == ')' || s[i] == ']' || s[i] == '}') {
			if (stack.size == 0) {
				STDdestroy(&stack);
				return false;
			}
			if (stack.phead[stack.size - 1] == '(' && s[i] == ')') {
				pop(&stack);
			}
			else if (stack.phead[stack.size - 1] == '[' && s[i] == ']') {
				pop(&stack);
			}
			else if (stack.phead[stack.size - 1] == '{' && s[i] == '}') {
				pop(&stack);
			}
			else {
				return false;
			}
		}
	}
	if (stack.size == 0) {
		STDdestroy(&stack);
		return true;
	}
	else {
		STDdestroy(&stack);
		return false;
	}
}