每日一题---有效的括号问题
文章目录
- 前言
- 1.题目以及分析
- 2.参考代码
前言
前面我们学习了栈的相关操作，现在我们做一道题，进行巩固
Leetcode—有效的括号
1.题目以及分析
这道题就可以使用栈进行操作，因为把最左边的括号当成栈底，最右边的是栈顶，其中每种左括号(例如{，（，[ )），进行入栈，把右括号（例如( }，），] )）这些跟前面的括号进行匹配，如果没有匹配上，那就是false。
最后，判断时候有多余的括号，然后再返回。
2.参考代码
typedef struct Stack{char*arr;int top;int capacity;
}Stack;
void StackInit(Stack *ps){ps->arr=NULL;ps->top=ps->capacity=0;
}
void StackDestory(Stack*ps){free(ps->arr);ps->arr=NULL;ps->top=ps->capacity=0;
}
void StackPush(Stack *ps,char x){if(ps->capacity==ps->top){int newCapacity=ps->capacity==0?4:2*ps->capacity*sizeof(int);char*tmp=(char*)realloc(ps->arr,newCapacity*sizeof(char));ps->arr=tmp;ps->capacity=newCapacity;}ps->arr[ps->top]=x;ps->top++;
}
bool StackEmpty(Stack*ps){return ps->top==0;
}
void StackPop(Stack*ps){ps->top--;
}
char StackTop(Stack*ps){return ps->arr[ps->top-1];
}
bool isValid(char* s) {Stack sk;StackInit(&sk);while(*s){if(*s=='['||*s=='{'||*s=='('){StackPush(&sk,*s);}else{if(StackEmpty(&sk)){StackDestory(&sk);return false;}char top=StackTop(&sk);StackPop(&sk);if((top=='{'&&*s!='}')||(top=='['&&*s!=']')||(top=='('&&*s!=')')){StackDestory(&sk);return false;}}s++;}bool ret=StackEmpty(&sk);StackDestory(&sk);return ret;
}