20. Valid Parentheses

成都創(chuàng)新互聯(lián)專注于企業(yè)網(wǎng)絡(luò)營銷推廣、網(wǎng)站重做改版、秀英網(wǎng)站定制設(shè)計(jì)、自適應(yīng)品牌網(wǎng)站建設(shè)、HTML5建站、成都商城網(wǎng)站開發(fā)、集團(tuán)公司官網(wǎng)建設(shè)、成都外貿(mào)網(wǎng)站建設(shè)公司、高端網(wǎng)站制作、響應(yīng)式網(wǎng)頁設(shè)計(jì)等建站業(yè)務(wù)，價(jià)格優(yōu)惠性價(jià)比高，為秀英等各大城市提供網(wǎng)站開發(fā)制作服務(wù)。

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.

題意：

括號(hào)字符串的匹配。

棧的特性：

后進(jìn)先出。

棧的頭文件：

struct stack

{

    char elem;

    struct stack *next;

};

棧的大小：

在64位系統(tǒng)上：sizeof(char) = 1，sizeof(struct stack *) = 8，sizeof(struct stack) = 16;

在32位系統(tǒng)上：sizeof(char) = 1，sizeof(struct stack *) = 4，sizeof(struct stack) = 8;

64位系統(tǒng)的地址是64位的，即8字節(jié)；32位系統(tǒng)的地址是32的，即4字節(jié)。所以sizeof(struct stack *)分別是8字節(jié)和4字節(jié)。雖然sizeof(char)都為一字節(jié)。由于結(jié)構(gòu)體存在字節(jié)對(duì)齊，所以sizeof取出的結(jié)構(gòu)體大小是結(jié)構(gòu)體最大元素的整數(shù)倍。所以結(jié)構(gòu)體大小是16字節(jié)和8字節(jié)。

push入棧，pop出棧，top獲取棧頂元素。getLen函數(shù)如果棧為空，則返回一；否則返回零。

思路：

如果元素是'('，'{'或'['則直接入棧；如果是元素是')'，則判斷棧頂，如果棧頂元素是'('則'('出棧。'}'和']'一樣處理。

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