上篇分析了栈（stack）的两种实现方法，一种是基于数组实现栈，另一种是基于单链表实现栈。（栈stack的数组和单链表实现 ）

本篇使用已经实现好的栈来解一个简单题：

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

有效字符串需满足：

左括号必须用相同类型的右括号闭合。

左括号必须以正确的顺序闭合。

输入：s = "{[]}"输出：true

输入：s = "([)]"输出：false

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

思路分析：

s的长度最长可达到10^4，使用数组实现的栈已经不合适，我们就使用基于单链表实现的栈。这是基于已经封装好的栈的实现来说的。如果我们使用数组，可以先求出字符串的实际长度，然后再定义栈数组的长度即可。

对给定的仅由括号'()[]{}'组成的字符串s进行遍历，遍历到的每一个左括号，在后续的遍历中，有一个相同类型的右括号将其闭合。为了保证左括号必须以正确的顺序闭合，后遇到的左括号要先闭，将这个左括号放入栈顶。

当遍历遇到一个右括号时，他需要一个相同类型的左括号将其闭合。我们将栈顶的左括号取出，判断是否为相同类型的括号。如果不是相同类型，或者栈中没有左括号，字符串S就是无效的，返回false。

过程分析：

注意到有效字符串的长度一定为偶数，因此如果字符串的长度为奇数，我们可以直接返回 ，省去后续的遍历判断过程。

if(strlen(s) % 2 != 0)return ret;

在遍历结束后，如果栈中没有左括号，说明我们将字符串 s 中的所有左括号闭合，返回 \text{True}True，否则返回 \text{False}False。

return IsStackEmpty(stack) ? ret : false;

遇到一个右括号时，他需要一个相同类型的左括号将其闭合。我们将栈顶的左括号取出，判断是否为相同类型的括号。如果不是相同类型，或者栈中没有左括号，字符串S就是无效的，返回false。

按照这个逻辑我们写出了如下代码，可以看出只是三个括号类型不同，代码其余部分相同，这种代码是应该去重的。

//第一个括号if(s[i] == '}'){    StackPop(stack, &data);    if(data != '{')    {        return false;    }    else    {        i++;    }                }//第二个括号if(s[i] == ']'){    StackPop(stack, &data);    if(data != '[')    {        return false;    }    else    {        i++;    }                }//第三个括号if(s[i] == ')'){    StackPop(stack, &data);    if(data != ')')    {        return false;    }    else    {        i++;    }                }

去重代码如下：

//把不同括号类型用同一个函数来获取char mach(char c){    if(c == '}')return '{';    if(c == ')')return '(';    if(c == ']')return '[';    return false;}//这样上边的代码就可以化简为如下形式if(mach(s[i])){    StackPop(stack, &data);    if(data != mach(s[i++]))    {       return false;     }  }    

为了保证左括号必须以正确的顺序闭合，后遇到的左括号要先闭，将这个左括号放入栈顶。

 if((s[i] == '{') || (s[i] == '(') || (s[i] == '['))  {            StackPush(stack, s[i++]);   }

完整代码如下：

#include<stdio.h>#include<stdlib.h>#include<string.h>struct List{    char data;    struct List* next;};struct Stack{    struct List* head;    int size;};struct Stack* StackInit(void){    struct Stack* stack = NULL;    stack = (struct Stack*)malloc(sizeof(struct Stack));    stack->head = (struct List*)malloc(sizeof(struct List));    stack->head->next = NULL;    stack->size = 0;    return stack;}int StackPush(struct Stack* stack, char data){    struct List* temp = (struct List*)malloc(sizeof(struct List));    temp->data = data;    temp->next = stack->head->next;    stack->head->next = temp;    stack->size++;    printf("push:%c \n",data);    return 0;}int IsStackEmpty(struct Stack* stack){    if(stack->head->next == NULL)    {        return 1;    }    else    {        return 0;    }  }int StackPop(struct Stack* stack, char* data){    struct List* temp = NULL;    if(IsStackEmpty(stack))        return -1;        temp = stack->head->next;    *data = temp->data;    stack->head->next = temp->next;    stack->size--;    free(temp);    printf("pop:%c\n",*data);    return 0;}char mach(char c){    if(c == '}')return '{';    if(c == ')')return '(';    if(c == ']')return '[';    return false;}bool isValid(char* s){    struct Stack* stack = NULL;    stack = StackInit();    int i = 0;    char data;    while (s[i] != '\0')    {        if(strlen(s) % 2 != 0)return false;        if((s[i] == '{') || (s[i] == '(') || (s[i] == '['))        {            StackPush(stack, s[i++]);        }        else        {             if(IsStackEmpty(stack)) return false;             if(mach(s[i]))             {                 StackPop(stack, &data);                 if(data != mach(s[i++]))                {                    return false;                }             }            }            }        return IsStackEmpty(stack);}int main(){    int i = 0;    char s[] = {"[[]]}{"};    bool ret = isValid(s);    printf("%d\n",ret);    printf("\n");    return 0;}

确定有限状态机(DFA)-Leet

字符串转换成一个 32 位有符号整数-atoi 函数Leet

leetcode2. 两数相加-c语言-python3

LeetCode4. 寻找两个正序数组的中位数

LeetCode5.1-马拉车算法求解最长回文子串

LeetCode5.0-最长回文子串-中心扩展法-C语言

LeetCode5.2-动态规划求解最长回文子串

LeetCode7.翻转整数-C语言与python的异同点

栈stack的数组和单链表实现

使用python实现已有c代码

c语言转学Python3——8条实用经验

判断二叉树是否为平衡二叉树

平衡二叉树 构建平衡二叉树

如何优雅地画好二叉树

二叉树的层序遍历及应用

二叉树遍历的思维导图

平衡二叉树的结点删除操作

不平衡二叉树的旋转（LL、RR、LR、RL）

二叉查找树（BST：Binary Search Tree）