目录
引言
这道题是关于栈的经典面试题,如果大家对栈这个数据结构不是很了解的话,可以先看这篇博客--数据结构之栈的超详细讲解-CSDN博客
题目描述:
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
示例 1：
输入：s = "()" 输出：true
示例 2：
输入：s = "()[]{}"
输出：true
示例 3：
输入：s = "(]" 输出：false
提示：
1 <= s.length <= 104s仅由括号'()[]{}'组成
思路分析:
这是一道很经典的问题,他要求我们对括号进行匹配,这里用其他方法不是很好做,但时用栈这个结构的话,能很轻松的解决.
这里我们写一个很复杂但是匹配的例子,比如[{()}]
我们用栈来存储所有的左括号,用栈顶元素与右括号进行匹配,这里巧妙使用了栈的后进先出的特性,栈顶元素即为最后一个左括号,与最开始的右括号进行匹配,最后当我们的字符数组没有元素时即为匹配成功.
代码展示:
因为这里需要使用栈这个数据结构,我们这里是使用C语言进行编写,没有C++STL容器可以直接使用,所以需要我们手动实现,大家如果还不会的,可以看数据结构之栈的超详细讲解-CSDN博客这篇博客,这里就不再另外进行讲解
代码如下:
//栈的结构 typedef char STDataType; typedef struct Stack { STDataType* a; 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; //top指向栈顶数据 //pst->top = -1; pst->capacity = 0; } void STDestory(ST* pst) { assert(pst); free(pst->a); pst->a = NULL; pst->top = pst->capacity = 0; } //入栈和出栈 void STPush(ST* pst, STDataType x) { assert(pst); //扩容 if (pst->top == pst->capacity) { int newcapcacity = pst->capacity == 0 ? 4 : pst->capacity * 2; STDataType* tmp = (STDataType*)realloc(pst->a, newcapcacity * sizeof(STDataType)); if (tmp == NULL) { perror("realloc fail!"); return; } pst->a = tmp; pst->capacity = newcapcacity; } 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) { assert(pst); return pst->top == 0; } //获取数据个数 int STSize(ST* pst) { assert(pst); return pst->top; }
代码:
//栈的结构
typedef char STDataType;
typedef struct Stack
{
STDataType* a;
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;
//top指向栈顶数据
//pst->top = -1;
pst->capacity = 0;
}
void STDestory(ST* pst)
{
assert(pst);
free(pst->a);
pst->a = NULL;
pst->top = pst->capacity = 0;
}
//入栈和出栈
void STPush(ST* pst, STDataType x)
{
assert(pst);
//扩容
if (pst->top == pst->capacity)
{
int newcapcacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
STDataType* tmp = (STDataType*)realloc(pst->a, newcapcacity * sizeof(STDataType));
if (tmp == NULL)
{
perror("realloc fail!");
return;
}
pst->a = tmp;
pst->capacity = newcapcacity;
}
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)
{
assert(pst);
return pst->top == 0;
}
//获取数据个数
int STSize(ST* pst)
{
assert(pst);
return pst->top;
}
bool isValid(char* s) {
ST st;
STInit(&st);
while(*s)
{
//左括号入栈
if(*s == '(' || *s == '[' || *s == '{')
{
STPush(&st, *s);
}
//右括号取栈顶与左括号尝试匹配
else
{
if(STEmpty(&st))
{
return false;
}
char top = STTop(&st);
STPop(&st);
//不匹配
if(top == '(' && *s != ')'
|| top == '{' && *s != '}'
|| top == '[' && *s != ']')
{
STDestory(&st);
return false;
}
}
++s;
}
//如果栈不为空,说明左括号必右括号多
bool ret = STEmpty(&st);
STDestory(&st);
return ret;
}我们重点看后面这个函数,我们先定义栈这个结构,然后进行初始化,当字符数组中有元素时,就进行循环,如果这个字符等于左括号时,将它入栈,否则取栈顶元素与第一个不为左括号的元素进行匹配,如果不匹配直接返回false,注意: 此时返回false时,要销毁我们的栈空间,否则会造成空间浪费.如果匹配成功,字符往下移动,进入下一轮匹配.
注意:
这里最后一定要进行判空处理
力扣中有这样一个例子: S = "{",字符数组中只有一个左括号,我们循环将它入栈后,直接结束,循环过程没有匹配失败,但这并不代表它是匹配的,所以最后进行判空处理,并销毁栈空间.