真值表计算器

Question

在我的软件工程课程中，我不得不用我选择的语言写一个真值表计算器。这就是我想出来的，我想知道下次我应该做什么更好：

import copy
import sys

print("This program reads boolean equations and outputs the truth table.")
print("You may use the operators ~, ∨, and ∧, or")
print("their text equivalents, not, or, and and.")
print("You may use parenthesis, braces, and brackets to group your equations,")
print("and you must use single letters for your variable names, as 'a∨b'\n")

equation = input()
equation_copy = equation
equation_vars = []
equation = " " + equation + " "
equation = equation.replace("~", " not ")
equation = equation.replace("∨", " or ")
equation = equation.replace("∧", " and ")
equation = equation.replace("[", "(")
equation = equation.replace("]", ")")
equation = equation.replace("{", "(")
equation = equation.replace("}", ")")

for index in range(len(equation)):
    if equation[index] in " ()^":
        continue
    if equation[index + 1] in " ()" and equation[index - 1] in " ()" and equation[index] not in equation_vars:
        equation_vars.append(equation[index])

equation_vars.sort()

for equationIndex in equation_vars:
    sys.stdout.write(equationIndex + '\t')

print(equation_copy)

for equationIndex in range(pow(2,len(equation_vars))):
    vals = str(bin(equationIndex)).replace('0b','').zfill(len(equation_vars))

    for value in vals:
        sys.stdout.write(value + '\t')

    equation_vars_copy = copy.deepcopy(equation_vars)
    for index in range(len(equation_vars_copy)):
        equation_vars_copy[index] += " = " + vals[index]
        exec(equation_vars_copy[index])

    truthTable = "result = equation"
    truthTable = truthTable.replace('equation', equation)
    exec(truthTable)
    if result:print(1)
    else:print(0)

我在IdeOne有一个工作版本。

Answer 1

我们自上而下吧。我会提出一些更聪明的方法来做一些事情，但是这次的回顾将在以下两个最重要的方面达到高潮：

• 这是一个巨大的安全漏洞，而且
• 您应该将代码组织成函数。

介绍性信息

编写多行字符串的一个好方法是使用"""the longstring"""语法。

不过，在这种情况下，介绍性消息也可以作为程序的docstring。您可以使用特殊的__doc__变量通过内省来获取docstring。

"""This program reads boolean expressions and outputs the truth table.
You may use the operators ~, ∨, and ∧, or
their text equivalents, not, or, and and.
You may use parenthesis, braces, and brackets to group your expressions,
and you must use single letters for your variable names, as 'a∨b'"""

print(__doc__)

请注意，“等式”不是正确的词:您不需要带有等号的字符串。你只想要一个“布尔表达式”。

引导表达

在多次传递中进行字符串替换是一种糟糕的做法。在最好的情况下，您会花费一些精力对字符串进行多次传递。在最坏的情况下，将先前替换的文本传递到另一轮可能是不正确的--不过幸运的是，这里的情况并非如此。

我建议在一次传递中使用正则表达式进行替换。

REPLACEMENTS = {
   '~': ' not ',
   'v': ' or ',
   '^': ' and ',
   '[': '(',
   ']': ')',
   '{': '(',
   '}': ')',
}
expr = re.sub('|'.join(re.escape(sym) for sym in REPLACEMENTS.keys()),
              lambda sym: REPLACEMENTS[sym.group(0)],
              expr).strip()

提取变量

这也可以使用正则表达式进行简化。\b[A-Za-z]\b在两边寻找任何以单词边界为界的字母。

此外，使用set更优雅的是去重复。

vars = sorted(set(re.findall(r'\b[A-Za-z]\b', expr)))

生成布尔值

对于itertools.product()来说，这是一项完美的工作，实际上，文档中有这样一个例子：

product(range(2), repeat=len(vars))

计算表达式

首先，您应该使用eval()，而不是exec()，因为您希望计算表达式并获得它的值，而不是运行一些代码来解决其副作用。result = eval(expr)优于exec('result = ' + expr)。

然而，最重要的是，像这样调用eval()或exec()是一个巨大的安全漏洞--它允许用户执行任意的Python代码。例如，用户可以输入要执行的内容：

__import__('os').system('rm -rfi /')

大家的共识是Python不能被安全地沙箱化。我们可以尝试通过在只包含相关变量的作用域中计算表达式来做得更好。

NO_GLOBALS = {'__builtins__': {}}
for vals in product(range(2), repeat=len(vars)):
    locals = dict(zip(vars, vals))
    result = eval(expr, NO_GLOBALS, locals)

然而，我怀疑即使这样也不安全。例如，lambda关键字仍然可用，这让我很紧张。最终，唯一安全的方法可能是编写自己的代码来解析和计算表达式-- Python本身太强大了。

建议的解决方案

最后一点是:问题可以很好地划分为功能。命名这些工作块可以使您的代码更容易理解。

"""This program reads boolean expressions and outputs the truth table.
You may use the operators ~, ∨, and ∧, or
their text equivalents, not, or, and and.
You may use parenthesis, braces, and brackets to group your expressions,
and you must use single letters for your variable names, as 'a∨b'"""

from itertools import product
import re

def canonicalize(expr):
    REPLACEMENTS = {
       '~': ' not ',
       'v': ' or ',
       '^': ' and ',
       '[': '(',
       ']': ')',
       '{': '(',
       '}': ')',
    }
    return re.sub('|'.join(re.escape(sym) for sym in REPLACEMENTS.keys()),
                  lambda sym: REPLACEMENTS[sym.group(0)],
                  expr).strip()

def extract_variables(expr):
    return sorted(set(re.findall(r'\b[A-Za-z]\b', expr)))

def truth_table(expr):
    expr = canonicalize(expr)
    vars = extract_variables(expr)
    NO_GLOBALS = {'__builtins__': {}}

    # Print header
    print('\t'.join(vars + [expr]))

    # Print body
    for vals in product(range(2), repeat=len(vars)):
        locals = dict(zip(vars, vals))
        result = eval(expr, NO_GLOBALS, locals)
        print('\t'.join([str(v) for v in vals] + [str(result)]))

def prompt_expr():
    print(__doc__)
    print()
    return input()

if __name__ == '__main__':
    truth_table(prompt_expr())

Answer 2

我在考虑如何安全地处理eval问题，我突然意识到，避免构建解析器的最好方法是将其与Python的ast模块挂钩。有一个方便的NodeVisitor类可以让我们对树进行递归评估。这有点微妙，所以我就把我想出来的东西告诉你。

import ast
import operator

class BoolExprEvaluator(ast.NodeVisitor):
    ops = {
        ast.And: operator.and_,
        ast.Or: operator.or_,
        ast.Not: operator.not_
    }

    def __init__(self, vars):
        self.vars = vars

    def callop(self, op, *args):
        return self.ops[type(op)](*args)

    def generic_visit(self, tree):
        """
        Overload the fallback visitor to throw an error.
        This should not be called from user code.
        """

        msg = "Can't evaluate expression containing {} ast nodes"
        raise ValueError(msg.format(type(tree).__name__))


    def visit_Module(self, module):
        [expr] = module.body
        return self.visit(expr)

    def visit_Expr(self, expr):
        return self.visit(expr.value)


    def visit_BoolOp(self, boolop):
        left, right = map(self.visit, boolop.values)
        return self.callop(boolop.op, left, right)

    def visit_UnaryOp(self, unaryop):
        expr = self.visit(unaryop.operand)
        return self.callop(unaryop.op, expr)


    def visit_Name(self, name):
        return self.vars[name.id]

用于：

tree = ast.parse("(a or not b and b) or (a or b)")
BoolExprEvaluator({"a": False, "b": False}).visit(tree)
#>>> False

这个链接非常整齐地连接到200_success的版本中。

还请注意，当前您支持

a && b
a // (a or not a)

通过使用定义良好的API，您可以避免这种奇怪的结果，并提供更好的错误消息。更好的做法是自己构建一个解析器，但这听起来更难。

我还会考虑在令牌级别上进行替换和查找所有的名称标记，因为它允许支持以下内容

abc∨def

目前抛出一个不愉快的错误。您也可以同时做白名单，进一步减少可能发生的不必要的计算量。这有点长，因为每个案件都需要单独处理，但案件本身相当简单：

import io
import tokenize

def transform_token(token):
    if token.type in (tokenize.ENCODING, tokenize.NAME, tokenize.ENDMARKER):
        return token

    elif token.type == tokenize.OP:
        if token.string in {"~", "(", ")"}:
            return token

        elif token.string in {"{", "["}:
            return token._replace(string="(")

        elif token.string in {"}", "]"}:
            return token._replace(string=")")

        else:
            err = "Only '~', '∨', '∧' and bracketing operators allowed; got {!r}"
            raise ValueError(err.format(token.string))

    elif token.type == tokenize.ERRORTOKEN and token.string == "∨":
        return token._replace(type=tokenize.OP, string=" or ")

    elif token.type == tokenize.ERRORTOKEN and token.string == "∧":
        return token._replace(type=tokenize.OP, string=" and ")

    raise ValueError("Invalid token: {!r}".format(token))

def token_filter(tokens, names):
    for token in tokens:
        if token.type == tokenize.NAME:
            names.add(token.string)

        yield transform_token(token)

使用需要令牌化：

equation = "[abc]∨∧~(def)"
stream = io.BytesIO(equation.encode("utf8")).read
tokens = tokenize.tokenize(stream)

然后在去标记之前传递它：

names = set()
transformed = token_filter(tokens, names)
tokenize.untokenize(transformed).decode("utf8")
names

这两种方法的结果都是，您对输入强制了相当强的良好的格式要求，而输入根本不可能做一些不好的事情。错误也更好，标识符可以是任意长度的。

我能想到的一件事是，它仍然允许与之不匹配的括号：

[ a )

如果在AST级别执行舍入替换，这将由ast.parse处理，但它会比较麻烦。一个更好的选择可能是在transform_token期间保留一个括号堆栈。

Answer 3

下面是您的代码的一个改进版本的草案。我一有时间就会对我改变的事情发表意见。此外，还有许多事情要做，比如摆脱exec。

事实上，这一切都是200_成功说的。

import copy
import itertools
import sys

def get_equation_from_user():
    print("This program reads boolean equations and outputs the truth table.")
    print("You may use the operators ~, ∨, and ∧, or")
    print("their text equivalents, not, or, and and.")
    print("You may use parenthesis, braces, and brackets to group your equations,")
    print("and you must use single letters for your variable names, as 'a∨b'\n")
    # commented for testing purposes: return input()
    return "(a ∧ b) ∨ c"

def convert_equation_to_python(equation):
    new_eq = equation
    new_eq = new_eq.replace("~", " not ")
    new_eq = new_eq.replace("∨", " or ")
    new_eq = new_eq.replace("∧", " and ")
    new_eq = new_eq.replace("[", "(")
    new_eq = new_eq.replace("]", ")")
    new_eq = new_eq.replace("{", "(")
    new_eq = new_eq.replace("}", ")")
    new_eq = " " + new_eq + " "
    return new_eq

def get_sorted_variables(python_equation):
    variables = set()
    for index in range(len(python_equation)):
        c = python_equation[index]
        if c not in " ()^" and python_equation[index + 1] in " ()" and python_equation[index - 1] in " ()":
            variables.add(c)
    return sorted(variables)


equation = get_equation_from_user()
pyt_equation = convert_equation_to_python(equation)
equation_vars = get_sorted_variables(pyt_equation)

print('\t'.join(equation_vars) + '\t' + equation)

for vals in itertools.product(['0', '1'], repeat=len(equation_vars)):
    for eq, val in zip(equation_vars, vals):
        exec(eq + " = " + val)
    exec("result = " + pyt_equation)
    print('\t'.join(vals) + '\t' + str(1 if result else 0))