如何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）空间中解决这个问题吗？

Answer 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 /

Answer 2

参考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); } 

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

格式正确的括号的例子：

 ()[] {()[]} 

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

 ([)] {()[}] 

Answer 3

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

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

Answer 4

编辑：虽然简单，但这个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)所以没有真正的好处！

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

Answer 5

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

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

Answer 6

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

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

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

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

Answer 7

这是一个有效的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; } } 

Answer 8

Sbusidan的答案如下修改是O（ n ² ）时间复杂，但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); } 

Answer 9

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

喜欢这个：

 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的早期部分用作堆栈。

Answer 10

我知道我对这个派对有点晚了， 这也是我在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，我会把它留在这里，因为它实际上并不是不可能的，但它确实需要一些修改。

Answer 11

 /** * * @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; } } 

Answer 12

你可以使用两个指针来检查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落案件没有处理。

Answer 13

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

Answer 14

你可以提供这个值，并检查它是否有效，它会打印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(); } 

Answer 15

 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); }; 

Answer 16

使用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(); 

Answer 17

这是我解决问题的方法。 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; }