Parentheses Matching
Posted 2 months ago by jordan. (last updated 2 months ago)
Today we'll be taking a look at nested parentheses.
Background
You're probably familiar with parentheses separating mathematical expressions like so:
(3x + 2)^2 - (x+1)
And, in some cases, you may have even come across nested parentheses:
((x + 4)^2 + 3) - (4x - 2)
Algebra aside, you'll notice that the grouping on the left contains a grouping within itself. The pattern above forms a valid arrangement of 3 nested parentheses - (())().
Examples
To start things off, consider the simplest case.
()
Not bad, one pair of parentheses. How about two pairs, how can we arrange those?
()() OR (())
Here we've got 2 options, we either set the parentheses side by side, or we nest them. Can you guess what the pattern will look like for 3 pairs?
()()() OR (())() OR ()(()) OR (()()) OR ((()))
Rules
You may see a pattern forming above, but let's look at invalid cases. Consider 1 pair of parentheses:
)(
This pair is invalid because we close a set before ever opening one! Likewise:
())
is also invalid.
Task
Your task is to prompt the user for a number of pairs, then generate all valid arrangements of parentheses with that amount of pairs. Let's see some examples.
parentheses@master -> ruby parentheses.rb 1 () parentheses@master -> ruby parentheses.rb 3 ((())) (()()) (())() ()(()) ()()() parentheses@master ->
Now, I won't directly reveal solutions for 4, 5, and 6 pairs (and onward). You can try and work them by hand, but you'll notice things grow pretty quickly! I can, however, offer this hint.
parentheses@master -> ruby parentheses.rb 4 | wc -l
14
parentheses@master -> ruby parentheses.rb 5 | wc -l
42
parentheses@master ->
Here, we can see that 4 and 5 pairs generate 14 and 42 arrangements respectively.
10 submissions
def parens(n)
if n==0 then
yield ""
else
n.times do |k|
parens(k) do |p|
parens(n-k-1) do |q|
yield "(#{p})#{q}"
end
end
end
end
end
parens(ARGV[0].to_i) do |p| puts p end
par[1] = {"()"};
par[n_] :=
Union[Flatten[{"()" <> #, "(" <> # <> ")", # <> "()"} & /@
par[n - 1]]];
def matching_parens(lps, rps = 0, prefix = '')
if lps == 0
puts prefix + ')'*rps
else
matching_parens lps-1, rps+1, prefix + '('
matching_parens lps, rps-1, prefix + ')' if rps > 0
end
end
matching_parens(ARGV[0].to_i.abs)
// open bracket is +1
// close bracket is -1
// left = how many open brackets we can still use
// count = how many open brackets that sre unclosed/unmatched
void par( string x, int count, int left, int size)
{
// unbalanced, return
if ( count < 0 ) return;
// we have reached max size, print what we have
if ( x.size() == size ){ cout << x << endl; return; }
// no more opening brackets left, still missing closing brackets
if ( count > 0 && left == 0 ) { par( x+")", count-1, left, size);}
// # of opening and closing brackets equal, but still have opening
// brackets left to use up
if ( count == 0 && left > 0 ) { par( x+"(", count+1, left-1, size);}
// -there's an opening bracket not closed yet
// -we also have opening brackets unused ( left > 0 )
// -so branch out and do both cases
// 1) use a close bracket to balance
// 2) use an open bracket
if ( count > 0 && left > 0 ){
par( x+")", count-1, left, size);
par( x+"(", count+1, left-1, size);
}
}
int main(){
string x = "";
int n = 3;
par( x, 0, n, n*2);
...
}
#!/usr/bin/env ruby
n = ARGV[0].to_i
# fits inside a tweet
([1,-1]*n).permutation(n*2).map{|x|x if x.reduce(0){|s,v|s<0?break: nil;s+v}}.uniq.compact.map{|i|i.reduce(''){|s,v|s+(v==1?'(':')')}}
#!/usr/bin/env ruby
#
# I'll go ahead and share my solution, nothing special :)
# http://jordanscales.com
def parentheses(to_open, to_close=0, build='')
if to_open == 0 and to_close == 0
puts build
end
if to_open > 0
parentheses(to_open - 1, to_close + 1, build + '(')
end
if to_close > 0
parentheses(to_open, to_close - 1, build + ')')
end
end
parentheses(ARGV[0].to_i)
#include <stdio.h>
#include <stdlib.h>
void fill(char *buf, char *next, int openRemaining, int closeRemaining)
{
int sizeRemaining = openRemaining + closeRemaining;
if(openRemaining > 0) {
*next = '(';
fill(buf, next + 1, openRemaining - 1, closeRemaining);
}
if(closeRemaining > 0 && closeRemaining > openRemaining) {
*next = ')';
if(sizeRemaining == 1)
printf("%s\n", buf);
else
fill(buf, next + 1, openRemaining, closeRemaining - 1);
}
}
int main(int argc, char **argv)
{
if(argc < 2) {
printf("Usage: %s <count>\n", argv[0]);
return -1;
}
int count = atoi(argv[1]);
char buf[(count * 2) + 1];
buf[count * 2] = 0;
fill(buf, buf, count, count);
return 0;
}
paren :: Int -> [[Char]]
paren n = paren1 n 0
where paren1 0 0 = [[]]
paren1 n 0 = ['(' : p | p <- paren1 (n-1) 1]
paren1 0 k = [')' : p | p <- paren1 0 (k-1)]
paren1 n k = ['(' : p | p <- paren1 (n-1) (k+1)] ++ [')' : p | p <- paren1 n (k-1)]
function g(p,i,l,r){return i||(l=r=p,i=''),r+l?(l?g(p,i+'(',l-1,r):'')+(r>l?g(p,i+')',l,r-1):''):i+" "}
function g(p,i,l,r){
//If input(i) is not defined(first iteration),
//define missing '(' (l), missing ')' (r), and input
return i||(l=r=p,i=''),
//If the input is not at max size(missing '(' or ')')
r+l?
//If there are missing '('
(l?g
//Add the iteration with one more '(' to the result
(p,i+'(',l-1,r):'')+
//If there are less ')' than '('
(r>l?
//Add the iteration with one more ')' to the result
g(p,i+')',l,r-1):'')
//Else(input at max size), add the input to the result
//and a separator, so the inputs don't stick together
:i+" "
}
//Usage:
g(3)
//"((())) (()()) (())() ()(()) ()()() "
#!/usr/bin/python
from sys import argv
for i in range(2*(4**int(argv[1])-1)/3,(2**int(argv[1])-1)*2**int(argv[1])+1,2):
r=0
for j in bin(i)[2:]:
r+={'1':1,'0':-1}[j]
if r<0:break
if r==0:print ''.join([chr(41-int(i))for i in bin(i)[2:]])