LeetCode之有效的括号

思路

借助栈解题，遍历字符数组，左括号进栈，右括号就与最近的栈顶元素比较，先看是不是为空栈，是则说明有多余的右括号，不是则正常比较，比之后出栈，才能和下一个栈里的元素比较，所有字符遍历完后还要判断栈是否为空，不为空说明有多余的左括号，空则是有效的括号。
//每次返回前都要销毁栈。

解题

typedefinttype;typedefstructStack{type*a;inttop;intcapacity;}stack;voidInit(stack*s){assert(s);s->a=NULL;s->top=0;//初始 0则代表top指向栈顶元素的下一个数据（可以当有效元素个数用），初始-1代表指向栈顶元素（可以当下标用）。s->capacity=0;}voidDestroy(stack*s){assert(s);assert(s->a);free(s->a);s->a=NULL;s->top=s->capacity=0;}voidCheck(stack*s){if(s->top==s->capacity){intnewcapacity=s->capacity==0?4:s->capacity*2;type*tmp=(type*)realloc(s->a,sizeof(type)*newcapacity);if(tmp==NULL){perror("realloc");exit(1);}s->a=tmp;s->capacity=newcapacity;}}voidPush(stack*s,type x){//不分头尾插入是因为只规定一端插入删除。assert(s);Check(s);s->a[s->top++]=x;}voidPop(stack*s){assert(s);assert(s->top>0);//要删除元素个数不能为0.s->top--;}typeTop(stack*s){assert(s);assert(s->top>0);returns->a[s->top-1];}boolEmpty(stack*s){assert(s);returns->top==0;}intNum(stack*s){assert(s);returns->top;}boolisValid(char*s){stack str;Init(&str);while(*s!='\0'){//遍历字符串if(*s=='('||*s=='{'||*s=='['){//左括号就进栈Push(&str,*s);}else{//右括号就和栈顶元素比较if(Empty(&str)){//如果栈空，说明有多余的右括号，就返回falseDestroy(&str);//返回前记得销毁栈returnfalse;}type top=Top(&str);Pop(&str);//每次和栈顶元素比较后都要出栈，才能和下一个栈顶元素比较if((top=='('&&*s!=')')||//不匹配(top=='{'&&*s!='}')||(top=='['&&*s!=']')){Destroy(&str);returnfalse;}}s++;}//如果有多余的左括号就返回false，没有就truebool ret=Empty(&str);Destroy(&str);returnret;}