给定一个只包括 '(',')','{','}','[',']' 的字符串 s ,判断字符串是否有效。
左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。
1 <= s.length <= 104
s
仅由括号 '()[]{}'
组成bool isValid(char * s){
//开辟栈
ST st;
StackInit(&st);
char* str=s;
while(*str!='\0')
{
//遇到左括号入栈
if(*str=='('
||*str=='{'
||*str=='[')
{
StackPush(&st,*str);
str++;
}
else
{
//遇到右括号出栈匹配
if(*str=='}'
||*str==']'
||*str==')')
{
//为空栈时
if(StackEmpty(&st))
{
StackDestroy(&st);//注意栈空间销毁(养成好的习惯)
return false;
}
else
{
char tmp=StackTop(&st);//获取栈顶数据
StackPop(&st);//出栈
if((*str==']'&&tmp!='[')
||(*str=='}'&&tmp!='{')
||(*str==')'&&tmp!='('))
{
//匹配失败
StackDestroy(&st);
return false;
}
else
str++;
}
}
}
}
//遍历完时栈还有数据为被出栈
if(StackEmpty(&st))
{
StackDestroy(&st);//结束前先销毁栈
return true;
}
else
{
StackDestroy(&st);
return false;
}
}
//默认栈数据类型
typedef char STDataType;
//栈类型结构
typedef struct Stack
{
//数组栈(指向数组的指针)
STDataType* a;
//栈顶位置
int top;
//栈容量
int capacity;
}ST;
//栈初始化
void StackInit(ST* ps);
//栈销毁
void StackDestroy(ST* ps);
//入栈
void StackPush(ST* ps, STDataType x);
//出栈
void StackPop(ST* ps);
//获取栈顶数据
STDataType StackTop(ST* ps);
//栈使用空间大小
int StackSize(ST* ps);
//是否为空栈
bool StackEmpty(ST* ps);
//栈初始化
void StackInit(ST* ps)
{
//避免传入空指针
assert(ps);
ps->a = NULL;
ps->top = 0;//定义top为栈最后数据的后一个位置
//也可以选择让top为当前最后数据的位置 此时初始化top=-1;
ps->capacity = 0;
return;
}
//栈销毁
void StackDestroy(ST* ps)
{
//避免传入空指针
assert(ps);
free(ps->a);//释放开辟的数组栈空间
ps->a = NULL;//置空,避免造成野指针
}
//入栈
void StackPush(ST* ps, STDataType x)
{
assert(ps);
if (ps->top == ps->capacity)//栈满的情况
{
//如果原来容量为0则让新容量为4,否则为两倍
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
//调整数组栈大小(特别的:当数组指针为NULL时,realloc的作用和malloc的作用一样)
STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(ST) * newcapacity);
if (tmp == NULL)//tmp为NULL时则表示调整数组空间失败,那么就打印错误并结束进程
{
perror("realloc fail:");
exit(-1);
}
ps->a = tmp;
ps->capacity = newcapacity;
}
ps->a[ps->top] = x;//存入数据
ps->top++;//top位置更新
return;
}
//出栈
void StackPop(ST* ps)
{
//避免传入空指针
assert(ps);
//出栈到数据个数为0结束
if (StackEmpty(ps))
return;
ps->top--;//让top减减得到出栈的效果
return;
}
//获取栈顶数据
STDataType StackTop(ST* ps)
{
//避免传入空指针
assert(ps);
//为空栈时无栈顶数据
assert(!StackEmpty(ps));
return ps->a[ps->top-1];//此时top-1才表示栈顶数据的下标
}
//栈使用空间大小
int StackSize(ST* ps)
{
//避免传入空指针
assert(ps);
return ps->top;
}
//是否为空栈
bool StackEmpty(ST* ps)
{
//避免传入空指针
assert(ps);
return ps->top == 0;
}
每日k题无烦恼,点赞学习不得了~