[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;
}

char
top(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;
}

int
getLen(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);
}