嘉兴制作网站_广州番禺最新通告_网站服务器搭建_电商网站订烟平台

一、引言

在LeetCode 20 题 “有效的括号” 中，我们需要判断一个只包含 {} [] () 的字符串是否有效。本文通过实现一个动态栈结构，详细讲解代码逻辑，帮助理解栈在括号匹配问题中的应用。

---

二、栈结构核心函数讲解

1. 栈的初始化：StackInit

void StackInit(Stack* ps) {ps->_a = NULL;ps->_top = ps->_capacity = 0;
}

• 作用：初始化栈的成员变量。
• 细节：将存储数据的指针 _a 置为空，栈顶 _top 和容量 _capacity 初始化为 0，为后续操作做准备。

2. 获取栈顶元素：StackTop

STDataType StackTop(Stack* ps) {return ps->_a[ps->_top - 1];
}

• 作用：返回栈顶元素。
• 细节：通过 _top - 1 定位栈顶元素（因为 _top 指向栈顶下一个位置），使用前需确保栈非空。

3. 入栈操作：StackPush

void StackPush(Stack* ps, STDataType data) {assert(ps);if (ps->_top == ps->_capacity) {int newCapacity = ps->_capacity == 0 ? 4 : 2 * ps->_capacity;STDataType* tmp = (STDataType*)realloc(ps->_a, newCapacity * sizeof(STDataType));if (tmp == NULL) {perror("realloc fail");exit(1);}ps->_a = tmp;ps->_capacity = newCapacity;}ps->_a[ps->_top++] = data;
}

• 作用：向栈中插入元素，支持动态扩容。
• 细节：
  • 先检查栈空间是否不足，不足则用 realloc 扩容（初始容量 4，之后双倍扩容）。
  • 插入元素后，_top 自增指向下一个位置。

4. 检查栈是否为空：StackEmpty

bool StackEmpty(Stack* ps) {assert(ps);return ps->_top == 0;
}

• 作用：判断栈是否为空。
• 细节：通过 _top 是否为 0 判断，是则返回 true，否则 false。

5. 出栈操作：StackPop

void StackPop(Stack* ps) {assert(!StackEmpty(ps));ps->_top--;
}

• 作用：删除栈顶元素。
• 细节：先通过 assert 确保栈非空，再将 _top 减 1，实现逻辑删除。

6. 销毁栈：StackDestroy

void StackDestroy(Stack* ps) {if (ps->_a) {free(ps->_a);}ps->_a = NULL;ps->_top = ps->_capacity = 0;
}

• 作用：释放栈占用的内存，防止内存泄漏。
• 细节：先释放动态分配的数组 _a，再将成员变量重置为初始状态。

---

三、核心逻辑：isValid 函数

bool isValid(char* s) {Stack st;StackInit(&st);char* ps = s;while (*ps != '\0') {if (*ps == '(' || *ps == '[' || *ps == '{') {StackPush(&st, *ps);} else {if (StackEmpty(&st)) {StackDestroy(&st);return false;}char top = StackTop(&st);if ((top == '(' && *ps == ')') || (top == '[' && *ps == ']') || (top == '{' && *ps == '}')) {StackPop(&st);} else {StackDestroy(&st);return false;}}ps++;}bool ret = StackEmpty(&st);StackDestroy(&st);return ret;
}

• 逻辑解析：
  1. 初始化栈：创建栈 st 并初始化。
  2. 遍历字符串：
     • 遇到左括号 ({[，直接入栈。
     • 遇到右括号 )}]：
       • 若栈为空，说明无匹配左括号，直接返回 false。
       • 检查栈顶元素是否匹配当前右括号，匹配则出栈，不匹配返回 false。
  3. 最终检查：遍历结束后，若栈为空，说明所有括号匹配，否则不匹配。
  4. 销毁栈：无论结果如何，最后销毁栈释放资源。

---

四、完整代码

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>typedef char STDataType;
typedef struct Stack {STDataType* _a;int _top;int _capacity;
} Stack;void StackInit(Stack* ps) {ps->_a = NULL;ps->_top = ps->_capacity = 0;
}STDataType StackTop(Stack* ps) {return ps->_a[ps->_top - 1];
}void StackPush(Stack* ps, STDataType data) {assert(ps);if (ps->_top == ps->_capacity) {int newCapacity = ps->_capacity == 0 ? 4 : 2 * ps->_capacity;STDataType* tmp = (STDataType*)realloc(ps->_a, newCapacity * sizeof(STDataType));if (tmp == NULL) {perror("realloc fail");exit(1);}ps->_a = tmp;ps->_capacity = newCapacity;}ps->_a[ps->_top++] = data;
}bool StackEmpty(Stack* ps) {assert(ps);return ps->_top == 0;
}void StackPop(Stack* ps) {assert(!StackEmpty(ps));ps->_top--;
}void StackDestroy(Stack* ps) {if (ps->_a) {free(ps->_a);}ps->_a = NULL;ps->_top = ps->_capacity = 0;
}bool isValid(char* s) {Stack st;StackInit(&st);char* ps = s;while (*ps != '\0') {if (*ps == '(' || *ps == '[' || *ps == '{') {StackPush(&st, *ps);} else {if (StackEmpty(&st)) {StackDestroy(&st);return false;}char top = StackTop(&st);if ((top == '(' && *ps == ')') || (top == '[' && *ps == ']') || (top == '{' && *ps == '}')) {StackPop(&st);} else {StackDestroy(&st);return false;}}ps++;}bool ret = StackEmpty(&st);StackDestroy(&st);return ret;
}

---

五、总结

通过实现动态栈，我们高效解决了括号匹配问题。栈的 “后进先出” 特性完美契合括号匹配逻辑：左括号入栈，右括号与栈顶匹配。这一思路可扩展到更多需要匹配关系的场景（如标签匹配、表达式校验等）。理解栈的底层实现，能更灵活地应用这一数据结构解决实际问题。