如何find一串括号,大括号和方括号的有效性?

我最近接触到这个有趣的问题。 给你一个只包含字符'('')''{''}''['']'的string,例如"[{()}]" ,你需要写一个函数会检查这个inputstring的有效性,函数可能是这样的:
bool isValid(char* s);
这些括号必须以正确的顺序closures,例如"()""()[]{}"都是有效的,但是"(]""([)]""{{{{"不是!

我出来以下O(n)时间和O(n)空间复杂性解决scheme,它工作正常:

  1. 保持一堆字符。
  2. 每当你发现开放大括号'(''{''['推到堆栈上。
  3. 每当你发现右括号')''}'']' ,检查堆栈顶部是否对应的左括号,如果是,则popup堆栈,否则打破循环并返回false。
  4. 重复步骤2 – 3,直到string结束。

这个工作,但我们可以优化它的空间,可能是恒定的额外空间,我明白,时间复杂性不能小于O(n),因为我们必须看每一个字符。

所以我的问题是我们可以在O(1)空间中解决这个问题吗?

实际上,由于Ritchie和Springsteel有一个确定性的对数空间algorithm: http : //dx.doi.org/10.1016/S0019-9958 ( 72 ) 90205-7支付宝,抱歉不在线)。 由于我们需要logging位来索引string,所以这是空间最优的。


如果你愿意接受单方面的错误,那么有一个algorithm使用n polylog(n)time和polylog(n)空间: http : //www.eccc.uni-trier.de/report/2009/119 /

参考Matthieu M.的优秀答案,这里是C#中的一个实现,它似乎很好地工作。

 /// <summary> /// Checks to see if brackets are well formed. /// Passes "Valid parentheses" challenge on www.codeeval.com, /// which is a programming challenge site much like www.projecteuler.net. /// </summary> /// <param name="input">Input string, consisting of nothing but various types of brackets.</param> /// <returns>True if brackets are well formed, false if not.</returns> static bool IsWellFormedBrackets(string input) { string previous = ""; while (input.Length != previous.Length) { previous = input; input = input .Replace("()", String.Empty) .Replace("[]", String.Empty) .Replace("{}", String.Empty); } return (input.Length == 0); } 

从本质上讲,它所做的只是删除成对的括号,直到没有剩下要删除; 如果有什么留下的方括号不正确的形成。

格式正确的括号的例子:

 ()[] {()[]} 

格式不正确的括号的例子:

 ([)] {()[}] 

如果input是只读的,我不认为我们可以做O(1)空间。 任何O(1)空间可判定的语言都是规则的(即作为正则expression式可写)是众所周知的事实。 你有的string不是一个正规的语言。

当然,这是关于一个图灵机。 我也希望固定字RAM机也是如此。

编辑:虽然简单,但这个algorithm实际上是O(n ^ 2)的字符比较。 为了演示它,可以简单地生成一个string为'(' * n + ')' * n

我有一个简单的,但也许是错误的想法,我会服从你的批评。

这是一个破坏性的algorithm,这意味着如果你需要这个string,它不会有帮助(因为你需要把它复制下来)。

否则,该algorithm在当前string中使用简单的索引。

这个想法是一个接一个地去除一对:

  1. ([{}()])
  2. ([()])
  3. ([])
  4. ()
  5. empty – > OK

它基于一个简单的事实,即如果我们有匹配的对,那么至less有一个是()没有任何对的字符。

algorithm:

  1. i := 0
  2. ifind一对匹配。 如果没有find,那么string是无效的。 如果find了,让i成为第一个字符的索引。
  3. 从string中删除[i:i+1]
  4. 如果i在string的末尾,而string不是空的,这是一个失败。
  5. 如果[i-1:i]是一个匹配对, i := i-1并返回到3。
  6. 否则,回到1。

该algorithm的复杂性是O(n) ,因为:

  • 循环的每次迭代都会从string中删除2个字符
  • 第二步是线性的,是自然界的( i不能无限增长)

而且它在空间中是O(1) ,因为只需要索引。

当然,如果你不能摧毁string,那么你将不得不复制它,这是太空O(n)所以没有真正的好处!

当然,除非我深深地误以为是某个地方,也许有人可以用最初的想法(有一对)来取得更好的效果。

我怀疑你会find一个更好的解决scheme,因为即使你使用内部函数正则expression式或计数发生,他们仍然有一个O(…)的成本。 我会说你的解决scheme是最好的:)

为了优化空间,你可以在你的堆栈上做一些行程编码,但是我怀疑它会给你带来什么,除了{{{{{{{{{{}}}}}}}}}}

http://www.sureinterview.com/shwqst/112007

用堆栈解决这个问题是很自然的。

如果只使用'('和')',则堆栈不是必需的。 我们只需要为不匹配的left(')保留一个计数器,如果计数器在比赛期间总是非负的,则expression式是有效的,并且在结束时为零。

在一般情况下,虽然堆叠仍然是必要的,但堆叠的深度可以通过使用不匹配的支架的计数器来减less。

这是一个有效的java代码,我从stringexpression式中过滤出括号,然后通过用空值

示例input = (a+{b+c}-[de])+[f]-[g] FilterBrackets将输出= ({}[])[][]然后我检查格式。

评论欢迎。

 public class ParanString { public static void main(String[] args) { String s = FilterBrackets("(a+{b+c}-[de])[][]"); while ((s.length()!=0) && (s.contains("[]")||s.contains("()")||s.contains("{}"))) { //System.out.println(s.length()); //System.out.println(s); s = s.replace("[]", ""); s = s.replace("()", ""); s = s.replace("{}", ""); } if(s.length()==0) { System.out.println("Well Formed"); } else { System.out.println("Not Well Formed"); } } public static String FilterBrackets(String str) { int len=str.length(); char arr[] = str.toCharArray(); String filter = ""; for (int i = 0; i < len; i++) { if ((arr[i]=='(') || (arr[i]==')') || (arr[i]=='[') || (arr[i]==']') || (arr[i]=='{') || (arr[i]=='}')) { filter=filter+arr[i]; } } return filter; } } 

Sbusidan的答案如下修改是O( n 2 )时间复杂,但O(log n )空间简单。

 #include <stdio.h> #include <string.h> #include <stdbool.h> char opposite(char bracket) { switch(bracket) { case '[': return ']'; case '(': return ')'; } } bool is_balanced(int length, char *s) { int depth, target_depth, index; char target_bracket; if(length % 2 != 0) { return false; } for(target_depth = length/2; target_depth > 0; target_depth--) { depth=0; for(index = 0; index < length; index++) { switch(s[index]) { case '(': case '[': depth++; if(depth == target_depth) target_bracket = opposite(s[index]); break; case ')': case ']': if(depth == 0) return false; if(depth == target_depth && s[index] != target_bracket) return false; depth--; break; } } } } void main(char* argv[]) { char input[] = "([)[(])]"; char *balanced = is_balanced(strlen(input), input) ? "balanced" : "imbalanced"; printf("%s is %s.\n", input, balanced); } 

如果你可以覆盖inputstring(在我设想的用例中是不合理的,但到底是什么…),你可以在恒定的空间中完成,尽pipe我相信时间需求上升到O(n 2

喜欢这个:

 string s = input char c = null int i=0 do if s[i] isAOpenChar() c = s[i] else if c = isACloseChar() if closeMatchesOpen(s[i],c) erase s[i] while s[--i] != c ; erase s[i] c == null i = 0; // Not optimal! It would be better to back up until you find an opening character else return fail end if while (s[++i] != EOS) if c==null return pass else return fail 

这样做的实质是将input的早期部分用作堆栈。

我知道我对这个派对有点晚了, 这也是我在StackOverflow上的第一篇文章。

但是当我看到答案的时候,我想我可能会想出一个更好的解决scheme。

所以我的解决scheme是使用几个指针。
它甚至不需要使用任何RAM存储器,因为可以使用寄存器。
我没有testing代码; 它是在飞行中写的。
你需要解决我的错误,并debugging它,但我相信你会明白的。

内存使用情况:大多数情况下只有CPU注册。
CPU使用率:取决于,但大约是读取string所用时间的两倍。
修改内存:不。

b:stringeginning,e:stringend。
l:左右位置,r:右侧位置。
c: c har,m: m atch char

如果r到达string的末尾,我们就成功了。
我从r朝b后退
只要r满足新的开始types,设置l = r。
当我到达b,我们完成了块; 跳到下一个块的开始。

 const char *chk(const char *b, int len) /* option 2: remove int len */ { char c, m; const char *l, *r; e = &b[len]; /* option 2: remove. */ l = b; r = b; while(r < e) /* option 2: change to while(1) */ { c = *r++; /* option 2: if(0 == c) break; */ if('(' == c || '{' == c || '[' == c) { l = r; } else if(')' == c || ']' == c || '}' == c) { /* find 'previous' starting brace */ m = 0; while(l > b && '(' != m && '[' != m && '{' != m) { m = *--l; } /* now check if we have the correct one: */ if(((m & 1) + 1 + m) != c) /* cryptic: convert starting kind to ending kind and match with c */ { return(r - 1); /* point to error */ } if(l <= b) /* did we reach the beginning of this block ? */ { b = r; /* set new beginning to 'head' */ l = b; /* obsolete: make left is in range. */ } } } m = 0; while(l > b && '(' != m && '[' != m && '{' != m) { m = *--l; } return(m ? l : NULL); /* NULL-pointer for OK */ } 

在思考了一段时间之后,我意识到现在不行。
问题是如果你有“[()()]”,到达']'就会失败。
但是,不要删除build议的解决scheme,我会把它留在这里,因为它实际上并不是不可能的,但它确实需要一些修改。

 /** * * @author madhusudan */ public class Main { /** * @param args the command line arguments */ public static void main(String[] args) { new Main().validateBraces("()()()()(((((())))))()()()()()()()()"); // TODO code application logic here } /** * @Use this method to validate braces */ public void validateBraces(String teststr) { StringBuffer teststr1=new StringBuffer(teststr); int ind=-1; for(int i=0;i<teststr1.length();) { if(teststr1.length()<1) break; char ch=teststr1.charAt(0); if(isClose(ch)) break; else if(isOpen(ch)) { ind=teststr1.indexOf(")", i); if(ind==-1) break; teststr1=teststr1.deleteCharAt(ind).deleteCharAt(i); } else if(isClose(ch)) { teststr1=deleteOpenBraces(teststr1,0,i); } } if(teststr1.length()>0) { System.out.println("Invalid"); }else { System.out.println("Valid"); } } public boolean isOpen(char ch) { if("(".equals(Character.toString(ch))) { return true; }else return false; } public boolean isClose(char ch) { if(")".equals(Character.toString(ch))) { return true; }else return false; } public StringBuffer deleteOpenBraces(StringBuffer str,int start,int end) { char ar[]=str.toString().toCharArray(); for(int i=start;i<end;i++) { if("(".equals(ar[i])) str=str.deleteCharAt(i).deleteCharAt(end); break; } return str; } } 

你可以使用两个指针来检查string的字符,而不是将大括号放入堆栈。 一个从string的开头开始,另一个从string的结尾开始。 就像是

 bool isValid(char* s) { start = find_first_brace(s); end = find_last_brace(s); while (start <= end) { if (!IsPair(start,end)) return false; // move the pointer forward until reach a brace start = find_next_brace(start); // move the pointer backward until reach a brace end = find_prev_brace(end); } return true; } 

请注意,有一些angular落案件没有处理。

我认为你可以实现一个O(n)algorithm。 只需要为每个types初始化一个计数器variables:curl,方形和正常的括号。 之后,你应该迭代string,并应增加相应的计数器,如果括号被打开,否则减less它。 如果计数器为负,则返回false。 之后我认为你可以实现一个O(n)algorithm。 只需要为每个types初始化一个计数器variables:curl,方形和正常的括号。 之后,你应该迭代string,并应增加相应的计数器,如果括号被打开,否则减less它。 如果计数器为负,则返回false。 统计完所有括号后,您应该检查所有计数器是否为零。 在这种情况下,string是有效的,你应该返回true。

你可以提供这个值,并检查它是否有效,它会打印YES,否则会打印NO

 static void Main(string[] args) { string value = "(((([{[(}]}]))))"; List<string> jj = new List<string>(); if (!(value.Length % 2 == 0)) { Console.WriteLine("NO"); } else { bool isValid = true; List<string> items = new List<string>(); for (int i = 0; i < value.Length; i++) { string item = value.Substring(i, 1); if (item == "(" || item == "{" || item == "[") { items.Add(item); } else { string openItem = items[items.Count - 1]; if (((item == ")" && openItem == "(")) || (item == "}" && openItem == "{") || (item == "]" && openItem == "[")) { items.RemoveAt(items.Count - 1); } else { isValid = false; break; } } } if (isValid) { Console.WriteLine("Yes"); } else { Console.WriteLine("NO"); } } Console.ReadKey(); } 
 var verify = function(text) { var symbolsArray = ['[]', '()', '<>']; var symbolReg = function(n) { var reg = []; for (var i = 0; i < symbolsArray.length; i++) { reg.push('\\' + symbolsArray[i][n]); } return new RegExp('(' + reg.join('|') + ')','g'); }; // openReg matches '(', '[' and '<' and return true or false var openReg = symbolReg(0); // closeReg matches ')', ']' and '>' and return true or false var closeReg = symbolReg(1); // nestTest matches openSymbol+anyChar+closeSymbol // and returns an obj with the match str and it's start index var nestTest = function(symbols, text) { var open = symbols[0] , close = symbols[1] , reg = new RegExp('(\\' + open + ')([\\s\\S])*(\\' + close + ')','g') , test = reg.exec(text); if (test) return { start: test.index, str: test[0] }; else return false; }; var recursiveCheck = function(text) { var i, nestTests = [], test, symbols; // nestTest with each symbol for (i = 0; i < symbolsArray.length; i++) { symbols = symbolsArray[i]; test = nestTest(symbols, text); if (test) nestTests.push(test); } // sort tests by start index nestTests.sort(function(a, b) { return a.start - b.start; }); if (nestTests.length) { // build nest data: calculate match end index for (i = 0; i < nestTests.length; i++) { test = nestTests[i]; var end = test.start + ( (test.str) ? test.str.length : 0 ); nestTests[i].end = end; var last = (nestTests[i + 1]) ? nestTests[i + 1].index : text.length; nestTests[i].pos = text.substring(end, last); } for (i = 0; i < nestTests.length; i++) { test = nestTests[i]; // recursive checks what's after the nest if (test.pos.length && !recursiveCheck(test.pos)) return false; // recursive checks what's in the nest if (test.str.length) { test.str = test.str.substring(1, test.str.length - 1); return recursiveCheck(test.str); } else return true; } } else { // if no nests then check for orphan symbols var closeTest = closeReg.test(text); var openTest = openReg.test(text); return !(closeTest || openTest); } }; return recursiveCheck(text); }; 

使用c#OOPS编程…小而简单的解决scheme

 Console.WriteLine("Enter the string"); string str = Console.ReadLine(); int length = str.Length; if (length % 2 == 0) { while (length > 0 && str.Length > 0) { for (int i = 0; i < str.Length; i++) { if (i + 1 < str.Length) { switch (str[i]) { case '{': if (str[i + 1] == '}') str = str.Remove(i, 2); break; case '(': if (str[i + 1] == ')') str = str.Remove(i, 2); break; case '[': if (str[i + 1] == ']') str = str.Remove(i, 2); break; } } } length--; } if(str.Length > 0) Console.WriteLine("Invalid input"); else Console.WriteLine("Valid input"); } else Console.WriteLine("Invalid input"); Console.ReadKey(); 

这是我解决问题的方法。 O(n)是时间的复杂性,没有空间的复杂性。 代码在C.

 #include <stdio.h> #include <string.h> #include <stdbool.h> bool checkBraket(char *s) { int curly = 0, rounded = 0, squre = 0; int i = 0; char ch = s[0]; while (ch != '\0') { if (ch == '{') curly++; if (ch == '}') { if (curly == 0) { return false; } else { curly--; } } if (ch == '[') squre++; if (ch == ']') { if (squre == 0) { return false; } else { squre--; } } if (ch == '(') rounded++; if (ch == ')') { if (rounded == 0) { return false; } else { rounded--; } } i++; ch = s[i]; } if (curly == 0 && rounded == 0 && squre == 0){ return true; } else { return false; } } void main() { char mystring[] = "{{{{{[(())}}]}}}"; int answer = checkBraket(mystring); printf("my answer is %d\n", answer); return; }