leetcode 20.有效的括号

⭐️ 题目描述

leetcode链接： 有效的括号

1️⃣ 代码与思路：

栈问题： 左括号进栈，如果是右括号则拿出栈顶元素比较，相同弹出栈顶元素，接着继续比较，不相同返回 false，还要考虑一些特殊情况，具体看如下代码。

注：由于C语言没有接口，所以手写了一套栈来使用。或者也可以使用静态数组模拟栈。

typedef char StackType;typedef struct Stack {StackType* data;int top;// 栈顶int capacity;// 容量}Stack;void StackInit(Stack * ps);void StackDestroy(Stack * ps);void StackPush(Stack* ps , StackType node);void StackPop(Stack* ps);bool StackEmpty(Stack* ps);int StackSize(Stack* ps);StackType StackTop(Stack * ps);void StackInit(Stack* ps) {assert(ps);ps->data = NULL;ps->top = 0;ps->capacity = 0;}void StackDestroy(Stack* ps) {assert(ps);free(ps->data);ps->top = 0;ps->capacity = 0;}void StackPush(Stack* ps , StackType node) {assert(ps);// 检查容量if (ps->top == ps->capacity) {int newCapacity = ps->capacity == 0 " />4 : ps->capacity * 2;StackType* newData = (StackType*)realloc(ps->data , sizeof(StackType) * newCapacity);assert(newData);ps->data = newData;ps->capacity = newCapacity;}ps->data[ps->top] = node;ps->top++;}void StackPop(Stack* ps) {assert(ps);// 判断栈是否为空assert(!StackEmpty(ps));ps->top--;}StackType StackTop(Stack* ps) {assert(ps);assert(!StackEmpty(ps));return ps->data[ps->top - 1];}bool StackEmpty(Stack* ps) {assert(ps);// 空为真，非空返回0return ps->top == 0;}int StackSize(Stack* ps) {assert(ps);return ps->top;}// 思路：左括号进栈 如果是右括号则拿出栈顶元素比较 以此类推...bool isValid(char * s){Stack st;StackInit(&st);while (*s) {if (*s == '{' || *s == '[' || *s == '(') {// 进栈StackPush(&st , *s);s++;} else {// 特殊情况：如果栈为空 那么当前的右括号无匹配项 直接返回 fasleif (StackEmpty(&st)) {StackDestroy(&st);return false;}// 取栈顶元素StackType topElement = StackTop(&st);// 弹出栈顶元素StackPop(&st);if ( (topElement == '{' && *s == '}') || (topElement == '(' && *s == ')') ||(topElement == '[' && *s == ']')) {s++;}else {StackDestroy(&st);return false;}}}// 如果循环结束 栈是空的 说明括号一对一对抵消了// 如果栈里有元素 说明括号没有完全匹配bool res = StackEmpty(&st);StackDestroy(&st);return res;}