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);
}
亿速云「云服务器」,即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘,价格低至29元/月。点击查看>>
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。