做网站需要投资多少钱,公司网站建设哪里实惠,贵阳app定制开发,同城58招聘信息题目描述 分析
我们刚上来的思路可能是#xff1a;找出这三种括号的个数 如果都是偶数 说明匹配 但是这里还有一个顺序问题 比如 )( 这样是不匹配的#xff01; 所以这种思路不可取#xff01;
我们想 如果遇到左括号#xff0c;把他读到一个顺序表中#…题目描述 分析
我们刚上来的思路可能是找出这三种括号的个数 如果都是偶数 说明匹配 但是这里还有一个顺序问题 比如 )( 这样是不匹配的 所以这种思路不可取
我们想 如果遇到左括号把他读到一个顺序表中然后遇到匹配的右括号就把他放出来也就相当于对对碰 比如 { [ ( ) ] } 我们会把 { [ ( 读到一个顺序表里 然后依次让( ) [ ] { }对对碰消掉如果最后顺序表中没有元素是不是说明就匹配呢 这里我们就考虑使用 栈 因为栈只有压栈和出栈十分符合这道题
代码
由于想省事我就直接把之前写的栈的实现给搬到了题目中 其实 写几个有用的接口就可以 没必要都写
typedef int STDataType;
typedef struct Stack {//动态开辟数组STDataType* a;int top;//栈顶int capacity;//容量
}ST;
//初始化
void StackInit(ST* ps);
//压栈
void StackPush(ST* ps, STDataType x);
//出栈
void StackPop(ST* ps);
//获取栈中有效元素个数
int StackSize(ST* ps);
//显示栈顶元素
STDataType StackTop(ST* ps);
//检测栈是否为空
bool StackEmpty(ST* ps);
//销毁
void StackDestory(ST* ps);//初始化
void StackInit(ST* ps)
{assert(ps);ps-a NULL;ps-capacity ps-top 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-a,sizeof(STDataType) * newCapacity);if (tmp NULL){printf(realloc fail);exit(-1);}ps-capacity newCapacity;ps-a tmp;}ps-a[ps-top] x;ps-top;
}
//出栈
void StackPop(ST* ps)
{assert(ps);assert(ps-top 0);//只需要ps--就可以了ps-top--;}
//获取栈中有效元素个数
int StackSize(ST* ps)
{assert(ps);return ps-top;
}
//获取栈顶元素
STDataType StackTop(ST* ps)
{assert(ps);return ps-a[ps-top-1];
}
//检测栈是否为空
bool StackEmpty(ST* ps)
{assert(ps);return ps-top 0;
}
//销毁
void StackDestory(ST* ps)
{assert(ps);free(ps-a);ps-a NULL;//ps-a 不用了 所以置空就可以了ps-capacity ps-top 0;
}bool isValid(char * s){ST st;StackInit(st);// 左括号入栈右括号出栈while(*s){//如果是左括号 那么入栈if((*s{) ||(*s() || (*s[)){StackPush(st,*s);s;//判断完这一次 向后走}else{//如果上面的if没有执行 说明第一个就是右括号那么 肯定不匹配if(StackEmpty(st)){//异常情况返回需要先销毁栈 否则容易造成内存泄漏StackDestory(st);return false;}char chStackTop(st);//获取栈顶元素if ((ch{ *s})//匹配是哪一种情况|| (ch [ *s])|| (ch( *s))){StackPop(st);//如果满足一对括号匹配那么出栈s;}else//如果不匹配 返回false{//返回之前防止内存泄漏 要销毁栈StackDestory(st);return false;}}}//利用临时变量判断是否为空,为空说明都读走了 否则说明有不匹配的bool retStackEmpty(st);//销毁--防止内存泄漏!StackDestory(st);return ret;
}
