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 parentheses on my keyboard are all worn out, and I want to avoid using them as much as possible. Your challenge is to balance a line containing parentheses by adding them in before and after each line.

This is similar to TI-Basic's automatic parentheses and string closure (i.e. Output(1, 1, "Hello, World!). It also saves precious bytes from a program!

Example input:

This line has no parentheses
alert(Math.max(1, 2
1+1)*2).toString()
function() { alert('Hello, World!'); })(

Example (possible) output:

This line has no parentheses
alert(Math.max(1, 2))
((1+1)*2).toString()
(function() { alert('Hello, World!'); })()

Specification:

  • For each line of input,

    • Add as many open parentheses to the beginning and close parentheses to the end of the line as needed to balance the parentheses in the line

      • The definition of "balance" is:

        • Same amount of ( and ) in the line

        • For every substring starting from the beginning of the string, this substring must not have more closing parentheses than opening parentheses

          • For example, (foo))(bar is not balanced because (foo)) has more closing parentheses than opening parentheses
    • You may add extra unnecessary parentheses if you want to, if it makes your code shorter

    • You do not need to worry about string literals or anything like that, assume that all parentheses need balancing

  • Output each line with parentheses balanced

This is , so the shortest code in bytes will win!

share|improve this question
    
Are you just concerned with () parens, or do other brackets {}, [], <>, etc need to be considered as well? –  DigitalTrauma Apr 15 at 22:13
    
@DigitalTrauma Nope, only ( and ). –  Doorknob 冰 Apr 15 at 22:14
    
Do you have any test cases? –  Peter Taylor Apr 16 at 7:22
1  
@Peter Yeah, they're right there in the post... –  Doorknob 冰 Apr 16 at 11:50

4 Answers 4

GolfScript, 23 bytes

n/{"()"1/{.2$\-,*}%*n}/

The loophole I'm exploiting is the ruling that:

You may add extra unnecessary parentheses if you want to, if it makes your code shorter

Basically, for each line, this code counts the number of characters on the line that are not opening parentheses, and prepends that many extra opening parentheses to the line, and then does the same for closing parentheses. This is incredibly inefficient, but does ensure that all the parentheses on the output line are balanced.

For example, given the input:

This line has no parentheses
alert(Math.max(1, 2
1+1)*2).toString()
function() { alert('Hello, World!'); })(

this program will output:

((((((((((((((((((((((((((((This line has no parentheses))))))))))))))))))))))))))))
(((((((((((((((((alert(Math.max(1, 2)))))))))))))))))))
(((((((((((((((((1+1)*2).toString())))))))))))))))
(((((((((((((((((((((((((((((((((((((function() { alert('Hello, World!'); })()))))))))))))))))))))))))))))))))))))

Ps. You can also test this code online.

share|improve this answer
    
Just noticed that you got 10k (reputation) - congrats! :-) –  Doorknob 冰 Apr 16 at 11:59
4  
This reminds me of when I used to program in Lisp... A few bits of code lost in a sea of parenthesis. –  Taconut Apr 16 at 14:43

Perl, 32 = 31 + 1 or 73 = 72 + 1 (minimized parentheses)

32 = 31 + 1: with extra unnecessary parentheses

Edits:

  • Fix, parentheses now counted with y///.
  • Unnecessary variable $a removed.
$_="("x y/)//.s|$|")"x y/(//|er

It is used with the run-time switch -p (+1 byte).

Test file input.txt:

This line has no parentheses
alert(Math.max(1, 2
1+1)*2).toString()
function() { alert('Hello, World!'); })(
(foo))(bar
)))(((
((
))

Command line:

perl -p script.pl <input.txt

or

perl -pe '$_="("x y/)//.s|$|")"x y/(//|er' <input.txt

Result:

This line has no parentheses
alert(Math.max(1, 2))
(((1+1)*2).toString())
(((function() { alert('Hello, World!'); })()))
(((foo))(bar))
((()))((()))
(())
(())

Ungolfed:

The algorithm is simple, just add the counterpart for each found parentheses.

$_ =                     # $_ is provided as input by switch `-p` and
                         # it is printed afterwards as output.
                         # y/X// is used to count the character 'X' in $_
    '(' x y/)//          # add opening parentheses for each closing parentheses
    . s|$|')' x y/(//|er # go right before the end of line and insert
                         # closing parentheses for each opening parentheses
                         # in the original string

73 = 72 + 1: adding minimum number of parentheses

This script only adds the minimum number of parentheses to get a balanced output.

$a=y/()//cdr;1while$a=~s/\(\)//g;$_=$a=~y/)(/(/dr.$_;s|$|$a=~y/()/)/dr|e

It is used with the run-time switch -p (+1 byte).

perl -pe "$a=y/()//cdr;1while$a=~s/\(\)//g;$_=$a=~y/)(/(/dr.$_;s|$|$a=~y/()/)/dr|e" <input.txt

Result:

This line has no parentheses
alert(Math.max(1, 2))
((1+1)*2).toString()
(function() { alert('Hello, World!'); })()
((foo))(bar)
((()))((()))
(())
(())

Ungolfed:

$a = y/()//cdr;            # filter parentheses and store in $a
1 while $a =~ s/\(\)//g;   # remove matching parentheses
$_ = $a =~ y/)(/(/dr . $_; # add missing opening parentheses at start of string
s|$|$a=~y/()/)/dr|e        # insert missing closing parentheses at end of string

81 = 80 + 1: adding minimum number of parentheses

This is an older method to add the minimum number of parentheses for a balanced output.

my($l,$r);s/[()]/($&eq")"&&($r&&$r--||++$l))||$r++/ger;$_="("x$l.$_;s/$/")"x$r/e

It uses Perl 5.14 (because of the non-destructive substitution modifier) and the run-time switch -p (+1 byte).

perl -p script.pl <input.txt

Result:

This line has no parentheses
alert(Math.max(1, 2))
((1+1)*2).toString()
(function() { alert('Hello, World!'); })()
((foo))(bar)
((()))((()))
(())
(())

Ungolfed:

# The while loop is added by option "-p".
LINE:
while (<>) {

    # $_ contains the current line
    my ($l, $r); # initializes $l and $r (to undef/kind of indirect 0)
    # Modifiers for the following substitution of $_:
    # /g: process all parentheses
    # /e: evaluate code
    # /r: does not change the original input string $_ (Perl 5.14)
    s/[()]/
        # $& contains the matched parentheses
        # $r is a balance level counter; at the end $r contains
        #    the number of needed closing parentheses
        # $l is the number of needed opening parentheses;
        #    if $r would go negative, then an opening parentheses
        #    is missing and $l is increases and $r remains zero.
        (  
            $& eq ")" &&   # case ")"
            ($r && $r--    # close a parentheses group and update balance counter
                || ++$l)   # or update $l if an opening parentheses is needed
        )
        || $r++            # case "(": increase balance counter
    /ger;
    $_ = "(" x $l . $_;    # add opening parentheses at the begin of line
    s/$/")" x $r/e         # add closing parentheses before the line end

# the remainder is added by run-time switch "-p"
} continue {
    print or die "-p destination: $!\n";
}
share|improve this answer
2  
Wow, that almost looks like golfscript ;-) –  DigitalTrauma Apr 15 at 23:54
    
@HeikoOberdiek What perl are you using for the first version? It doesn't seem to work on 18.1 due to '('x/\)/g always equaling '('... –  Mouq Apr 16 at 0:23
    
@Mouq: Thanks, fixed now using y/// instead of m//g for counting the parentheses. –  Heiko Oberdiek Apr 16 at 1:57

Python 2.7 3: 62 60 58 bytes

while 1:s=input();c=s.count;print('('*c(')')+s+')'*c('('))

Not super golfed, but you know. I might be able to squeeze some more bytes out if I really tried.

For each line, outputs (*the number of ) in the line, then the line, then )*the number of ( in the line. If I understand the rules correctly, this will always provide valid output.

Exits by throwing an exception, as a result of the way I did input. (Input is always a hard part of these problems.) If this isn't acceptable, it'll cost me a few bytes to fix, though I'm not yet sure how many.

Example output:

This line has no parentheses
alert(Math.max(1, 2))
(((1+1)*2).toString())
(((function() { alert('Hello, World!'); })()))
share|improve this answer
    
This does not appear to take multiline input, i.e. prints are interspersed with lines of input. But nice algorithm idea, I didn't think of that ;) –  Doorknob 冰 Apr 15 at 22:31
    
python2 balanced_parenthesis.py < input.txt 2>/dev/null gets the output I wrote but if you want multiline input while doing it interactively it'll cost me a few bytes. Give me a second, I'll figure something out... –  undergroundmonorail Apr 15 at 22:43
    
Ah, okay, never mind then. That will work! –  Doorknob 冰 Apr 15 at 22:46
    
save 2 chars: while 1:s=raw_input();c=s.count;print'('*c(')')+s+')'*c('(') –  Quincunx Apr 16 at 1:03
    
@qui Oh, wow. I came so close to figuring that out, but I didn't realize you could do c=s.count. I thought you had to do c=s, s.c(). Thanks! –  undergroundmonorail Apr 16 at 4:49

Pure Bash, 72 bytes

Uses the same algorithm as @undergroundmonorail's answer:

while read a;do
o=${a//[!(]}
c=${a//[!)]}
echo ${c//)/(}$a${o//(/)}
done

Output:

$ ./lazyparens.sh < input.txt
This line has no parentheses
alert(Math.max(1, 2))
(((1+1)*2).toString())
(((function() { alert('Hello, World!'); })()))
$ 
share|improve this answer

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.