# Write a program which replaces with spaces the braces in cases where braces in places cause stasis

You are a project manager. One day, one of your programmers went insane (not your fault) and took all the expressions in the codebase and added random brackets to them, before quitting on the spot, ranting about your incompetence (also not your fault). This would be an easy fix, however, for some reason you aren't using revision control (totally not your fault). And for some reason, none of the other programmers want to go through every expression to fix up the mismatched brackets (by the way, that is not your fault). Programmers these days, you think to yourself. You will have to do it yourself. The horror! Such tasks were supposed to be beneath you...

The input will be a single line, which will contain a number of left brackets (( [ {) and right brackets () ] }). It also may, but not always, contain comments (/* */) and string literals (" " or ' ') and various numbers, letters, or symbols.

There will be at least one bracket (outside of a comment or string literal) that does not have a corrosponding opposite (outside of a comment or string literal). For example, an errant } without a { prior. Another example: a ( which does not have a ) afterwards. Your program will replace with a space the minimum number of brackets required to make the brackets match up.

Examples:

(4 + (2 + 3))] ==> (4 + (2 + 3))  (the square bracket at the end)
][][[]] ==>  [][[]] (the square bracket at the start)
("Hel(o!")) ==> ("Hel(o!")  (the parenthesis at the end)
( /* )]*/ ==>  /* )]*/ (the parenthesis at the start)
{()] ==>  ()  (the curly bracket and the square bracket)

• Input can be taken from whichever way is most convenient (STDIN, command line argument, reading from a file, etc.)
• If there is more than one way to resolve the mismatch with the same number of removals, either is acceptable.
• There will be only mismatches in brackets. String literals and comments will always be correctly formed.
• The title comes from this SO thread

This is code golf, so minimum number of bytes wins. Ask questions in comments if the specification is not clear.

• Whoops, our edits kind of collided there. :P Everything should be fixed now. – Doorknob Aug 19 '14 at 22:22
• @Doorknob Thanks for that, by the way. Didn't know how to stop SE from wiping the spaces.​​​​​​​​​​​​​​​ – absinthe Aug 19 '14 at 22:22
• Do we have to handle escaping stuff in string literals (e.g. ("foo (\") bar"))? – Doorknob Aug 19 '14 at 22:30
• I would argue that the correct output for {{(}) should be { }  or equivalent, since the opening scenario implies that the code was working to begin with, and {(}) counts as mismatched brackets in every programming language I know (i.e. "causes stasis"??). But, then, I already wrote an answer, so I'm biased. – DLosc Aug 21 '14 at 22:48
• I see. Guess I'm just not incompetent enough. ;) – DLosc Aug 21 '14 at 23:00

# Ruby, 223 characters

This one turned out a bit long.

u,b,i=[],[[],[],[]],-1
s=gets.gsub(/(\/\*|"|').*?(\*\/|"|')|~/){|m|u+=[m];?~}
s.chars{|c|i+=1
(t='{[('.index(c))?b[t].push(i):((t='}])'.index(c))&&(b[t].pop||s[i]=' '))}
b.flatten.map{|l|s[l]=' '}
puts s.gsub(/~/){u.shift}


What it does is take out the strings and comments first, so they don't get counted (and puts them back in later).

Then, it goes through the string character by character. When it finds an opening brace, it stores its position. When it finds a closing brace, it pops from its respective open brace storage array.

If pop returns nil (i.e. there weren't enough opening braces), it removes the closing brace. After this entire thing is done, it removes the remaining extra opening braces (i.e. there weren't enough closing braces).

At the end of the program, it puts all the strings and comments back and outputs them.

Ungolfed:

in_str = gets

# grab strings and comments before doing the replacements
i, unparsed = 0, []
in_str.gsub!(/(\/\*|"|').*?(\*\/|"|')|\d/){|match| unparsed.push match; i += 1 }

# replaces with spaces the braces in cases where braces in places cause stasis
brace_locations = [[], [], []]
in_str.each_char.with_index do |chr, idx|
if brace_type = '{[('.index(chr)
brace_locations[brace_type].push idx
elsif brace_type = '}])'.index(chr)
if brace_locations[brace_type].length == 0
in_str[idx] = ' '
else
brace_locations[brace_type].pop
end
end
end
brace_locations.flatten.each{|brace_location| in_str[brace_location] = ' ' }

# put the strings and comments back and print
in_str.gsub!(/\d+/){|num| unparsed[num.to_i - 1] }
puts in_str

• This is seriously impressive. One question, though: will it still work for an input like (("string"/*comment*/)"string"? If I'm reading (the ungolfed version) correctly, you replace strings and comments with their index in the unparsed array, which would lead to a substitution like ((12)3 and then looking for a nonexistent index 12 (or 11). I see the golfed version just uses shift, but might it not still have a similar problem? – DLosc Aug 21 '14 at 23:49

# Python 3, 410322 317

import re;a='([{';z=')]}';q=[re.findall('".*?"|/\*.*?\*/|.',input())]
while q:
t=q.pop(0);s=[];i=0
for x in t:
if x in a:s+=[x]
try:x in z and 1/(a[z.find(x)]==s.pop())
except:s=0;break
if[]==s:print(''.join(t));break
while 1:
try:
while t[i]not in a+z:i+=1
except:break
u=t[:];u[i]=' ';q+=[u];i+=1


Tries every possible set of deletions, starting with smaller ones, until it finds one where the braces are balanced. (By which I mean fully correctly balanced: {{(}) produces ( ), not {(}).)

The first version used a recursive generator function, which was really cool but also really long. This version performs a simple breadth-first search using a queue. (Yes, it's a factorial time algorithm. What's the problem? :^D)

• I like this one because it actually finds the least removal and produces correctly nested expressions, but the last comment by @vonilya suggests that correct nesting isn't important. However, it is really slow if lots of braces need to be removed. – rici Aug 21 '14 at 6:09

## C - 406

An Attempt in C without using regular expressions.

#define A if((d==125||d==93||d==41)
char*s;t[256];f(i,m,n,p){while(s[i]!=0){int c=s[i],k=s[i+1],v=1,d;if((c==42&&k==47)||(c==m&&i>n))return i;if(!p||p==2){if((c==39||c==34)||(c==47&&k==42)){i=f(i,c*(c!=47),i,p+1);
c=c==47?42:c;}d=c+1+1*(c>50);A){v=f(i+1,d,i,2);if(!p&&v)t[d]++;if(p==2&&v)i=v;}}d=c;A&&!p){v=!!t[c];t[c]-=v;}if(p<2)putchar(c*!!v+32*!v);i++;}return 0;}main(int c,char*v[]){s=v[1];f(0,0,0,0);}


To compile and run (on a linux machine):
gcc -o brackets brackets.c
./brackets "[(])"

In undefined cases like [ ( ] ) it returns the last valid bracket pair ( )

# Python 3, 320

import re
O=dict(zip('([{',')]}'))
def o(s,r,m=0,t=[]):m+=re.match(r'([^][)({}/"]|/(?!\*)|/\*.*?\*/|".*?")*',s[m:]).end();return r and o(s[:m]+' '+s[m+1:],r-1,m+1,t)or(o(s,r,m+1,t+[O[s[m]]])if s[m]in O else[s[m]]==t[-1:]and o(s,r,m+1,t[:-1]))if s[m:]else not t and s
s=input();i=0;a=0
while not a:a=o(s,i);i+=1
print(a)


Like DLosc's solution, this investigates every possible deletion, but it uses a recursive explore and fallback strategy which is a lot faster. I know that speed is not a criterion in code golf, and exhaustive search is in any case exponential, but this one can handle inputs like ({({({({({({({({(}}}}}}}} in a couple of seconds.

• Well played, well played. I did manage to get down to 317, but I think you should be able to pass that pretty easily. (Meanwhile, my program is still churning away at your example input...) – DLosc Aug 22 '14 at 18:20
• @DLosc: Don't hold your breath :). It took my machine 58 minutes to do the version of that pattern with 6 open parens. In order to solve the stasis before the universe reaches heat-death, you'll need to memoise the queue; otherwise, you end up with an O(n!!) solution, not O(n!). (My golf is O(n*2^n) instead of O(2^n), because o actually produces all the patterns with up to r removals, instead of exactly r removals. Easy to fix, but it would cost a few characters.) – rici Aug 23 '14 at 3:24