本文共 1576 字，大约阅读时间需要 5 分钟。

题目描述

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

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。

示例1：

输入：s = “{[]}”

输出：true

示例2：

输入：s = “([)]”

输出：false

题解

本题的思想其实很简单，用栈来实现，从头开始遍历字符串，如果遇到 ‘(’ 、’{’、’[’，则入栈，一旦遇到 ‘)’、’}’、’]’，则出栈做匹配，如果能够匹配上，则继续向后走，直到字符串走完为止，再返回true，如果匹配不上，则直接返回false。

题解代码

typedef struct node{       char* a;    int top;    int capacity;}Stack;void StackInit(Stack* p){          assert(p);    p->a = (char*)malloc(sizeof(char)*4);    p->top = 0;    p->capacity = 4;}//入栈void push(Stack* p,char data){       assert(p);    // 若空间满了，则扩容    if(p->top == p->capacity)    {           char* tmp = (char*)realloc(p->a,sizeof(char)*p->capacity*2);        p->capacity *= 2;        p->a = tmp;    }    p->a[p->top] = data;    p->top++;}//弹出栈char pop(Stack* p){       assert(p);    if(p->top == 0)    {           exit(-1);    }    int t = p->a[p->top-1];    p->top--;    return t;}bool isValid(char * s){       Stack p;    StackInit(&p);    while(*s)    {           if(*s == '(' || *s == '[' || *s == '{')        {               push(&p,*s);            s++;        }        else        {               if(p.top == 0)            {                   return false;            }            char tmp = pop(&p);    //        printf("%c",tmp);            if((*s == ')' && tmp == '(') || (*s == ']' && tmp == '[') || (*s == '}' && tmp == '{'))            {                   s++;            }            else{                   return false;            }        }    }    //若为NULL，则说明匹配完成    if(p.top == 0)    {           return true;    }    else    {           return false;    }}