北辰苏州网站建设,合肥有做网站的吗,重庆壹制作,dt高端网站设计思路#xff1a;用栈的后进先出的特性#xff0c;来完成题目的要求 因为C有库#xff0c;可以直接用#xff0c;而C语言没有#xff0c;所以我们直接把写好的栈拷贝上来用。 首先#xff0c;完成框架的搭建 其次#xff0c;再实现循环内的部分。1.左括号入栈 2.右括… 思路用栈的后进先出的特性来完成题目的要求 因为C有库可以直接用而C语言没有所以我们直接把写好的栈拷贝上来用。 首先完成框架的搭建 其次再实现循环内的部分。1.左括号入栈 2.右括号出栈匹配 这里在右括号匹配的判断要注意不要写成两个都相等这样不能说明全都匹配成功所以就写成两边不相等满足则直接return false不满足则继续循环 每次循环结束s。所有循环停止后没有return false则return true 看起来好像没有什么问题对吧 其实上述只适用于左右括号数量相等的场景我们还要考虑两种特殊情况 1.左括号多于右括号 2.右括号多于左括号 左括号多于右括号时循环结束栈内元素个数不为0则用STEmpty判断一下 如果为空与之前相同返回true如果不为空则返回false 右括号多于左括号时在循环内部直到栈已经空了还有右括号要匹配那么此时也直接返回false 完整代码如下
typedef char STDataType;
typedef struct Stack
{STDataType* a;int top;int capacity;
}ST;//初始化
void STInit(ST* pst);
//销毁
void STDestroy(ST* pst);
//压栈
void STPush(ST* pst, STDataType x);
//出栈
void STPop(ST* pst);
//获取栈顶元素
STDataType STTop(ST* pst);
//检测栈是否为空
bool STEmpty(ST* pst);
//检测栈中有效元素个数
int STSize(ST* pst);void STInit(ST* pst)
{assert(pst);pst-a NULL;pst-top 0;//top指向栈顶元素的下一个位置pst-capacity 0;
}void STDestroy(ST* pst)
{assert(pst);free(pst-a);pst-top pst-capacity 0;
}void STPush(ST* pst, STDataType x)
{assert(pst);if (pst-top pst-capacity){int newCapacity pst-capacity 0 ? 4 : pst-capacity * 2;STDataType* tmp (STDataType*)realloc(pst-a, newCapacity * sizeof(STDataType));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(!STEmpty(pst));pst-top--;
}STDataType STTop(ST* pst)
{assert(pst);assert(!STEmpty(pst));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){//1.左括号入栈//2.右括号出栈匹配if (*s (||*s [||*s {){STPush(st, *s);}else{//解决右括号多于左括号的问题if (STEmpty(st)){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;
}
