LeetCode之有效的括号

有效的括号思路解题思路借助栈解题遍历字符数组左括号进栈右括号就与最近的栈顶元素比较先看是不是为空栈是则说明有多余的右括号不是则正常比较比之后出栈才能和下一个栈里的元素比较所有字符遍历完后还要判断栈是否为空不为空说明有多余的左括号空则是有效的括号。//每次返回前都要销毁栈。解题typedefinttype;typedefstructStack{type*a;inttop;intcapacity;}stack;voidInit(stack*s){assert(s);s-aNULL;s-top0;//初始 0则代表top指向栈顶元素的下一个数据可以当有效元素个数用初始-1代表指向栈顶元素可以当下标用。s-capacity0;}voidDestroy(stack*s){assert(s);assert(s-a);free(s-a);s-aNULL;s-tops-capacity0;}voidCheck(stack*s){if(s-tops-capacity){intnewcapacitys-capacity0?4:s-capacity*2;type*tmp(type*)realloc(s-a,sizeof(type)*newcapacity);if(tmpNULL){perror(realloc);exit(1);}s-atmp;s-capacitynewcapacity;}}voidPush(stack*s,type x){//不分头尾插入是因为只规定一端插入删除。assert(s);Check(s);s-a[s-top]x;}voidPop(stack*s){assert(s);assert(s-top0);//要删除元素个数不能为0.s-top--;}typeTop(stack*s){assert(s);assert(s-top0);returns-a[s-top-1];}boolEmpty(stack*s){assert(s);returns-top0;}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 topTop(str);Pop(str);//每次和栈顶元素比较后都要出栈才能和下一个栈顶元素比较if((top(*s!))||//不匹配(top{*s!})||(top[*s!])){Destroy(str);returnfalse;}}s;}//如果有多余的左括号就返回false没有就truebool retEmpty(str);Destroy(str);returnret;}