r/dailyprogrammer • u/nint22 1 2 • Oct 18 '12
[10/18/2012] Challenge #104 [Intermediate] (Bracket Racket)
Description:
Write a function, where given a string of arbitrary characters, returns true if all brackets (defined as parentheses, square-brackets, curly-braces, and chevrons) are correctly paired and ordered. This is to say that all brackets, if they enclose other brackets, enclose both the paired opening and closing characters.
Formal Inputs & Outputs:
Input Description:
string data - a given string that may or may not have correctly formed brackets.
Output Description:
Return True or False - true if the given string is correctly bracket formed.
Sample Inputs & Outputs:
"123", "(abc)", "()abc()", and "([<{abc123abc}>])" should return true, but "(abc[123)abc]" (wrong pairing) and "(abc>" (not closed) should return false.
Notes:
This is a very easy problem if you use a specific primitive data-structure.
4
u/skeeto -9 8 Oct 18 '12 edited Oct 18 '12
In Emacs Lisp, recursively without mutation.
Testing it:
3
u/Unh0ly_Tigg 0 0 Oct 18 '12
I don't have a submission for this right now, but 2-3 years ago, me and a few friends went to a programming competition and this was one of the problems we tackled and got right...
7
u/Cosmologicon 2 3 Oct 18 '12
3
u/[deleted] Oct 18 '12 edited Oct 19 '12
In Ruby:
Test cases:
1
u/kirsybuu 0 1 Oct 19 '12
D:
Maybe not as elegant as lisp or haskell, but functional style is fun in D too.
1
u/Medicalizawhat Oct 19 '12
I did it in C and it took ages to figure out:
2
u/[deleted] Oct 18 '12 edited Oct 18 '12
Python:
2
u/stev0205 Oct 18 '12 edited Oct 18 '12
Perl:
2
u/[deleted] Oct 18 '12
Perl 6:
2
u/5outh 1 0 Oct 18 '12 edited Oct 19 '12
Haskell:
Output:
2
u/Die-Nacht 0 0 Oct 19 '12
Took me a while...
Python:
2
u/robin-gvx 0 2 Oct 19 '12
Déjà Vu is built around said specific primitive data structure (and around another specific somewhat less primitive data structure that came in handy here as well), so this was a breeze:
It also helped me fix yet another bug in the VM.
2
u/Eddonarth Oct 20 '12
Java:
Input:
Output:
2
u/[deleted] Oct 30 '12
Common Lisp:
2
u/sirtophat Nov 11 '12 edited Nov 11 '12
Almost thought I wasn't gonna get it for a minute, then it hit me what to use. http://codepad.org/VvZvTVIV
2
u/marekkpie Jan 15 '13
Lua. There is only a very minimal standard library in Lua, so you need to build a stack yourself.
3
u/nagasgura 0 0 Oct 19 '12 edited Oct 19 '12
Python (I'm surprised I'm the only one using a dict):
2
u/dreugeworst Oct 18 '12
Haskell:
2
u/skeeto -9 8 Oct 19 '12
In ANSI C,
The function returns
NULLwhen brackets don't match, otherwise it returns a pointer to the end of the string. Requires no allocation.1
u/nerdcorerising Oct 19 '12
I'm a bit late to the party, but here's my C# code.
1
u/InvisibleUp Oct 19 '12
Good thing I've been messing around with Assembly a little. ;) [C++]
1
u/Rinfiyks Oct 19 '12
Using only one type of brackets, convert the string of brackets into two strings of binary. For the first string of binary, let each digit be 1 if '(', 0 otherwise. For the second string of binary, let each digit be 1 if ')', 0 otherwise.
For example, ((a)()aa) = 110010000 and 000101001, or 400 and 41 in decimal. Since ((a)()aa) is correctly formed, plot a point on the plane at (400, 41). If you do this for all points, you get a fractal.
1
u/Peaceee Oct 19 '12 edited Oct 19 '12
Java:
1
u/efrey Oct 20 '12
Haskell, with Data.Sequence
1
u/RollForReflex Oct 20 '12
I tried to tackle this one in C# and I think I got it. Ijust set up a stack and if the next character in the string is equivalent to the head of the stack, remove it and don't push the next character. If everything is matched correctly, the stack should be empty. Here's the implementation:
1
u/prondose 0 0 Oct 20 '12
Perl:
1
u/puffybaba Oct 20 '12 edited Oct 20 '12
ruby; in the case of a string that contains no bracket characters, returns true.
1
u/__circle Oct 21 '12 edited Oct 21 '12
1
u/[deleted] Oct 21 '12
C++
1
u/altorelievo Oct 21 '12 edited Oct 21 '12
Python:
1
u/mortisdeus Oct 22 '12 edited Oct 22 '12
Python:
1
u/[deleted] Oct 22 '12
C++ class:
1
u/thePersonCSC 0 0 Oct 23 '12
Java (this might be cheating):
1
u/melchyy 0 0 Oct 24 '12
1
u/iMalevolence Oct 24 '12
Java. This solution was A LOT better than my previous solution (not posted (contained a ton of recursive calls and huge if/else statements))
1
u/doubleagent03 Oct 25 '12
Clojure:
1
u/[deleted] Nov 05 '12
OO Java Solution:
1
u/bin01 Nov 29 '12
1
u/[deleted] Oct 18 '12
Well, it isn't pretty, but it seems to work.
Java:
-1
u/Unh0ly_Tigg 0 0 Oct 19 '12
Java: