Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

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.

share|improve this question
2  
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 at 18:42
    
@Danny Ugh, I should have known I'd forget something. Sure, let's add that. –  acbabis Feb 20 at 18:46
    
Stack based languages may be particularly good at this –  Cruncher Feb 20 at 21:48
add comment

17 Answers

up vote 3 down vote accepted

Perl, (136 130 129 chars - (20*3) - 30 - 50 - 20 - 50) == -81

<3 recursive REs.

$/=$_;print!(<>!~m#^(([^][<{('"/)}>]|'[^']*'|"[^"]*"|/((?![*/])|\*((?!\*/).)*\*/|/[^\n]*+)|<(?1)>|\((?1)\)|\[(?1)]|{(?1)})*)$#s)
share|improve this answer
1  
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 at 21:54
    
Congratulations –  acbabis Mar 3 at 20:16
add comment

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)

share|improve this answer
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
    
Don't forget to add your explanation. –  Quincunx Feb 20 at 19:53
    
@Quincunx done (comment too short) –  mniip Feb 20 at 19:58
add comment

C, 70 62 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!

share|improve this answer
1  
~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 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 at 22:50
add comment

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.

share|improve this answer
    
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. –  acbabis Feb 20 at 21:08
    
@acbabis Oh, I misread; it's -50 for // and another -50 for /* */? –  Joshua Taylor Feb 20 at 21:10
    
No, you were right the first time. Its -70 total for both. –  acbabis Feb 20 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? –  acbabis Feb 20 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 at 21:20
show 2 more comments

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<},!&
share|improve this answer
    
Remember to add an explanation. –  Quincunx Feb 20 at 20:47
    
@Quincunx Done! –  Ben Reich Feb 20 at 21:07
add comment

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.

share|improve this answer
add comment

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 :)

share|improve this answer
    
Suggested an edit for the part you gave up on (and fixed a bug) –  impinball Feb 25 at 6:34
    
I'm afraid your edit is incorrect - it throws line 1: syntax error near unexpected token `done' –  Riot Feb 25 at 12:22
add comment

Javascript: 392 383 387 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.

share|improve this answer
    
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 –  Charles Feb 21 at 1:52
    
@Charles Fixed. Thank you. –  Victor Feb 21 at 2:04
    
Also, I think the following would fail: ('a quote " in apostrophes!') "and two quotes out of them" –  Charles Feb 21 at 4:24
    
@Charles Thank you. Fixed and reduced it more 42 characters. –  Victor Feb 21 at 4:55
add comment

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.

share|improve this answer
    
Good work. The -80 bonus should be -60 because handling 1 brace type is required. –  acbabis Feb 20 at 19:15
    
Bah, you're right. I can't math. –  undergroundmonorail Feb 20 at 19:16
add comment

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
share|improve this answer
add comment

Python:

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.

share|improve this answer
add comment

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!/[()<>{}[\]]/
share|improve this answer
add comment

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;}
share|improve this answer
    
Only realised that the bonuses were a good thing after writing this. Genius :p –  Pharap Feb 21 at 12:46
    
I'm not sure if your program meets all the requirements. Your program should return false for ][ and should return true for the empty program. –  acbabis Feb 21 at 16:08
    
The first point I understand, but where in the brief does it say that the program has to output true for an empty string? –  Pharap Feb 21 at 19:21
    
It doesn't explicitly state it, but if a program contains no braces it is logically correct to say that all braces match. The requirements don't say a program can't not contain braces :) –  acbabis Feb 21 at 20:32
    
All of these programs/functions would be useless for use as part of an actual program reader/parser anyway. –  Pharap Feb 22 at 23:09
add comment

EcmaScript 6:

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

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
share|improve this answer
    
doesn't this check more than just matched braces? –  Jan Dvorak Feb 20 at 18:53
3  
Also, it won't compile (<>), so no dice –  acbabis Feb 20 at 18:55
    
All this does is try to compile it as C source code –  TheDoctor Feb 20 at 19:05
    
@TheDoctor ...but it doesn't meet any of the requirements or bonuses :/ –  acbabis Feb 20 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. –  Visa is Racism Feb 20 at 20:01
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.