Guest User

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