How to find the correctness of a string of parentheses, curly brackets and square brackets?

Question

I recently got in touch with this interesting issue. You are given a string containing only the characters '(' , ')' , '{' , '}' , '[' and ']' , for example, "[{()}]" , you need to write a function that checks the correctness of such an input line, the function may be like this:
bool isValid(char* s);
these brackets must be closed in the correct order, for example, "()" and "()[]{}" are valid, but "(]" , "([)]" and "{{{{" are not!

I came out with the following solution O (n) and O (n) of spatial complexity, which works fine:

• Maintain a character stack.
• Whenever you discover opening curly braces '(' , '{' OR '[' , push down on the stack.
• Whenever you find closing curly braces ')' , '}' OR ']' , check if the top of the stack matches the corresponding opening brace, if so, then place the stack, otherwise break the loop and return false.
• Repeat steps 2 to 3 until the end of the line.

This works, but we can optimize it for space, it can be a constant additional space, I understand that the time complexity cannot be less than O (n), because we have to look at each character.

So my question is: can we solve this problem in O (1) space?

Answer 1

Actually there is a deterministic log space algorithm due to Ritchie and Springsteel: http://dx.doi.org/10.1016/S0019-9958(72)90205-7 ( paywalled, sorry, not online). Since we need log bits to index the string, this is optimal for space.

---

If you agree to accept a one-sided error, then there is an algorithm that uses n polylog (n) time and polylog (n): http://www.eccc.uni-trier.de/report/2009/119/

Answer 2

As for the excellent answer from Matthieu M. , here is a C # implementation that seems to work just fine.

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

Essentially, all he does is remove the pairs of brackets until they are removed; if something remains, brackets are not formed.

Examples of well-formed parentheses:

 ()[] {()[]} 

Example of invalid brackets:

 ([)] {()[}] 

Answer 3

If the input is read-only, I don't think we can make O (1) space. It is well known that any decidable language of the space O (1) is regular (can be written as a regular expression). The string set that you have is not a common language.

Of course, this is a Turing machine. I would expect this to be true for fixed memory devices.

Answer 4

Edit: Although it is simple, this algorithm is actually O (n ^ 2) in terms of character mappings. To demonstrate this, you can simply generate the string as '(' * n + ')' * n .

I have a simple, though possibly erroneous, idea that I will submit to your criticism.

This is a destructive algorithm, which means that if you need a string, it will not help (since you will need to copy it).

Otherwise, the algorithm works with a simple index in the current row.

The idea is to remove the pairs one by one:

• ([{}()])
• ([()])
• ([])
• ()
• empty → OK

It is based on the simple fact that if we have the corresponding pairs, then at least one has the form () without any para-symbol between them.

Algorithm:

• i := 0
• Find the right pair from i . If none are found, the string is invalid. If it is found, let i be the index of the first character.
• Remove [i:i+1] from the line
• If i is at the end of the line and the line is not empty, this is a failure.
• If [i-1:i] is a matching pair, i := i-1 and back to 3.
• The rest is back to 1.

The O(n) algorithm is complex because:

• each loop iteration removes 2 characters from the string
• step 2., which is linear, is naturally related ( i cannot grow indefinitely)

And this is O(1) in space because only an index is required.

Of course, if you cannot afford to destroy the string, you will have to copy it, and this is O(n) in space, so there is no real benefit there!

Unless, of course, I’m mistaken somewhere ... and maybe someone could use the original idea (there is somewhere a couple) to improve the effect.

Answer 5

I doubt you will find a better solution, since even if you use internal functions to regex or count occurrences, they still have an O (...) cost. I would say your solution is the best :)

To optimize the space, you can do some encoding on your stack, but I doubt you will like it very much, unless {{{{{{{{{{}}}}}}}}}} .

Answer 6

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

Naturally solve this problem with the stack.

If only '(' and ')' are used, the stack is not needed. We just need to maintain the counter for the left unsurpassed '('. The expression is valid if the counter is always non-negative during the match and is zero at the end.

In the general case, although the stack is still necessary, the depth of the stack can be reduced by using a counter for unsurpassed braces.

Answer 7

This is the working Java code in which I filter out the brackets from the string expression and then check the correctness of the form, replacing the well-formed curly braces with zeros

Example input = (a+{b+c}-[de])+[f]-[g] FilterBrackets will output = ({}[])[][] Then I will check the correctness.

Comments are welcome.

 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

The next modification to the Sbusidan response is the O ( n ² ) time complex, but O (log n ) is simple.

 #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

If you can rewrite the input string (not reasonable in the use cases that I imagine, but what the hell ...), you can do it in constant space, although I believe that the need for time goes up to O (n ² ) .

Like this:

 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 

The essence of this is to use the early part of the input as a stack.

Answer 10

I know I'm a little late for this party; this is also my very first post on StackOverflow.

But when I looked through the answers, I thought that I could come up with a better solution.

So my solution is to use multiple pointers.
It should not even use RAM memory, since registers can be used for this.
I have not tested the code; he wrote it on the fly.
You will need to correct my typos and debug it, but I believe that you will get this idea.

Memory usage: in most cases, only the central processor is registered.
CPU usage: it depends, but about twice as much time spent reading a line. Changes memory: None.

b: string b eginning, e: string e nd.
l: l position eft, r: r position.
c: c har, m: m atch char

if r reaches the end of the line, we are successful.
l goes back from r to b.
Whenever r meets a new start type, set l = r.
when l reaches b, we are done with the block; go to the beginning of the next block.

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

After thinking about this approach for a while, I realized that it will not work as it is now.
The problem will be that if you have "[() ()]", it will not succeed when reaching "]".
But instead of deleting the proposed solution, I will leave it here, since it is actually not impossible to make it work, but it requires some modification.

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

Instead of pushing curly brackets onto the stack, you can use two pointers to check the characters of a string. one starts at the beginning of the line and the other starts at the end of the line. something like

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

Please note that some corner cases are not processed.

Answer 13

I think you can implement the O (n) algorithm. You just have to initialize the counter variable for each type: curly, square and regular brackets. After that, you must iterate over the string and must increase the counter if the bracket is open, otherwise, to decrease it. If the counter is negative, return false. AfterI think you can implement the O (n) algorithm. You just have to initialize the counter variable for each type: curly, square and regular brackets. After that, you must iterate over the string and must increase the counter if the bracket is open, otherwise, to decrease it. If the counter is negative, return false. After you count all the brackets, you should check if all the counters are equal. In this case, the string is correct and you must return true.

Answer 14

This is my solution to the problem. O (n) is the complexity of time without the complexity of space. Code in 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; } 

Answer 15

You can specify a value and check if it is valid, it will print YES, otherwise it will print 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 16

 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 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 after the nest if (test.pos.length && !recursiveCheck(test.pos)) return false; // recursive checks what 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 17

Using C # OOPS Programming ... Small and Simple Solution

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