【栈与队列面试题】有效的括号（动图演示）

leetcode20.括号匹配问题

前言：

💥🎈个人主页:Dream_Chaser～ 🎈💥

✨✨刷题专栏:http://t.csdn.cn/UlvTc

⛳⛳本篇内容:力扣上栈与队列的面试OJ题目

leetcode20.括号匹配问题

1.问题描述

2.前提准备

3.问题题解

1.问题描述

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

有效字符串需满足：

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

2.前提准备

栈的实现

#pragma once
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
#include<stdio.h>
typedef int STDataType;
typedef struct Stack
{STDataType* a;int top;//栈顶的位置int capacity;//栈的容量
}ST;void STInit(ST* pst);
void STDestroy(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;//指向栈顶元素的下一个位置pst->capacity = 0;}
void STDestroy(ST* pst)
{assert(pst);free(pst->a);pst->a = NULL;
}void STPush(ST* pst,STDataType x)
{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;//返回的是realloc出来的内存块的地址pst->capacity = newCapacity;//把扩容后的空间大小赋值给栈容量}pst->a[pst->top] = x;//先放值pst->top++;//再++
}void STPop(ST* pst)
{assert(pst);assert(!STEmpty(pst));pst->top--;
}STDataType STTop(ST* pst)
{assert(pst);assert(!STEmpty(pst));return pst->a[pst->top - 1];
}bool STEmpty(ST* pst)//栈为空返回true,不为空返回false
{//assert(pst);//if (pst->top == 0)//{//	return true;//}//else//{//	return false;//}return pst->top == 0;
}int STSize(ST* pst)
{assert(pst);return pst->top;
}

3.问题题解

s指向的是右括号,top存储的是左括号，st（栈顶指针），a（栈底指针）

只要有一次不对应的情况，那么程序直接返回false
字符串遍历结束，若栈不为空，直接返回false
在比较过程中，若遇到栈为空，可是此时字符串未遍历完，直接返回false

第一种情况:左括号多余

第二种情况:括号没有多余，但是类型匹配不上

第三种情况:右括号多余

代码实现：

bool isValid(char * s){ST st;STInit(&st);while(*s)//*s就是输入的那个x的值{//1.左括号入栈if(*s == '(' || *s == '['  || *s == '{'){STPush(&st, *s);    }else{if(STEmpty(&st))//栈为空也需要销毁，因为它malloc了空间，空间在那占用着，只是数据没填进去{STDestroy(&st);return false;}//右括号出栈匹配char top=STTop(&st);STPop(&st);//只要有一个不匹配，直接返回false//左括号和右括号相等说明不了问题，只能说明这一次，这一对括号匹配，还有其它括号不匹配的//所以要找到不继续的条件if((*s == ']' && top!= '[')||(*s == ')'&& top !='(')||(*s=='}' && top!='{')){STDestroy(&st);return false;}}++s;//字符指针的移动}bool ret=STEmpty(&st);//栈不为空那就是falseSTDestroy(&st);return ret;
}

代码执行：