# Regular Expression for Binary Numbers Divisible by n

a guest
Feb 3rd, 2018
285
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. class Term(object):
2.     def __init__(self, state, symbol):
3.         self.state = str(state)
4.         self.symbol = str(symbol)
5.
6.     def __str__(self):
7.         return self.state + '(' + self.symbol + ')'
8.
9. def removeLoops(table):
10.     loops = dict()
11.
12.     for i in range(1, len(table)):
13.         row = table[i]
14.         for term in row:
15.             if term.state == str(i):
16.                 loops[term.state] = term.symbol
17.                 row.remove(term)
18.
19.     for i in range(len(table)):
20.         row = table[i]
21.         for term in row:
22.             if term.state in loops:
23.                 if len(loops[term.state]) > 1:
24.                     term.symbol = '(?:' + loops[term.state] + ')*' + term.symbol
25.                 else:
26.                     term.symbol = loops[term.state] + '*' + term.symbol
27.
28.
29. def substituteLastTerm(table):
30.     state = str(len(table) - 1)
31.     terms = table.pop()
32.     for i in range(len(table) - 1, -1, -1):
33.         row = table[i]
34.         newRow = []
35.         for t in row:
36.             if t.state == state:
37.                 for term in terms:
38.                     newRow.append(Term(term.state, term.symbol + t.symbol))
39.             else:
40.                 newRow.append(t)
41.         table[i] = consolidatedRow(newRow)
42.
43. def consolidatedRow(row):
44.     terms = dict()
45.     for term in row:
46.         if term.state in terms:
47.             terms[term.state].append(term.symbol)
48.         else:
49.             terms[term.state] = [term.symbol]
50.
51.     result = []
52.     for state in sorted(terms.keys()):
53.         if len(terms[state]) > 1:
54.             result.append(Term(state, '(?:' + '|'.join(terms[state]) + ')'))
55.         else:
56.             result.append(Term(state, terms[state][0]))
57.     return result
58.
59. def regex_divisible_by(n):
60.     if n == 1:
61.         return '^(0|1)+\$'
62.
63.     table = []
64.     for i in range(n):
65.         table.append([Term(i//2, i%2), Term((i+n)//2, (i+n)%2)])
66.
67.     while len(table) > 1:
68.         removeLoops(table)
69.         substituteLastTerm(table)
70.
71.     return '^' + table[0][0].symbol + '+\$'
RAW Paste Data