QMC Python

#!/usr/bin/env python

import sys
import math
import re


def find_char_difference(str1, str2) :
    if len(str1) != len(str2) :
        return None;
    counter = 0
    index = -1
    for i in range(len(str1)) :
        if str1[i] != str2[i] :
            counter += 1
            index = i
    if counter != 1 :
        return None
    return index

class Minterm :
    def __init__(self, terms, rep) :
        self.minterms = terms
        self.binary = rep
        self.done = False

def is_complete_table(table) :
    for m in table :
        if not m.done :
            return False
    return True


def combine_terms(term1, term2) :
    if term1.done or term2.done :
        return None
    index = find_char_difference(term1.binary, term2.binary)
    if index == None :
        return None
    listterm = list(term1.binary)
    listterm[index] = '-'
    term = "".join(listterm)
    newMin = Minterm(list(set(term1.minterms+term2.minterms)), term)
    return newMin


def is_contained_by(term1, term2) :
    for i in term2.minterms :
        if not i in term1.minterms :
            return False
    return True


def imply_table(table) :
    newTable = []
    for m in range(len(table)) :
        if table[m].done :
            newTable.append(table[m])
            continue
        wasCombined = False
        for n in range(m+1, len(table)) :
            if table[m].minterms == table[n].minterms :
                continue
            newTerm = combine_terms(table[m], table[n])
            if not newTerm :
                continue
            newTable.append(newTerm)
            wasCombined = True

        table[m].done = not wasCombined
        if table[m].done :
            newTable.append(table[m])
    m = 0
    while m < len(newTable)-1 :
        n = m+1
        while n < len(newTable) :
            if is_contained_by(newTable[m], newTable[n]) :
                del newTable[n]
                n-= 1
            n+=1
        m+=1
    return newTable


# read in and sanatize the data
data = sys.stdin.read()
data = re.sub(r'\s','',data)
N = math.log(len(data),2)
if N < 1 or N != int(N) :
    sys.exit(0)
N = int(N)
print "N = " + `N`
for c in data :
    if c != '0' and c != '1' :
        sys.exit(0)
# create a mintable with all of the terms
mintable = []
minlist = []
for i in range(0, len(data)) :
    if data[i] == '1' :
        mintable.append(Minterm([i], bin(i)[2:].zfill(N)))
        minlist.append(i)

while not is_complete_table(mintable) :
    mintable = imply_table(mintable)

print "NOTE: NOT FULLY REDUCED (NEEDS PRIME IMPLICATION)"
string = "f(A"
for i in range(1,N) :
    string += "," + chr(65+i)
string += ") = "
for t in mintable :
    for i in range(N) :
        if t.binary[i] == '0' or t.binary[i] == '1' :
            string += chr(65+i)
            if t.binary[i] == '0' :
                string += "`"
    string += " + "
string = string[:-3]
print string