首页 > 代码库 > LeetCode Valid Parentheses 有效括号
LeetCode Valid Parentheses 有效括号
1 class Solution { 2 public: 3 void push(char c){ //插入结点 4 struct node *n=new struct node; 5 n->nex=0; 6 n->ch=c; 7 n->pre=last; 8 last->nex=n; 9 last=last->nex;10 }11 bool jud(char c){ //判断12 struct node *m;13 if(c==‘]‘)14 c=‘[‘;15 else if(c==‘}‘)16 c=‘{‘;17 else if(c==‘)‘)18 c=‘(‘;19 if(last->ch==c&&first.nex!=0){20 m=last;21 last=last->pre;22 delete m;23 last->nex=0;24 return 1;25 }26 else27 return 0;28 }29 bool isValid(string s) { //主判断函数30 char *p=&s[0];31 while(*p!=‘\0‘){32 if(*p==‘[‘ || *p==‘{‘ || *p==‘(‘)33 push(*p);34 else if(*p==‘]‘ || *p==‘}‘ || *p==‘)‘){35 if(jud(*p)==false) //判断错误36 return 0;37 }38 p++;39 }40 if(last==&first)41 return 1;42 else43 return 0; 44 }45 private: 46 struct node{ //结构体47 struct node *pre;48 struct node *nex;49 char ch;50 }first={0,0,0};51 struct node *last=&first; 52 53 };
题意：判断括号是否成对的出现，并且是合法的，类似判断一个算术式子中的括号有没有错一样。过滤掉非3种括号的其他字符。
思路：因为不知道这个string到底多大，可能很大，可能很小，所以我选择用盏（链表）来解决。一旦有不成对出现的，立刻就可以返回了。我这里用多两个函数将功能模块化，一个用于进盏，一个用于转化括号为另一半并判断。正常情况下结束时盏中应该空（我用last是否为链表头first来判断）。
注意：此题用STL和string类来解决应该更简单。代码量也会减少很多。
LeetCode Valid Parentheses 有效括号
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。