数据结构：（OJ题力扣 20）. 有效的括号

本文主要是介绍数据结构：（OJ题力扣 20）. 有效的括号，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
3. 每个右括号都有一个对应的相同类型的左括号。

示例 1：

输入：s = "()"
输出：true

示例 2：

输入：s = "()[]{}"
输出：true

示例 3：

输入：s = "(]"
输出：false

提示：

• 1 <= s.length <= 104
• s 仅由括号 '()[]{}' 组成

代码如下：

#include <stdbool.h>//定义栈的结构
typedef char STDataType;
typedef struct Stack
{STDataType* arr;int capacity;int top;
}ST;
//初始化
void STInit(ST* ps)
{assert(ps);ps->arr = NULL;ps->capacity = ps->top = 0;
}//销毁
void STDestory(ST* ps)
{assert(ps);if (ps->arr){free(ps->arr);}ps->arr = NULL;ps->capacity = ps->top = 0;
}//入栈
void StackPush(ST* ps, STDataType x)
{assert(ps);if (ps->capacity == ps->top){int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;STDataType* tmp = (STDataType*)realloc(ps->arr, newcapacity * sizeof(STDataType));if (tmp == NULL){perror("realloc fail!");exit(1);}ps->arr = tmp;ps->capacity = newcapacity;}//空间足够ps->arr[ps->top++] = x;
}
//判断是否为空
bool StcakEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}
//出栈
void StackPop(ST* ps)
{assert(ps);assert(!StackEmpty(ps));--ps->top;
}
//取出栈顶的元素
STDataType StackTop(ST* ps)
{assert(ps);assert(!StackEmpty(ps));return ps->arr[ps->top - 1];
}//获取栈中有效元素的个数
int STSize(ST* ps)
{assert(ps);return ps->top;
}
bool isValid(char* s) {ST st;//初始化STInit(&st);//遍历字符串char*ps=s;while(*ps!='\0'){//左括号入栈if(*ps=='('||*ps=='['||*ps=='{'){StackPush(&st,*ps);}else //右括号和栈顶元素比较{//取栈顶元素char ch=StackTop(&st);if(*ps==')'&&ch=='('||*ps==']'&&ch=='['||*ps=='}'&&ch=='{'){StackPop(&st);}else{STDestory(&st);return false;}    }ps++;}//销毁STDestory(&st);return false;
}

这篇关于数据结构：（OJ题力扣 20）. 有效的括号的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---