原题链接:https://leetcode.cn/problems/valid-parentheses/
目录
1. 题目描述
2. 思路分析
3. 代码实现
1. 题目描述
文章来源地址https://www.toymoban.com/news/detail-658003.html
2. 思路分析
这道题目主要考查了栈的特性:
题目的意思主要是要做到3点匹配:类型、顺序、数量。
题目给的例子是比较简单的情况,可能还有如下较为复杂的情况:
循环遍历字符串s中的字符,逐个取到每个括号,如果该括号是:
1. 左括号,入栈
2. 右括号,出栈顶括号,进行匹配。
如果不匹配,直接返回false。否则继续循环。
循环结束后,如果栈空则匹配,否则左括号比右括号多肯定不匹配。
3. 代码实现
typedef char STDataType;
#define INIT_CAPACITY 4
typedef struct Stack
{
STDataType* a;
int top; //栈顶
int capacity; //容量
}ST;
//初始化栈
void STInit(ST* ps);
//入栈
void STPush(ST* ps, STDataType x);
//出栈
void STPop(ST* ps);
//获取栈顶元素
STDataType STTop(ST* ps);
//获取栈中有效元素个数
int STSize(ST* ps);
//检测栈是否为空
bool STEmpty(ST* ps);
//销毁栈
void STDestroy(ST* ps);
void STInit(ST* ps)
{
assert(ps);
ps->a = NULL;
ps->top = 0;
ps->capacity = 0;
}
void STPush(ST* ps, STDataType x)
{
assert(ps);
if (ps->top == ps->capacity)
{
int newCapacity = ps->capacity == 0 ? INIT_CAPACITY : ps->capacity * 2;
STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newCapacity);
if (tmp == NULL)
{
perror("realloc failed");
exit(-1);
}
ps->a = tmp;
ps->capacity = newCapacity;
}
ps->a[ps->top] = x;
ps->top++;
}
void STPop(ST* ps)
{
assert(ps);
//空
assert(ps->a > 0);
--ps->top;
}
STDataType STTop(ST* ps)
{
assert(ps);
//空
assert(ps->a > 0);
return ps->a[ps->top - 1];
}
int STSize(ST* ps)
{
assert(ps);
return ps->top;
}
bool STEmpty(ST* ps)
{
assert(ps);
return ps->top == 0;
}
void STDestroy(ST* ps)
{
assert(ps);
ps->a = NULL;
ps->top = ps->capacity = 0;
}
bool isValid(char * s){
ST st;
STInit(&st);
char topVal;
while(*s)
{
if(*s=='('||*s=='{'||*s=='[')
{
STPush(&st,*s);
}
else
{
if(STEmpty(&st))
{
STDestroy(&st);
return false;
}
topVal=STTop(&st);
if(*s==')'&&topVal!='('
||*s=='}'&&topVal!='{'
||*s==']'&&topVal!='[')
{
STDestroy(&st);
return false;
}
else
{
STPop(&st);
}
}
++s;
}
bool ret=STEmpty(&st);
STDestroy(&st);
return ret;
}
文章来源:https://www.toymoban.com/news/detail-658003.html
到了这里,关于【数据结构OJ题】有效的括号的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!