[LeetCode]20. Valid Parentheses

20. Valid Parentheses

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

题意：

括号字符串的匹配。

栈的特性：

后进先出。

栈的头文件：

struct stack

{

char elem;

struct stack *next;

};

栈的大小：

在64位系统上：sizeof(char) = 1，sizeof(struct stack *) = 8，sizeof(struct stack) = 16;

在32位系统上：sizeof(char) = 1，sizeof(struct stack *) = 4，sizeof(struct stack) = 8;

64位系统的地址是64位的，即8字节；32位系统的地址是32的，即4字节。所以sizeof(struct stack *)分别是8字节和4字节。虽然sizeof(char)都为一字节。由于结构体存在字节对齐，所以sizeof取出的结构体大小是结构体最大元素的整数倍。所以结构体大小是16字节和8字节。

push入栈，pop出栈，top获取栈顶元素。getLen函数如果栈为空，则返回一；否则返回零。

思路：

如果元素是'('，'{'或'['则直接入栈；如果是元素是')'，则判断栈顶，如果栈顶元素是'('则'('出栈。'}'和']'一样处理。

struct stack{    char elem;    struct stack *next;};struct stack*push(struct stack *head, char c){    struct stack *node = NULL;    node = (struct stack *)malloc(sizeof(struct stack));    if ( node == NULL )    {        return NULL;    }        node->elem = c;    if ( head == NULL )    {        node->next = NULL;        head = node;    }    else    {        node->next = head;    }        return node;}chartop(struct stack *head){    if ( !head )    {        return 0;    }    return head->elem;}struct stack*pop(struct stack *head){    if ( !head )    {        return NULL;    }    char val = head->elem;    struct stack *delete = head;    head = head->next;    free(delete);    return head;}intgetLen(struct stack *head){    return head == NULL ? 1 : 0;}bool isValid(char* s) {    struct stack *head = NULL;    while ( *s )    {        if ( *s == '(' || *s == '{' || *s == '[' )        {            head = push(head, *s);        }                if ( *s == ')' )        {            if ( top(head) == '(' )            {                head = pop(head);            }            else            {                head = push(head, *s);            }        }                if ( *s == '}' )        {            if ( top(head) == '{' )            {                head = pop(head);            }            else            {                head = push(head, *s);            }        }                if ( *s == ']' )        {            if ( top(head) == '[' )            {                head = pop(head);            }            else            {                head = push(head, *s);            }        }        s++;    }        return getLen(head);}