有效的括号（栈）

有效的括号（栈）

题目描述

• 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

  有效字符串需满足：

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。
  3. 每个右括号都有一个对应的相同类型的左括号。

• 示例 1：

  输入：s = “()”

  输出：true

  示例 2：

  输入：s = “()[]{}”

  输出：true

  示例 3：

  输入：s = “(]”

  输出：false

  示例 4：

  输入：s = “([])”

  输出：true

• 提示：

  • 1 <= s.length <= 10^4
  • s 仅由括号 '()[]{}' 组成

• 然后题目提供了一个函数

• bool isValid(char* s) {}
  

答案

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>typedef int SKDataType;
typedef struct Stack
{SKDataType *a;int top;//栈顶下标int capacity;//容量
}SK;//初始化栈
void SKInit(SK* ps);
//销毁栈
void SKDestroy(SK* ps);//插入数据，压栈
void SKPush(SK* ps,SKDataType x);
//删除数据，出栈
void SKPop(SK* ps);
//获取现在栈顶元素的值
SKDataType SKTop(SK* ps);//栈的大小
int SKSize(SK* ps);
//判断栈是否为空
bool SKEmpty(SK* ps);//初始化栈
void SKInit(SK* ps)
{assert(ps);ps->a=NULL;ps->capacity=0;ps->top=0;
}//销毁栈
void SKDestroy(SK* ps)
{assert(ps);free(ps->a);ps->a=NULL;ps->top=ps->capacity=0;
}//插入数据，压栈
void SKPush(SK* ps,SKDataType x)
{assert(ps);if(ps->top==ps->capacity){int newCapacity=ps->capacity==0 ? 4 :ps->capacity*2;SKDataType * tmp=(SKDataType*) realloc(ps->a,sizeof (SKDataType)*newCapacity);if(tmp==NULL){perror("realloc failed");exit(-1);}ps->a=tmp;ps->capacity=newCapacity;}ps->a[ps->top]=x;ps->top++;
}//删除数据，出栈
void SKPop(SK* ps)
{assert(ps);assert(ps->top>0);ps->top--;
}//获取现在栈顶元素的值
SKDataType SKTop(SK* ps)
{assert(ps);assert(ps->top>0);return ps->a[ps->top-1];
}//栈的大小
int SKSize(SK* ps)
{assert(ps);return ps->top;
}//判断栈是否为空
bool SKEmpty(SK* ps)
{assert(ps);return ps->top==0;
}bool isValid(char* s) {SK st;SKInit(&st);char topval;while(*s){if(*s=='('||*s=='['||*s=='{'){SKPush(&st,*s);}else{//数量不匹配if(SKEmpty(&st)){SKDestroy(&st);return false;}topval=SKTop(&st);SKPop(&st);if((*s==']'&&topval!='[')||(*s==')'&&topval!='(')||(*s=='}'&&topval!='{')){SKDestroy(&st);return false;}}s++;}//判断栈是否为空，不为空则说明数量不匹配bool ret =SKEmpty(&st);SKDestroy(&st);return ret;
}

思路解析

• 具体的过程如下：