Advertisement

# Random Parentheses Sequence

a guest
Sep 2nd, 2013
600
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. import random
2.
3. # Quadric algorithm
4.
5. def correct(seq):
6.   balance = 0
7.   for c in seq:
8.     balance += 1 if c == '(' else -1
9.     if (balance < 0):
10.       return False
11.   return True
12.
13. def tryAndCheck(n):
14.   seq = [')', '('] * n
15.   while (not correct(seq)):
16.     random.shuffle(seq)
17.   return seq
18.
19. # Linear algorithm
20.
21. def tryAndFix(n):
22.   seq  = ['(', ')'] * n
23.   random.shuffle(seq)
24.
25.   stack   = []
26.   result  = []
27.
28.   balance = 0
29.   prev    = 0
30.   for pos in range( len(seq) ):
31.     balance += 1 if seq[pos] == '(' else -1
32.     if balance == 0:
33.       if seq[prev] == '(':
34.         result.extend( seq[ prev : pos + 1 ] )
35.       else:
36.         result.append('(')
37.         stack.append( [ ')' if v == '(' else '(' for v in seq[ prev + 1 : pos ] ] )
38.       prev = pos + 1
39.
40.   for lst in reversed(stack):
41.     result.append(')')
42.     result.extend(lst)
43.
44.   return result
45.
46. print "".join( tryAndCheck(50) )
47. print "".join( tryAndFix(50) )
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement