# Fun with Matching Braces [duplicate]

The contest is to make a program or function that takes an arbitrary string resembling source code and checks to see if the "braces" follow the basic rules for brace matching. That is, the number of left braces and right braces have to match, and you can't have a right brace without a corresponding prior left brace.

You may choose to use any "brace" among ( [ { <

Your program must output/return a true-y value or 'Y' if the input is legal and a false-y value or 'N' if the input is illegal.

Scoring

Your score is the number of bytes in your source minus bonuses.

Bonuses

• -20 per each additional brace type handled among ( [ { <
• -30 if you handle multiple brace types and don't allow mismatched braces like <(>)
• -50 points if you handle /* */ or // comments (the same way C or Java does)
• -20 points if you handle both types of comments
• -50 if you ignore braces inside ' and " quotes. To get the points you also have to check that quotes properly match. Eg: ("')"') is not a valid "program" but ("')") is. You do not have to worry about escaped characters. "\"" is an illegal program if you go for this bonus.

So if your program is 327 ASCII characters long, handles ( and [, doesn't check mismatching, and handles // comments and quotes, you get:

327 - 20 * 1 - 0 - 50 - 0 - 50 = 207 points

EDIT: Added bonuses for ignoring braces inside ' and " quotes
EDIT 2: Return values cannot be any string. Must be true/false 1/0 'Y'/'N' ect.
EDIT 3: Since there is some confusion, here is some pseudo-BNF to give an idea of what is expected.

Grammar for minimal program:
exprs = expr exprs
expr = ( exprs ) || not_braces* || nil

Grammar for all bonuses:
exprs = expr exprs
expr = ( exprs ) || [ exprs ] || { exprs } || < exprs > || // not_newline* \n || /* not_end_comment* */ || not_braces* || nil

Note that if you do the bonuses, you will both accept and reject things that the basic program would not.

• How should we handle braces in string literals, like "Hel(o"? I assume they should be handled like your -50 for comments, but you don't specify that. – Danny Feb 20 '14 at 18:42
• @Danny Ugh, I should have known I'd forget something. Sure, let's add that. – aebabis Feb 20 '14 at 18:46
• Stack based languages may be particularly good at this – Cruncher Feb 20 '14 at 21:48
• your grammars look good, but the first paragraph makes it sound like [(]) is valid – Sparr Oct 4 '15 at 1:37
• @Sparr The first paragraph only applies to a program without bonuses, in which case your example is valid. Your program only needs to reject that example if you want the bonus -30. – aebabis Oct 4 '15 at 1:42

# Perl, (136130 129 chars - (20*3) - 30 - 50 - 20 - 50) == -81

<3 recursive REs.

$/=$_;print!(<>!~m#^(([^][<{('"/)}>]|'[^']*'|"[^"]*"|/((?![*/])|\*((?!\*/).)*\*/|/[^\n]*+)|<(?1)>|$$(?1)$$|$(?1)]|{(?1)})*)#s)  • You can shorten this by clearing / to avoid joining, by changing <STDIN> to <> (which reads from STDIN unless a file name is passed on the command line), and by outputting an empty string (which should count as false-y) in the output if the match fails: to /=_;_=<>;print!!m#...#. – hvd Feb 21 '14 at 21:54 • Congratulations – aebabis Mar 3 '14 at 20:16 ## PHP, -4 (156 - 20*3 - 30 - 50 - 20) <?php x=preg_replace("!(//.*|/\*.*\*/|[^()[${}<>])!sm",'',$argv[1]);while(strlen($x)!=strlen($x=str_replace(str_split('()[]{}<>',2),'',$x)));print $x?0:1;  1. It removes comments 2. It filters out all characters different than (, ), [, ], {, }, <, > 3. It replaces all (), [], {}, <> pairs until there are no matches 4. Prints 1 if the string is empty, 0 otherwise (Edit: changed the regex; the source code is now 156 instead of 175) # GolfScript, 38 chars − 3 × 20 − 30 = −52 points 0\{")]>}([<{"?.4/"4^^{0}* ;"n/=~}/;]!  Prints 1 if all the braces in the input are correctly balanced, 0 otherwise. Bonus points for: • handling all four types of braces: 3 × 20 points • not allowing mismatched braces: 30 points This solution uses the GolfScript internal stack to keep track of which braces have been seen so far. When an opening brace is encountered, it is pushed onto the stack; when a closing brace is encountered, the code checks if there's a matching opening brace on the stack. If there is, it is popped off; otherwise a sentinel value (0) matching no brace is push onto the stack, ensuring that it cannot ever be popped off. One such sentinel value is pushed onto the stack at the beginning, to guard against stack underflow if there are too many closing braces. At the end, the program simply checks whether the stack is empty except for the initial sentinel value. # Lua - 51 print(not not("("..io.read"*a"..")"):match"^%b()$")


What this program is doing, is wrapping the input string in (), then it matches it against a pattern (not a regex). The pattern matches beginning of string followed by string containing balanced parentheses, followed by end of string.
On a successful match, the whole string is returned, which is turned into true by not not. If match is unsuccessful, nil is returned, which turns info false because of not not.

• Don't forget to add your explanation. – Justin Feb 20 '14 at 19:53
• @Quincunx done (comment too short) – mniip Feb 20 '14 at 19:58

## C, 7062 61

A;main(c){for(;~c&~A;c=getchar())A-=c==41,A+=c==40;exit(!A);}


Alternatively, supporting all bracket types: 147 - (3*20) = 87

A,B,C,D;main(c){for(;~(c=getchar())&~A&~B&~C&~D;)c-40?c-41?c-91?c-93?c-'{'?c-'}'?c-60?c-62||D--:D++:C--:C++:B--:B++:A--:A++;puts(A|B|C|D?"N":"Y");}


The program reads in a single character at a time. Every time a ( is found a counter is incremented. Similarly, every time a ')' is found a counter is decremented. If the counter ever drops below 0, we know a ) was found without a prior (. When we reach EOF, if the counter equals 0, we have success!

EDIT: A big thanks to @ugoren!

• ~c&~A is great. But c=~getchar() can save parentheses (but requires some changes, I think it can help). A-=c==41 can save one. – ugoren Feb 20 '14 at 22:27
• Thanks! A-=c==41 really helped reduce the character count. I'll play around a bit, but getting rid of the parens really kills the evaluation order...not sure how to get around that right now. – Josh Feb 20 '14 at 22:50

## Common Lisp (???)

The idea here was to highlight the flexibiliity of the Lisp reader and actually allow other characters as list delimiters. Unfortunately, it seems like too much of the other parts of the language syntax (e.g., using 'foo as an abbreviation for (quote foo) and different comment syntaxes (; rather than // for end-of-line comments, and #| … |# instead of /* … */)) probably disqualify this from being a "working" entry.

(defun check-source (x)
(labels ((s (x y)
(set-macro-character x y))
(r (e)
(s e (get-macro-character #\) nil))
(lambda (s c)
(read-delimited-list e s t)))
(p (b e)
(s b (r e))))
(map 'nil #'p "[{<" "]}>")
(listp (read-from-string (concatenate 'string "(" x ")")))))

(defun check-source(x)(labels((s(x y)(set-macro-character x y))(r(e)(s e(get-macro-character #)()))(lambda(s c)(read-delimited-list e s t)))(p(b e)(s b(r e))))(map'nil #'p"[{<""]}>")(listp(read-from-string(concatenate'string"("x")")))))


This uses the standard Lisp reader (which already handles ( and ), of course), and defines each new set of a delimiters as another list construction syntax. These are automatically matched (i.e., mismatches result in an error). This doesn't handle /* ... */ and // comments, but it handles #| ... |# and // comments. Double quoted strings are handled, including escapes.

• Nice work. While I did add the quotes bonus after posting, I am hesitant to change the rules again. I intentionally made the parse rules for this problem not match any real language so that some contestants would write their own scanner. You get the -20, the -30, and the -50 for // comments, but not the -20 for /**/ comments or the -50 for quotes. The last bonus was intended to add substantially more difficulty. – aebabis Feb 20 '14 at 21:08
• @acbabis Oh, I misread; it's -50 for // and another -50 for /* */? – Joshua Taylor Feb 20 '14 at 21:10
• No, you were right the first time. Its -70 total for both. – aebabis Feb 20 '14 at 21:13
• Is there any way you can ignore #| ... |# comments? You need to do that to qualify. Perhaps run the input through a RegEx before parsing? – aebabis Feb 20 '14 at 21:19
• What do you mean "ignore" #| ... |# comments? They're already ignored (since they're comments). If you mean "don't treat them as comments", then I'd rather not do that, since the task is to accept an "arbitrary string resembling source code", and something like #| ok, here's where the magic happens... |# (setf *special-character #\@) does resemble source code. – Joshua Taylor Feb 20 '14 at 21:20

## GolfScript 37

{[40.)]&},.,,\{\>}+%{0\~}%(!\{0<},!&


Suppose the input to the program is '(123(abc)(hello))'. First, filter out all characters that are not ( (ASCII 40) or ) (ASCII 41):

{[40.)]&},  #Stack is now '(()())'


Next, generate an array from 0 to the length of the array:

.,, #Stack is now '(()())' [0, 1, 2, 3, 4, 5]


Now, generate all suffixes of the filtered string

\{\>}+% #Stack is now ['(()())', '()())', ')())', '())', '))', ')' ]


Recall that in GolfScript, ( decrements integers and ) increments them.

So, checking if the parentheses are valid is equivalent to checking if that no suffix, when treated as a code block and applied to 0, dips below 0 (so that there are more close braces than open braces) and that the whole string, when treated as a code block and applied to 0, return 0 (so that there is an equal number of open and close parenthesis).

So, apply each suffix to 0:

{0\~}% #Stack is now [0, 1, 2, 1, 2, 1]


And then check that the first element (where the entire string treated as a function) returns 0, and that no elements are below 0 (recall that the empty array [] is falsey in GolfScript):

 (!\{0<},!&

• Remember to add an explanation. – Justin Feb 20 '14 at 20:47
• @Quincunx Done! – Ben Reich Feb 20 '14 at 21:07

## flex, (70+4)-50=24

%{
a;
%}
%%
"(" a++;
")" a?a--:exit(0);
"//".*
.
<<EOF>> exit(!a);
%%


In order for compilation to succeed, you need to use flag -lfl so I added 4 to my character count.

flex flex.l
gcc lex.yy.c -lfl


The code reads character by character, incrementing a counter if a ( is detected and decrementing a counter if a ) is detected. If the counter is zero when a ) is detected, then we know we don't have a matching ( and can exit. Simple // comments are matched (and ignored) via a regular expression for the minus fifty bonus.

# Bash: 369 bytes - 110 bonus = 259

e=exit;function f(){ s=$1;a=X;until [ "$a" = "" ];do a=${s::1};s=${s:1}
if [ "$a" = $$];then f "s"$$||$e 1
elif [ "$a" = [ ];then f "$s" ]||$e 1 elif [ "$a" = \< ];then f "$s" \>||$e 1
elif [ "$a" = { ];then f "$s" }||$e 1 elif [ "$a" = \) ]||[ "$a" = ] ]||[ "$a" = \> ]||[ "$a" = } ] then [$a = "$2" ]&&return||$e 1;fi;done;[ "$2" = "" ]||$e 1;};f "$1"&&$e 0||$e 1  Scoring: • Handles all four brace types, 4x -20 = -80 • handles mismatched brackets, -30 There's probably room to further golf the chain of elifs into && and ||'s, but some odd behaviour started creeping in when I tried so I gave up :) • Suggested an edit for the part you gave up on (and fixed a bug) – Isiah Meadows Feb 25 '14 at 6:34 • I'm afraid your edit is incorrect - it throws line 1: syntax error near unexpected token done' – Riot Feb 25 '14 at 12:22 ## Javascript: 392383387 345 characters - 210 bonus = 135 points function x(a){z=1;k="",a=a.replace(/\/\*.*?\*\/|\/\/.*?\n|".*?"|'.*?'/mg,"").split('');try{for(d in a){eval("c=a[d]//%(')k='(%[')k='[%{')k='{%<')k='<%)_(#%]_[#%}_{#%>_<#".replace(/#/g,"')k=k.substr(1);else z=0//").replace(/%/g,"'+k\nif(c=='").replace(/_/g,"')if(k.charAt(0)=='"))}}catch(e){z=0}return''==k&z==1&a.indexOf("'")<0&a.indexOf('"')<0}  It is a function that returns 0 if the input is not valid and 1 if it is. First, it uses regular expressions to remove the /* ... */, // ... \n, ' ... ' and " ... " sequences. Second, it decompresses and run a code that iterates the input string, char-by-char, looking for (, [, { and <, stacking them into a string k. When he founds ), ], } and >, it looks the top of the stack and if they match, he pops the stack, otherwise he sets a variable z to zero. If any exception happens, z is set to zero. In the end, he checks if the stack is empty and no ' or " are left, returning 1 if this is the case and 0 otherwise. Thanks to @Charles for pointing out bugs in earlier versions. • looks like your regexes are greedy, so they'll return true for somehting like: (/*abc*/) def*/). Aside from that, that'd pretty much be my algorithm – Not that Charles Feb 21 '14 at 1:52 • @Charles Fixed. Thank you. – Victor Stafusa Feb 21 '14 at 2:04 • Also, I think the following would fail: ('a quote " in apostrophes!') "and two quotes out of them" – Not that Charles Feb 21 '14 at 4:24 • @Charles Thank you. Fixed and reduced it more 42 characters. – Victor Stafusa Feb 21 '14 at 4:55 # JavaScript (ES6), 92 115 Bytes Oh look, I beat the other JavaScript answer without any bonuses. c=s=>{d=0;s=s.split("");for(z=0;z<s.length;z++){if(s[z]=="{")d++;if(s[z]=="}")--d;if(d<0)a="N"}return a||d?"N":"Y"}  Ungolfed, dev-friendly, and ES5-(-friendly) version: function check(str){ depth = 0; str = str.split(""); for(var z=0;z<str.length;z++){ if(str[z]=="{") str[z]+=depth++; if(str[z]=="}") str[z]+=--depth; if(depth<0) return "unmatched"; } return depth; }  Returns a version of the string with the "depth" of the bracket afterword. I am using this function for evaluation purposes. I might try for some bonuses later. • All this does is make sure the number of { is equal to the number of }; you need to make sure the running sum never gets below 0 to ensure braces are matched. e.g. {}}{ wouldn't be matched. – lirtosiast Oct 4 '15 at 1:42 • @ThomasKwa Oversight on my part. Thanks. – Conor O'Brien Oct 4 '15 at 1:43 # Bash - 4 chars cc f  Assuming f is your c source code file If you want it to print 'yes' or 'no', 43 chars: cc f;if$?=0;then echo yes;else echo no;fi

• doesn't this check more than just matched braces? – John Dvorak Feb 20 '14 at 18:53
• Also, it won't compile (<>), so no dice – aebabis Feb 20 '14 at 18:55
• All this does is try to compile it as C source code – TheDoctor Feb 20 '14 at 19:05
• @TheDoctor ...but it doesn't meet any of the requirements or bonuses :/ – aebabis Feb 20 '14 at 19:13
• cc f;if $?=0;then echo yes;else echo no;fi = cc f && echo yes || echo no, assuming the if had [ in the first place. – Shahbaz Feb 20 '14 at 20:01 # Python 2.7: 171 bytes - 60 - 30 = 81 points import sys b=[] for c in sys.stdin.read(): if c in '([{<':b+=[c] if c in ')]}>': if b[-1]!='([{<'[list(')]}>').index(c)]:print 0==1;break b.pop() else:print len(b)==0  Handles all bracket types and doesn't allow mismatched brackets. • Good work. The -80 bonus should be -60 because handling 1 brace type is required. – aebabis Feb 20 '14 at 19:15 • Bah, you're right. I can't math. – undergroundmonorail Feb 20 '14 at 19:16 ## VB.net 93c This check to see if BrainF*ck code has balanced square braces. Function(c$)c.Aggregate(Of Int32)(0,Function(s,i)If(s<0,s,If(i="["c,s+1,If(i="]"c,s-1,s))))=0


## Perl, 106 bytes − (3*20 + 30 + 50 + 0 + 0) bonus = −34 points

$_=join"",<>;$a='[^()<>{}[\]]*';while(s|//.*||+s/$$a$$//+s/$a]//+s/{a}//+s/<a>//){}exit!/[()<>{}[$]/


Input is expected from STDIN (multiple lines) and the return is given as exit code, 1 for successful validation and 0 for unmatched braces. Example for calling:

perl bracevalidator.pl<inputfile;echo $?  The following is supported/validated: • Balanced braces: (..), <..>, {..}, [..]. • No mismatch for different brace types. • C++ style comments //. The idea is to match the innermost balanced braces first and removes them from the string until all brace pairs are gone. If a brace is left, then the return value is 0, otherwise all braces are properly nested and 1 is returned. First the whole file is read in variable $_:

$_join'',<>;  Variable $a serves as abbreviation for the brace free stuff between an innermost brace pair:

\$a='[^()<>{}[\]]*';


The main loop removes the C++ comments and the brace pairs bottom-up:

while(s|//.*||+s/$$a$$//+s/$a]//+s/{a}//+s/<a>//){}  Then the remaining string is checked for any remaining brace: exit!/[()<>{}[$]/


C# - 380 characters

Continuously reads the user's input until they quit, each time giving back true or false as to whether their input is valid.

using C = System.Console;

namespace P
{
class P
{
static void Main(string[] a) { while(true) C.WriteLine(F(C.ReadLine())); }
static bool F(string x)
{
int l = 0, r = 0;
foreach (var c in x) { if (c == '[') l++; if (c == ']') { r++; if ( r > l ) return false; }
return l == r;
}
}
}


Condensed form - 239 characters

using C = System.Console;
namespace P{class P{static void Main(string[] a){while(true)C.WriteLine(F(C.ReadLine()));}static bool F(string x){int l=0,r=0;foreach(var c in x){if(c=='[')l++;if(c==']'){r++;if(r>l)return false;}}return l==r;}}}


And lastly
the function itself - 112 characters (condensed form)

bool F(string x){int l=0,r=0;foreach(var c in x){if(c=='[')l++;if(c==']'){r++;if(r>l)return false;}return l==r;}

• Only realised that the bonuses were a good thing after writing this. Genius :p – Pharap Feb 21 '14 at 12:46
• All of these programs/functions would be useless for use as part of an actual program reader/parser anyway. – Pharap Feb 22 '14 at 23:09

# EcmaScript 6:

!(_=x[z='replace'](/("|').*?\1|\/\*.*?\*\/|[^({<[\]>})]/g,''),_.length-_[z](/[^({<[]/g,'').length)


# TI-BASIC, 39 bytes

cumSum(iPart(2sin(2seq(inString("()",sub(Ans,X,1)),X,1,length(Ans
not(min(Ans or Ans(dim(Ans


cumSum( keeps a running total of the number of braces, then the second line checks if both the minimum and the last element are zero.

Two tricks used:

• iPart(2sin(2* maps {0,1,2} to {0,1,-1} so I don't need to match { and } separately.
• I or the last element with the whole list, rather than min(Ans), to save a close-paren.

# Python, 7 bytes

eval(i)


Where i is the input. It handles {, [ and (, ignores braces in quotes, and, does to allow mismatched braces.

On an error, a Syntax error is generated!

Example:

>> eval('([{"("}])')

>> eval('([{(}])')
^
SyntaxError: invalid syntax


Edit: This is just a fun partial solution. It does not handle cases such as [ inside {, and {}[]` etc.