题目描述:
括号序列由()[ ] { }组成,例如:([{()}])这样的序列是合法的,(}{)或者(}){这样的的序列是不合法的。
要求用程序实现:
(1)判断一个括号学列是否合法:boolean IsValidSeq(String input){}
(2)如果一个序列不合法,请加入最少的括号数,将这个学列变成合法的:String fixSeq(String input){}
分析:
(1)使用vector来存储括号序列,当遇到左边的括号就push_back(),当遇到右边的括号就判断最后一个是否与之匹配,
是,则继续判断;否则返回false。
bool isValidSeq(char* str) { char *input=str; if(input==NULL) return false; vector<char> v; while(*input!='\0') { if(v.size()<=0) { v.push_back(*input); }else { switch(*input) { case '{': case '(': case '[': v.push_back(*input); break; case '}': if(*(v.end()-1)=='{') { v.pop_back(); }else { return false; } break; case ')': if(*(v.end()-1)=='(') { v.pop_back(); }else { return false; } break; case ']': if(*(v.end()-1)=='[') { v.pop_back(); }else { return false; } break; } }// else input++; } if(v.size()>0) return false; else return true; }
(2)要使用最少的步骤,可参考(1),同样的思路,多加一个数组来存储匹配后的序列。
同样的判断,当不匹配的时候,就添加括号的另一半使之匹配,并存入数组。最后返回该数组。
char* fixSeq(char* str) { char *input=str; if(input==NULL) return false; vector<char> v; char *ret=new char[50]; int count=0; while(*input!='\0') { if(v.size()<=0) { v.push_back(*input); ret[count++]=*input; }else { switch(*input) { case '{': case '(': case '[': v.push_back(*input); ret[count++]=*input; break; case '}': if(*(v.end()-1)=='{') { v.pop_back(); ret[count++]='}'; }else { ret[count++]='{'; ret[count++]='}'; } break; case ')': if(*(v.end()-1)=='(') { v.pop_back(); ret[count++]=')'; }else { ret[count++]='('; ret[count++]=')'; } break; case ']': if(*(v.end()-1)=='[') { v.pop_back(); ret[count++]='['; }else { ret[count++]='['; ret[count++]=']'; } break; } } input++; } return ret; }
Reference:
http://blog.csdn.net/chenqin158741019/article/details/8149585