5
\$\begingroup\$

In of my software engineering classes, I had to write a truth table calculator in the language of my choice. This is what I came up with, and I would like to know what I should do better next time:

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)

I have a working version at IdeOne.

\$\endgroup\$

3 Answers 3

4
\$\begingroup\$

Let's proceed top-down. I'll suggest cleverer ways to do a bunch of stuff, but the review will culminate in the two most important points:

  • this is a huge security hole, and
  • you should organize your code into functions.

Introductory message

A good way to write a multiline string is using """the longstring""" syntax.

In this case, though, that introductory message could just as well be the docstring for the program. You could use the special __doc__ variable to fetch the docstring by introspection.

"""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__)

Note that "equation" is not the right word: you don't want a string with an equals sign. You just want a "boolean expression".

Canonicalizing the expression

Doing string substitutions in multiple passes is bad practice. In the best case, you waste a bit of effort making multiple passes over the string. In the worst case, passing previously substituted text through another round could be incorrect — though fortunately that's not the case here.

I recommend doing the substitution in one pass using a regular expression.

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()

Extracting the variables

This, too, can be simplified using a regular expression. \b[A-Za-z]\b looks for any single letter bounded by word boundaries on both sides.

In addition, deduplication is more elegant using a set.

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

Generating the boolean values

This is a perfect job for itertools.product(), and in fact the documentation has just such an example:

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

Evaluating the expression

First of all, you should use eval(), not exec(), since you want to evaluate the expression and get its value, rather than running some code for its side-effect. result = eval(expr) is better than exec('result = ' + expr).

Most importantly, though, calling eval() or exec() like that is a huge security hole — it lets the user execute arbitrary Python code. For example, the user might enter this to be executed:

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

The consensus is that Python can't be safely sandboxed. We can try to do better by evaluating the expression in a scope that contains just the relevant variables.

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

However, I suspect that even that won't be secure. The lambda keyword is still available, for example, and that makes me nervous. Ultimately, the only safe approach may be to write your own code to parse and evaluate the expression — Python itself is too powerful.

Suggested solution

As a final remark: the problem can be divided neatly into functions. Naming these chunks of work make your code easier to follow.

"""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())
\$\endgroup\$
1
  • \$\begingroup\$ I'd be tempted to split that re.sub into multiple logical lines (regex = re.compile('|'.join(...)); return regex.sub(...).strip()). Alternatively with the upcoming regex library you can do regex.sub(r"\L<chars>", ..., chars=REPLACEMENTS). \$\endgroup\$
    – Veedrac
    Jan 6, 2015 at 9:31
2
\$\begingroup\$

I was thinking about how to approach the eval problem safely, and it occurred to me that the best way to avoid building a parser would be too hook into Python's ast module. There is a convenient NodeVisitor class that can let us do recursive evaluation of a tree. This is somewhat fiddly so I'll just give you what I came up with.

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]

Used like:

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

This hooks into 200_success' version quite neatly.

Also note that currently you support

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

By using a well-defined API you can avoid such strange results and give better errors messages. Even better would be building a parser yourself, but that sounds a touch harder.

I would also consider doing substitutions and finding all name tokens at the token level simply because it allows supporting things like

abc∨def

which currently throws an unhappy error. You could also do whitelisting at the same time, further reducing the amount of unwanted computation that can happen. This is a bit long because each case needs dealing with separately but the cases themselves are rather straightforward:

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)

Usage requires tokenization:

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

and then you pass it through before detokenizing:

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

The result of both of these is that you force a rather strong well-formedness requirement on input and it's basically impossible for input to do something bad. Errors are also better and identifiers can be of any length.

The one thing I can think of that isn't covered by this is that it still allows improperly matched brackets:

[ a )

If bracketing substitution was done at the AST level, this would be dealt with by ast.parse but it would rather hacky. A better option might be keeping a bracket stack during transform_token.

\$\endgroup\$
1
\$\begingroup\$

Here's a draft for an improved version of your code. I'll comment on things I have changed as soon as I have time. Also, many things are still to be done like getting rid of exec.

Well, actually, 200_success said it all.

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))
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.