Creating truth table from a logical statement

This code creates a truth table from a statement in logic. The statement is input as a string, and it is identified as a tautology if it is true for all true and false combinations of the variables.

Note: brackets must contain only one logical operator. For example, \$(A \lor B \lor C)\$ does not work, but \$(A \lor B) \lor C\$ does.

```
import itertools
import re
from tabulate import tabulate
from collections import OrderedDict

symbols = {'∧', '∨', '→', '↔'} # Symbols for easy copying into logical statement

statement = '~(A ∧ B) ↔ (~A ∨ ~B)'

def parenthetic_contents(string):
"""
From http://stackoverflow.com/questions/4284991/parsing-nested-parentheses-in-python-grab-content-by-level

Generates parenthesized contents in string as pairs (level, contents).

>>> list(parenthetic_contents('~(p ∨ q) ↔ (~p ∧ ~q)')
[(0, 'p ∨ q'), (0, '~p ∧ ~q')]
"""
stack = []
for i, char in enumerate(string):
if char == '(':
stack.append(i)
elif char == ')' and stack:
start = stack.pop()
yield (len(stack), string[start + 1: i])

def conditional(p, q):
"""Evaluates truth of conditional for boolean variables p and q."""
return False if p and not q else True

def biconditional(p, q):
""" Evaluates truth of biconditional for boolean variables p and q."""
return (True if p and q
else True if not p and not q
else False)

def and_func(p, q):
""" Evaluates truth of AND operator for boolean variables p and q."""
return p and q

def or_func(p, q):
""" Evaluates truth of OR operator for boolean variables p and q."""
return p or q

def negate(p):
""" Evaluates truth of NOT operator for boolean variables p and q."""
return not p

def apply_negations(string):
"""
Applies the '~' operator when it appears directly before a binary number.

>>> apply_negations('~1 ∧ 0')
'0 ∧ 0'
"""
new_string = string[:]
for i, char in enumerate(str

1. Bugs

-
There's an infinite loop in solve:

>>> get_truth_table('AB')
^C
  File "", line 1, in 
  File "cr145465.py", line 215, in get_truth_table
    answer = solve(valued_statement)
  File "cr145465.py", line 190, in solve
    valued_statement = simplify(valued_statement)
  File "cr145465.py", line 170, in simplify
    return str(eval_logic(valued_statement))
KeyboardInterrupt

The problem is here:

while len(valued_statement) > 1:
    valued_statement = simplify(valued_statement)

Of course the input 'AB' is invalid, but I would expect to get a SyntaxError instead of an infinite loop.

-
Other inputs containing syntax errors result in exceptions that are hard to understand. For example:

>>> get_truth_table('')
Traceback (most recent call last):
  File "", line 1, in 
  File "cr145465.py", line 206, in get_truth_table
    if statement[0] != '(':
IndexError: string index out of range

Another example:

>>> get_truth_table('~~A')
Traceback (most recent call last):
  File "cr145465.py", line 97, in eval_logic
    return int(boolean) # Return boolean as 0 or 1
UnboundLocalError: local variable 'boolean' referenced before assignment

During handling of the above exception, another exception occurred:

Traceback (most recent call last):
  File "", line 1, in 
  File "cr145465.py", line 215, in get_truth_table
    answer = solve(valued_statement)
  File "cr145465.py", line 190, in solve
    valued_statement = simplify(valued_statement)
  File "cr145465.py", line 174, in simplify
    bool_string = str(eval_logic(string))
  File "cr145465.py", line 100, in eval_logic
    return int(string) # Return the value of the string itself
ValueError: invalid literal for int() with base 10: '~0'

-
Some incorrect inputs succeed but produce meaningless results:

>>> get_truth_table('7')
([[7]], False)

When invalid input is encountered, it is a good idea to raise a SyntaxError with an explanation of the problem.

1. Alternative approach

I'm not going to review the code in any detail, because the approach taken here (repeated string substitution) is slow and fragile and hard to get good error messages out of.

So instead, I'm going to demonstrate the standard way to tackle this kind of problem. The idea is to combine three processing stages:

-
Tokenization. In this stage the input string is turned into a sequence of tokens. For example, given this input:

~(A ∧ B) ↔ (~A ∨ ~B)

the tokenizer might emit this sequence of tokens:

'~', '(', 'A', '∧', 'B', ')', '↔', '(', '~', 'A', '∨', '~', 'B', ')', 

-
Parsing. In this stage the sequence of tokens is turned into a parse tree, a data structure corresponding to the syntactic structure of the input. For example, given the input above, the parser might construct the following data structure:

BinaryOp(
    left=UnaryOp(
        op=,
        operand=BinaryOp(
            left=Variable(name='A'),
            op=,
            right=Variable(name='B'))),
    op=,
    right=BinaryOp(
        left=UnaryOp(
            op=,
            operand=Variable(name='A')),
        op=,
        right=UnaryOp(
            op=,
            operand=Variable(name='B'))))

-
Expression evaluation. This stage takes a parse tree for an expression, together with an environment (a data structure mapping variables to their values), and returns the value of the expression.

There are several good reasons to solve the problem using this approach:

-
It's the standard approach, so other programmers will easily understand how it works.

-
It's efficient: each stage needs to pass over its input exactly once, thus avoiding the repeated string substitutions of the code in the post.

-
Splitting the work into steps with clearly defined inputs and outputs makes it easier to test.

-
The approach extends to more complicated applications, such as interpretation of programming languages.

1. Tokenization

Tokenization is often implemented using a finite-state machine but it's also often convenient to use a regular expression.

import re

# Regular expression matching optional whitespace followed by a token
# (if group 1 matches) or an error (if group 2 matches).
TOKEN_RE = re.compile(r'\s*(?:([A-Za-z01()~∧∨→↔])|(\S))')

# Special token indicating the end of the input string.
TOKEN_END = ''

def tokenize(s):
    """Generate tokens from the string s, followed by TOKEN_END."""
    for match in TOKEN_RE.finditer(s):
        token, error = match.groups()
        if token:
            yield token
        else:
            raise SyntaxError("Unexpected character {!r}".format(error))
    yield TOKEN_END

1. Parsing

Before you can write a parser, you need to make a formal grammar. This is probably the most difficult bit of the whole thing. Here's the grammar that I'm going to use, written in Backus–Naur form:

-
〈Variable〉 ::= "A" | "B" | … | "Z" | "a" | "b" | ... | "z"

-
〈Constant〉 ::= "0" | "1"

-
〈Term〉 ::= 〈Vari

StackExchange Code Review Q#145465, answer score: 7