?思路:Step1:如果是左括号,入栈
? ? ? ? ? Step2:如果是右括号,就出栈顶的元素与右括号进行比对,如果匹配,继续,直到都匹配成功结束。否则退出,直接返回false.
栗子:1.? {[()]}? ? ? 左括号? '{' '[' '('? 入栈后与栈顶的右括号 )')'? ']' '}' 依次进行匹配,结果发现匹配,返回true.
2.? [(]}? ? 左括号 '['? '('? 入栈,遇到右括号 ']' 与栈顶的左括号 '('? ?匹配,匹配不上,返回false.
注意:无论匹配或者不匹配,都要摧毁栈,防止内泄漏
用c语言实现栈,没法直接引用,这里需要自己创建一个栈,在完成上述操作。如果还不会栈的小伙伴可以看看我的这篇博客?【数据结构】栈【详解】?? ? ? ? ??-CSDN博客
?
typedef int STDataType;
typedef struct Stack//栈的声明与定义
{
STDataType* a;//定义一个指针,用于后续存储空间
int top;
int capacity;
}ST;
//初始化栈
void StackInit(ST* ps)
{
assert(ps);//为初始化的栈开辟一个空间
ps->a = (STDataType*)malloc(sizeof(STDataType) * 4);
if (ps->a == NULL)
{
printf("malloc fail\n");
exit(-1);
}
//同时让其容量为当前栈开辟的空间
ps->capacity = 4;
ps->top = 0;
}
//摧毁栈
void StackDestory(ST* ps)
{
assert(ps);
free(ps->a);
ps->a = NULL;
ps->top = ps->capacity = 0;
}
// 入栈
void StackPush(ST* ps, STDataType x)
{
assert(ps);
// 满了->增容,每次扩充的容量是当前的二倍
if (ps->top == ps->capacity)
{
STDataType* tmp = (STDataType*)realloc(ps->a, ps->capacity * 2 * sizeof(STDataType));
if (tmp == NULL)
{
printf("realloc fail\n");
exit(-1);
}
else
{//开辟玩空间后,让栈的指针指向这片空间,同时栈的容量增加
ps->a = tmp;
ps->capacity *= 2;
}
}
ps->a[ps->top] = x;
ps->top++;
}
// 出栈
void StackPop(ST* ps)
{
assert(ps);
// 栈空了,调用Pop,直接中止程序报错
assert(ps->top > 0);
//出栈直接让栈顶减一
//ps->a[ps->top - 1] = 0;
ps->top--;
}
//返回栈顶的元素
STDataType StackTop(ST* ps)
{
assert(ps);
// 栈空了,调用Top,直接中止程序报错
assert(ps->top > 0);
return ps->a[ps->top - 1];
}
//返回栈的大小
int StackSize(ST* ps)
{
assert(ps);
return ps->top;
}
?
//测试运行函数
bool isValid(char* s)
{
ST st;
StackInit(&st);
while(*s!='\0')
{ //通过指针来遍历数组,直到终止
//这里判断字符,左括号进栈,右括号出栈
switch(*s)
{
case '{':
case '[':
case '(':
{
StackPush(&st,*s);
++s;
break;//每次进栈就进行下一次循环,同时++s
}
case '}':
case ']':
case ')':
{//如果没有左括号,就说明只有右括号,栈内为空,就直接返回false
//记得要摧毁栈,防止内存泄漏
if(StackEmpty(&st))
{
StackDestory(&st);
return false;
}
//若栈不为空,就 取栈顶元素进行比对
//若为预期对应的右括号,匹配成功,同时++s,移向下一个位置继续匹配
char top=StackTop(&st);
StackPop(&st);
//不匹配就返回flase
if((*s=='}' && top!='{')
|| (*s==']' && top!='[')
|| (*s==')' && top!='('))
{
StackDestory(&st);
return false;
}
else
{
++s;
}
}
default:
break;
}
}
//若当前栈为空,说明已经匹配完成,都匹配,返回true
bool ret=StackEmpty(&st);
StackDestory(&st);
return ret;
}
如代码所示:通过遍历*s,来进行括号的匹配。如果字符是左括号就入栈StackPush,并使*s++。如果只有右括号而没有左括号,说明栈为空,这时直接摧毁栈并返回false。接着依次取栈顶元素与当前右括号匹配,成功就继续,直到最后一个匹配完成(这时判断条件是完成上述操作后StackEmpty是真),返回true,否者返回false。
?
typedef int STDataType; typedef struct Stack//栈的声明与定义 { STDataType* a;//定义一个指针,用于后续存储空间 int top; int capacity; }ST; //初始化栈 void StackInit(ST* ps) { assert(ps);//为初始化的栈开辟一个空间 ps->a = (STDataType*)malloc(sizeof(STDataType) * 4); if (ps->a == NULL) { printf("malloc fail\n"); exit(-1); } //同时让其容量为当前栈开辟的空间 ps->capacity = 4; ps->top = 0; } //摧毁栈 void StackDestory(ST* ps) { assert(ps); free(ps->a); ps->a = NULL; ps->top = ps->capacity = 0; } // 入栈 void StackPush(ST* ps, STDataType x) { assert(ps); // 满了->增容,每次扩充的容量是当前的二倍 if (ps->top == ps->capacity) { STDataType* tmp = (STDataType*)realloc(ps->a, ps->capacity * 2 * sizeof(STDataType)); if (tmp == NULL) { printf("realloc fail\n"); exit(-1); } else {//开辟玩空间后,让栈的指针指向这片空间,同时栈的容量增加 ps->a = tmp; ps->capacity *= 2; } } ps->a[ps->top] = x; ps->top++; } // 出栈 void StackPop(ST* ps) { assert(ps); // 栈空了,调用Pop,直接中止程序报错 assert(ps->top > 0); //出栈直接让栈顶减一 //ps->a[ps->top - 1] = 0; ps->top--; } //返回栈顶的元素 STDataType StackTop(ST* ps) { assert(ps); // 栈空了,调用Top,直接中止程序报错 assert(ps->top > 0); return ps->a[ps->top - 1]; } //返回栈的大小 int StackSize(ST* ps) { assert(ps); return ps->top; } //若为空,返回空栈 bool StackEmpty(ST* ps) { assert(ps); return ps->top == 0; } //测试运行函数 bool isValid(char* s) { ST st; StackInit(&st); while(*s!='\0') { //通过指针来遍历数组,直到终止 //这里判断字符,左括号进栈,右括号出栈 switch(*s) { case '{': case '[': case '(': { StackPush(&st,*s); ++s; break;//每次进栈就进行下一次循环,同时++s } case '}': case ']': case ')': {//如果没有左括号,就说明只有右括号,栈内为空,就直接返回false //记得要摧毁栈,防止内存泄漏 if(StackEmpty(&st)) { StackDestory(&st); return false; } //若栈不为空,就 取栈顶元素进行比对 //若为预期对应的右括号,匹配成功,同时++s,移向下一个位置继续匹配 char top=StackTop(&st); StackPop(&st); //不匹配就返回flase if((*s=='}' && top!='{') || (*s==']' && top!='[') || (*s==')' && top!='(')) { StackDestory(&st); return false; } else { ++s; } } default: break; } } //若当前栈为空,说明已经匹配完成,都匹配,返回true bool ret=StackEmpty(&st); StackDestory(&st); return ret; }
博客到这里也是结束了,喜欢的小伙伴可以点赞加关注支持下博主,这对我真的很重要~~
?