Fun with Matching Braces [duplicate]

Question

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.

Answer 1

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)

Answer 2

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.

Answer 3

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

<3 recursive REs.

$/=$_;print!(<>!~m#^(([^][<{('"/)}>]|'[^']*'|"[^"]*"|/((?![*/])|\*((?!\*/).)*\*/|/[^\n]*+)|<(?1)>|\((?1)\)|\[(?1)]|{(?1)})*)$#s)

Answer 4

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.

Answer 5

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!

Answer 6

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.

Answer 7

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<},!&

Answer 8

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.

Answer 9

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

Answer 10

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.

Answer 11

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.

Answer 12

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

Answer 13

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.

Answer 14

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

Answer 15

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!/[()<>{}[\]]/

Answer 16

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

Answer 17

EcmaScript 6:

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

Answer 18

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.

Answer 19

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.