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函数如果栈为空，则返回一；否则返回零。


思路：

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

structstack{charelem;structstack*next;};structstack*push(structstack*head,charc){structstack*node=NULL;node=(structstack*)malloc(sizeof(structstack));if(node==NULL){returnNULL;}node->elem=c;if(head==NULL){node->next=NULL;head=node;}else{node->next=head;}returnnode;}chartop(structstack*head){if(!head){return0;}returnhead->elem;}structstack*pop(structstack*head){if(!head){returnNULL;}charval=head->elem;structstack*delete=head;head=head->next;free(delete);returnhead;}intgetLen(structstack*head){returnhead==NULL?1:0;}boolisValid(char*s){structstack*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++;}returngetLen(head);}