python - 如何将德摩根定律应用于Python中的 boolean 表达式字符串？

Question

我编写了一个程序，它将 boolean 表达式作为字符串输入并给出函数的真值表。它适用于所有类型的表达式，除了那些涉及整个补集(即某些子表达式(不是变量)的补集)的表达式。 [例如。 A'(BC+D) 没有问题，但 A(BC+D)' 有]。

我不会选择 Pythonic 逻辑表达式(例如 not(a+b) 而不是 (a+b)')，因为表达式被视为用户输入和用户被假定为非程序员。

假设我有一个像 ((ab'+cd)'+cd'+ab)' 这样的字符串。反复应用德摩根定律，我必须得到如下表达式:

(ab'+cd)(c'+d)(a'+b')

同样，(a'b+ab')c'+(a'b+ab')'c 必须变为 (a'b+ab')c+(ab+ a'b')c.

如何在 Python 中完成此操作？

到目前为止我编写的代码是-

f=raw_input("enter the Boolean expression:")
fin=f
alpha=list(set([i for i in f if i in [chr(64+n) for n in range(27)]]))
alpha.sort()

truth=[bin(n).replace("0b","").rjust(int(len(alpha)),"0") for n in range(0,2**(len(alpha)))]

def change(string,old,new):
    pos=string.index(old)
    return string[:pos]+new+string[pos+1:]

out=[]
for i in range(len(truth)):
    for elem in f:
        if elem in alpha:
            if (f.index(elem))+1<len(f) and f[(f.index(elem))+1]=="'":
                f=change(f,elem,str(abs(int(truth[i][alpha.index(elem)])-1)))
            else:
                f=change(f,elem,truth[i][alpha.index(elem)])
    out.append(f)
    f=fin

out=[elem.replace("'","") for elem in out]
out=['+'.join('*'.join(x) for x in s.split('+')) for s in out]

m=f.count("(")

for k in range(m):
    for string in out:
        for i in range(len(string)):
            if string[i]=="(" and string[i+1]=="*":
                out[out.index(string)]=string[:i+1]+""+string[i+2:]
                break

for k in range(m):
    for string in out:
        for i in range(len(string)):
            if string[i]==")" and string[i-1]=="*":
                out[out.index(string)]=string[:i-1]+""+string[i:]
                break

out=[int(eval(elem)) for elem in out]
out=[int(elem/float(abs(elem))) if elem>=1 else 0 for elem in out]
print "Output values of the truth table:",out

print "--"*(7*len(alpha)+len(f)+2)
for elem in alpha:
    print elem,"\t",
print "  Y=",f
print "--"*(7*len(alpha)+len(f)+2)
for elem in truth:
    for i in range(len(elem)):
        tr=elem[i].split()
        for j in tr:
            print j,"\t",
    print "  "*(len(f)/2),out[truth.index(elem)],"\n"

这是用 Python 2.7 编写的，Python 3 可能需要进行一些小调整。

Answer 1

我会用正则表达式来完成你的任务。这是该算法的完整代码:

import re
import itertools


def get_variables(expr):
    return sorted(set(re.findall(r'[a-z]', expr)))


def perform_and(expr):
    """
    ab -> (a and b)
    (...)(...) -> (...) and (...)
    """
    expr = re.sub(r"([a-z]\'?)\s*([a-z]\'?)", r"(\1 and \2)", expr)
    expr = re.sub(r"([a-z]\'?)\s*(\()", r"(\1 and \2", expr)
    expr = re.sub(r"(\)\')\s*([a-z]\'?)", r"\1 and \2)", expr)
    expr = re.sub(r"(\)\')\s*(\()", r"\1 and \2", expr)
    return expr


def perform_or(expr):
    """
    ... + ... -> ... or ...
    """
    return re.sub(r"\+", " or ", expr)


def perform_not(expr):
    """
    a' -> not a
    (...)' -> not (...)
    """
    # Replacing brackets from () to {} (replacing back will be in the while-loop)
    expr = expr.replace("(", "{")
    expr = expr.replace(")", "}")

    # Adding 'not' to separate variables
    expr = re.sub(r"([a-z])\s*\'", r"not \1", expr)

    # Loop until expr stops changing
    while True:
        # Adding 'not' to expressions in {}-brackets without {}-brackets inside
        expr_new = re.sub(r"\{([^\{\}]+)\}\s*\'", r"not (\1)", expr)

        # Replacing brackets back from {} to ()
        expr_new = re.sub(r"\{([^\{\}]+)\}(\s*[^\'])", r"(\1)\2", expr_new)

        # Leaving the loop if nothing changed
        if expr == expr_new:
            break
        else:
            expr = expr_new

    # Replacing back
    expr = expr.replace("{", "(")
    expr = expr.replace("}", ")")

    return expr


def to_pythonic(expr):
    expr = perform_and(expr)
    expr = perform_or(expr)
    expr = perform_not(expr)
    expr = re.sub(r'\s+', ' ', expr)  # reducing multiple spaces (not necesary)
    return expr


def build_truth_table(pythonic_expr, variables):
    print(" ".join(variables), "->", "result")
    for values in itertools.product([0, 1], repeat=len(variables)):
        dct = dict(zip(variables, values))
        result = int(eval(pythonic_expr, dct))
        print(" ".join(map(str, values)), "->", result)


if __name__ == "__main__":
    expr = "((ab'+cd)'+cd'+ab)'"

    pythonic_expr = to_pythonic(expr)
    variables = get_variables(expr)
    build_truth_table(pythonic_expr, variables)

主要思想是用替换empty -> and 、+ -> or 、' -> not来Python化你的表达式，正确保持括号。之后，我迭代给定变量的所有可能值，并为 python 化表达式运行 eval 来计算结果。