数据结构 ——— 数组栈oj题：有效括号

目录

题目要求

代码实现 

---

题目要求

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

有效字符串需满足：

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

示例 1：

输入：s = "()"

输出：true

示例 2：

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

输出：true

示例 3：

输入：s = "(]"

输出：false

---

代码实现

创建栈所需的结构以及函数：

// 数据类型
typedef char STDataType;typedef struct Stack
{STDataType* a; //指向栈底的指针int top; //栈顶元素的下标int capaicty; //容量
}ST;// 初始化
void STInit(ST* pst)
{assert(pst);pst->a = NULL;pst->top = -1;pst->capaicty = 0;
}// 入栈（尾插）
void STPush(ST* pst, STDataType x)
{// 数据入栈前判断是否需要扩容if (pst->capaicty == (pst->top + 1)){// 扩容int newCapaicty = pst->capaicty == 0 ? 4 : pst->capaicty * 2;STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType) * newCapaicty);// 判断是否扩容成功if (tmp == NULL){perror("realloc fail");return;}pst->a = tmp;pst->capaicty = newCapaicty;}// 存放数据pst->a[++pst->top] = x;
}// 出栈（尾删）
void STPop(ST* pst)
{// 当栈内无数据时if (pst->top == -1){printf("无数据可出栈\n");return;}pst->top--;
}// 访问栈顶元素
STDataType STTop(ST* pst)
{assert(pst);// 当栈内无数据时if (pst->top == -1){printf("无数据可访问\n");return -1;}return pst->a[pst->top];
}// 判断栈是否为空
bool STEmpty(ST* pst)
{assert(pst);return pst->top == -1;
}// 释放栈
void STDestroy(ST* pst)
{assert(pst);free(pst->a);pst->a = NULL;pst->capaicty = 0;pst->top = -1;
}

代码演示：

bool isValid(char* s)
{assert(s != NULL);int len = (int)strlen(s);// 当字符串长度为奇数个时肯定会有括号不匹配if (len % 2 == 1)return false;ST st;STInit(&st);for (int i = 0; i < len; i++){// 1. 遇到左括号就入栈if (s[i] == '(' || s[i] == '[' || s[i] == '{'){STPush(&st, s[i]);}else //2. 遇到右括号就和栈顶元素（左括号）进行匹配{// 3. 排除第一个字符就是右括号的情况if (STEmpty(&st) == true){STDestroy(&st);return false;}// 取出当前栈顶元素char top = STTop(&st); // 4. 进行匹配if (top == '(' && s[i] != ')' ||  top == '[' && s[i] != ']' ||top == '{' && s[i] != '}'){// 5. 优先判断匹配不成功的情况STDestroy(&st);return false;}else{// 6. 表示匹配成功，移除当前栈顶元素，进行下一轮匹配STPop(&st);}}}bool ret = STEmpty(&st);// 7. 释放栈STDestroy(&st);return ret;
}

 代码解析：

遇到左括号就入栈，遇到右括号就和栈顶元素进行匹配
需要注意的是：当字符串的长度为奇数的情况，肯定不为有效括号，且当第一个括号就是右括号的情况，肯定不为有效括号

代码验证：

为有效括号时：

为无效括号时：

算法的时间和空间复杂度：

for 循环执行了 N 次，每次内部常数次，且以最坏的情况来看，额外开辟了 N 个空间

时间复杂度：O(N)

空间复杂度：O(N)