【数据结构】_栈与队列经典算法OJ：有效的括号

目录

1. 题目描述及链接

2. 解题思路

3. 程序

1. 题目描述及链接

1. 题目链接：20. 有效的括号 - 力扣（LeetCode）

2. 题目描述：

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。

2. 解题思路

对于括号匹配，既有数量要求，也有顺序要求。

每一个左括号都必须与最临近的右括号进行匹配；

具体实现思路：

遍历字符串，将左括号入栈，对于右括号则出栈顶的左括号进行匹配；

3. 程序

对于特殊情况的考虑：

主要有两个变量：字符串和栈，考虑遍历中二者其一为空的特殊情况：

1、字符串已遍历完毕，但栈中仍有元素：

说明字符串中左括号比右括号多，则需对栈是否为空进行判断，若栈不为空，即字符串已遍历完毕，仍然有括号不匹配，返回false；

2、遍历字符串已经取到右括号，要进行出栈顶左括号进行匹配，但栈为空：
存在无法匹配的右括号，返回false；

由于C语言没有提供栈，需要手动编写，栈结构与相关方法见下文：

【数据结构】_栈的结构与实现-CSDN博客文章浏览阅读296次，点赞3次，收藏7次。若top表示栈顶元素的下标，则初始化时(栈内无元素)，top=-1，插入时在a[top++]处入栈元素；若top表示栈顶元素的下一个元素的下标，则初始化时top为0，插入时在a[top]处入栈元素。1、若采用数组实现栈，则可将数组头视为栈底，数组尾视为栈顶，出入栈都在数组尾进行操作。3、若采用双链表实现栈，则无论将哪端视为栈底，出栈、入栈等方法的实现都非常方便；1、栈：一种特殊的线性表，只允许在固定的一端插入和删除数据；2、压栈：栈的插入操作叫做进栈、压栈、入栈。3、出栈：栈的删除操作叫做出栈。https://blog.csdn.net/m0_63299495/article/details/145428244完整解题程序如下：

typedef char STDataType;
typedef struct Stack {
	// 动态开辟数组
	STDataType* a;
	// top表示栈顶元素的下一个元素的下标
	int top;
	int capacity;
}ST;
void STInit(ST* pst);
void STDestory(ST* pst);
// 压栈
void STPush(ST* pst,STDataType x);
// 出栈
void STPop(ST* pst);
// 获取栈顶数据
STDataType STTop(ST* pst);
// 判空
bool STEmpty(ST* pst);
// 获取栈元素个数
int STSize(ST* pst);

// 初始化
void STInit(ST* pst) {
	assert(pst);
	pst->a = NULL;
	// top表示栈顶元素的下一个元素的下标
	pst->top = 0;
	// capacity表示栈内元素个数（等价于栈顶元素的下一个元素的下标）
	pst->capacity = 0;
}
// 销毁
void STDestory(ST* pst) {
	assert(pst);
	free(pst->a);
	pst->a = NULL;
	pst->capacity = pst->top = 0;
}
// 压栈
void STPush(ST* pst, STDataType x) {
	assert(pst);
	// 满则扩容
	if (pst->top == pst->capacity) {
		int newCapacity = pst->capacity == 0? 4 : pst->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(pst->a, newCapacity * (sizeof(STDataType)));
		if (tmp == NULL) {
			perror("realloc fail");
			return;
		}
		pst->a = tmp;
		pst->capacity = newCapacity;
	}
	// 入栈数据
	pst->a[pst->top] = x;
	pst->top++;
}
// 出栈
void STPop(ST* pst) {
	assert(pst);
	// 判栈非空
	assert(pst->top>0);
	pst->top--;
}
// 获取栈顶数据
STDataType STTop(ST* pst) {
	assert(pst);
	assert(pst->top>0);
	return pst->a[pst->top - 1];
}
// 判空
bool STEmpty(ST* pst) {
	if (pst->top == 0) {
		return true;
	}
	return false;
	//return pst->top == 0;
}
// 获取栈元素个数
int STSize(ST* pst) {
	assert(pst);
	return pst->top;
}
bool isValid(char* s) {
    ST st;
    STInit(&st);
    while(*s !='\0'){
        // 左括号:入栈
        if(*s == '(' ||*s == '{'||*s == '['){
            STPush(&st,*s);
        }
        else{
            // 右括号:测试匹配
            if(STEmpty(&st)){
                STDestory(&st);
                return false;
            };
            STDataType topEle=STTop(&st);
            STPop(&st);
            if(topEle =='(' && *s !=')'
                || topEle =='{' && *s !='}'
                || topEle =='[' && *s !=']'){
                STDestory(&st);
                return false;
            }
        }
        s++;
    }
    // 处理栈不为空的情况
    bool ret=STEmpty(&st);

    STDestory(&st);
    return ret;
}