【栈OJ题解】有效的括号
目录
一、题目：
二、题目分析：
三、思路：
四、代码实现：
王德有话说：
dear 盆友们，
上一节，我们简述了数据结构栈的底层代码实现，下面，我们一起来探讨一下栈的OJ有效的括号的实现：
一、题目：
先带大家来回顾一下栈的底层实现：
//定义栈的结构
typedef char STDataType;
typedef struct Stack
{STDataType* arr;int top;//始终指向栈顶的位置int capacity;//栈的容量
}ST;void StackInit(ST* ps)
{ps->arr = NULL;ps->top = ps->capacity = 0;
}//入栈
void StackPush(ST* ps,STDataType x)
{assert(ps);if (ps->top == ps->capacity){//增容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 StackEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}//出栈操作
void StackPop(ST* ps)
{assert(ps);//这里要判断一下栈是否为空if (!StackEmpty(ps)){//不为空才能继续往下走--ps->top;}
}//取栈顶元素
STDataType StackTop(ST* ps)
{assert(ps);return ps->arr[ps->top-1];
}//栈的销毁
void StackDestroy(ST* ps)
{if (ps->arr)free(ps->arr);ps->arr = NULL;ps->capacity = ps->top = 0;
}//获取栈中有效数据个数
int StackSize(ST* ps)
{assert(ps);return ps->top - 1;
}二、题目分析：
- 左括号必须与相同类型的右括号闭合；
- 左右括号必须以正确的顺序闭合；
- 每个右括号必须有相同类型的左括号与之闭合
有如下几个实例："([])"，"()[]{}"，"({])"，"("，")"。
值得注意的是，本题与小、中、大括号的优先级无关，童鞋们可以忽略这一点~
三、思路：
- 遍历数组
- 左括号入栈
- 右括号 取栈顶跟*pi进行匹配
首先，我们定义一个栈、一个char类型的指针pi（指向字符类型数组的第一个元素s），随后，遍历数组，这里可以用while，满足条件进入循环，不满足条件跳出循环，这里的条件是"*pi！='\0'"。
其次，在while循环中，我们使用if语句，如果遍历到的字符是左括号（'('、'['、'{'以下均简称为左括号，右括号同样）就入栈，如果不是左括号，就进入else语句。
进入到else语句，一般有几种情况：
- 一是并没有左括号入栈，栈为空，第一个字符就是右括号，这里要直接返回false；
这里值得注意的一点是：返回false之前要将栈销毁。
- 二是遍历完左括号之后遍历到了右括号，上述思路中，我们写到，如果遍历到了右括号，取栈顶，与右括号进行匹配，如果（ ）或者[ ] 亦或者{ }， 匹配成功，出栈顶（在else语句中实现），继续遍历，这里要进行pi++的操作。
注意这里：上述提到的pi++的操作是在if else语句外，while循环里实现的，因为小编也是新手，在这里思考了一会。
看到这儿，细心的朋友可能会问了，如果遇到了 只有左括号，'(' 这种事例呢，该如何解决？
下面，我们来分析，如果字符串中只有左括号，遍历之后，*pi为'\0'，跳出循环，此时判断栈是否为空，如果栈为空，说明匹配成功，因为匹配成功的左括号都会被销毁，如果栈中还留有括号，就说明未匹配成功，不符合“有效的括号”这一规则，返回false。
四、代码实现：
//借助数据结构栈来实现
bool isValid(char* s) {ST st;//定义一个栈StackInit(&st);//对栈进行初始化char*pi = s;//定义一个指针，准备遍历数组while(*pi!='\0')//进入数组{if(*pi=='('||*pi=='['||*pi=='{')//左括号入栈{StackPush(&st,*pi);}else{if(StackEmpty(&st))//判断栈为空的情况{return false;}char top = StackTop(&st);//如果是右括号，则出栈顶，与*pi进行匹配if((top=='('&& *pi!=')')||(top=='['&& *pi !=']')||(top=='{'&& *pi !='}')){StackDestroy(&st);return false;}StackPop(&st);}pi++;}bool ret = StackEmpty(&st)?true:false;//栈不为空，说明只有左括号//返回false，因为匹配成功的左括号都被销毁了StackDestroy(&st);return ret;
}