文章目录
- 有效的括号
有效的括号
原题链接:有效的括号
详解栈的链接
这道题可以利用栈来解决
1.左括号入栈
2.右括号与出栈顶左括号匹配
//创建一个动态的栈
typedef char STDateType;
typedef struct Stack
{STDateType* a;//储存指定数据类型的数组int top;//栈顶int capacity;//栈的容量
}ST;//栈的初始化和销毁
void STInit(ST* pst);
void STDestroy(ST* pst);//入栈和出栈
void STPush(ST* pst, STDateType x);
void STPop(ST* pst);//返回栈顶数据
STDateType STTop(ST* pst);//判空
bool STEmpty(ST* pst);//栈数据个数
int STSize(ST* pst);//栈的初始化
void STInit(ST* pst)
{assert(pst);pst->a = NULL;//指向栈顶元素的下一个位置pst->top = 0;//指向栈顶元素//pst->top = -1;pst->capacity = 0;
}//栈的销毁
void STDestroy(ST* pst)
{assert(pst);free(pst->a);pst->a = NULL;pst->top = 0;pst->capacity = 0;
}//入栈
void STPush(ST* pst, STDateType x)
{assert(pst);//如果容量不够,需要扩容if (pst->top == pst->capacity){int newcapacity = pst->capacity == 0 ? 4 : 2 * pst->capacity;STDateType* tmp = (STDateType*)realloc(pst->a, newcapacity * sizeof(ST));if (tmp == NULL){perror("realloc fail");return;}pst->a = tmp;pst->capacity = newcapacity;}//储存数据pst->a[pst->top++] = x;
}//出栈
void STPop(ST* pst)
{assert(pst);assert(pst->top > 0);pst->top--;
}//返回栈顶数据
STDateType STTop(ST* pst)
{assert(pst);assert(pst->top > 0);return pst->a[pst->top - 1];
}//判空
bool STEmpty(ST* pst)
{assert(pst);return pst->top == 0;
}//栈数据个数
int STSize(ST* pst)
{assert(pst);return pst->top;
}bool isValid(char* s)
{//定义一个栈ST st;STInit(&st);while(*s){//左括号入栈if(*s == '(' || *s == '[' || *s == '{'){STPush(&st,*s);}//右括号与出栈的左括号匹配else{if(STSize(&st) == 0){STDestroy(&st);return false;}char top = STTop(&st);STPop(&st);if((top == '(' && *s != ')') ||( top == '[' && *s != ']') || (top == '{' && *s != '}')){STDestroy(&st);return false;}}s++;}//出循环后有两种情况://左括号 == 右括号 //左括号的数量多于右括号的数量bool ret = STEmpty(&st);STDestroy(&st);return ret;}