【数据结构OJ题】有效的括号

原题链接：https://leetcode.cn/problems/valid-parentheses/

目录

1. 题目描述

2. 思路分析

3. 代码实现

---

1. 题目描述

 

2. 思路分析

这道题目主要考查了栈的特性：

题目的意思主要是要做到3点匹配：类型、顺序、数量。

题目给的例子是比较简单的情况，可能还有如下较为复杂的情况：

循环遍历字符串s中的字符，逐个取到每个括号，如果该括号是：

1. 左括号，入栈
2. 右括号，出栈顶括号，进行匹配。

 如果不匹配，直接返回false。否则继续循环。

 循环结束后，如果栈空则匹配，否则左括号比右括号多肯定不匹配。

3. 代码实现

typedef char STDataType;
#define INIT_CAPACITY 4
typedef struct Stack
{STDataType* a;int top;  //栈顶int capacity;  //容量
}ST;//初始化栈
void STInit(ST* ps);
//入栈
void STPush(ST* ps, STDataType x);
//出栈
void STPop(ST* ps);
//获取栈顶元素
STDataType STTop(ST* ps);
//获取栈中有效元素个数
int STSize(ST* ps);
//检测栈是否为空
bool STEmpty(ST* ps);
//销毁栈
void STDestroy(ST* ps);void STInit(ST* ps)
{assert(ps);ps->a = NULL;ps->top = 0;ps->capacity = 0;
}void STPush(ST* ps, STDataType x)
{assert(ps);if (ps->top == ps->capacity){int newCapacity = ps->capacity == 0 ? INIT_CAPACITY : ps->capacity * 2;STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newCapacity);if (tmp == NULL){perror("realloc failed");exit(-1);}ps->a = tmp;ps->capacity = newCapacity;}ps->a[ps->top] = x;ps->top++;
}void STPop(ST* ps)
{assert(ps);//空assert(ps->a > 0);--ps->top;
}STDataType STTop(ST* ps)
{assert(ps);//空assert(ps->a > 0);return ps->a[ps->top - 1];
}int STSize(ST* ps)
{assert(ps);return ps->top;
}bool STEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}void STDestroy(ST* ps)
{assert(ps);ps->a = NULL;ps->top = ps->capacity = 0;
}bool isValid(char * s){ST st;STInit(&st);char topVal;while(*s){if(*s=='('||*s=='{'||*s=='['){STPush(&st,*s);}else{if(STEmpty(&st)){STDestroy(&st);return false;}topVal=STTop(&st);if(*s==')'&&topVal!='('||*s=='}'&&topVal!='{'||*s==']'&&topVal!='['){STDestroy(&st);return false;}else{STPop(&st);}}++s;}bool ret=STEmpty(&st);STDestroy(&st);return ret;
}