题目链接:有效的括号
给定一个只包括 '('
,')'
,'{'
,'}'
,'['
,']'
的字符串 s
,判断字符串是否有效。
有效字符串需满足:
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
示例 1:
输入:s = "()" 输出:true
示例 2:
输入:s = "()[]{}" 输出:true
示例 3:
输入:s = "(]" 输出:false
实现代码:
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdbool.h>
#include<string.h>
#include<assert.h>
#include<stdlib.h>
//栈的实现
typedef char STdatetype;
typedef struct Stack {
STdatetype* phead;
int size;
int capacity;
}ST;
//栈的初始化
void STDInit(ST* tmp) {
assert(tmp);
tmp->phead = NULL;
tmp->capacity = tmp->size = 0;
}
//栈的销毁
void STDdestroy(ST* tmp) {
assert(tmp);
free(tmp->phead);
tmp->phead = NULL;
tmp->capacity = tmp->size = 0;
}
//判栈是否满
bool IsFull(ST* tmp) {
if (tmp->size == tmp->capacity) {
return true;
}
return false;
}
//入栈
void push(ST* tmp, STdatetype date) {
assert(tmp);
if (IsFull(tmp)) {
int newcapacity = tmp->capacity == 0 ? 4 : 2 * tmp->capacity;
STdatetype* ptr = (STdatetype*)realloc(tmp->phead, newcapacity * sizeof(STdatetype));
if (!ptr) {
perror("push:relloc");
return;
}
tmp->phead = ptr;
tmp->capacity = newcapacity;
}
tmp->phead[tmp->size++] = date;
}
//出栈
void pop(ST* tmp) {
assert(tmp);
if (tmp->size != 0)
tmp->size--;
else {
perror("pop");
}
}
//实际作用函数
bool isValid(char* s) {
size_t len = strlen(s);
if (len % 2) {
return false;
}
ST stack;
STDInit(&stack);
for (int i = 0; i < len; i++) {
if (s[i] == '(' || s[i] == '[' || s[i] == '{') {
push(&stack, s[i]);
}
if (s[i] == ')' || s[i] == ']' || s[i] == '}') {
if (stack.size == 0) {
STDdestroy(&stack);
return false;
}
if (stack.phead[stack.size - 1] == '(' && s[i] == ')') {
pop(&stack);
}
else if (stack.phead[stack.size - 1] == '[' && s[i] == ']') {
pop(&stack);
}
else if (stack.phead[stack.size - 1] == '{' && s[i] == '}') {
pop(&stack);
}
else {
return false;
}
}
}
if (stack.size == 0) {
STDdestroy(&stack);
return true;
}
else {
STDdestroy(&stack);
return false;
}
}