truth_tables.py

import warnings
import matplotlib.pyplot as plt
from typing import Callable, Dict, Iterable, List

warnings.filterwarnings("ignore")

Nodes: List['Node'] = []  # List of every node to make column for
Vars: Dict[str, bool] = {}  # Dictionary of every variable and its value


# Global Functions to interact with the Nodes.
# While this is not ideal, it makes the code a lot simpler
def Nodes_Reset():
    global Nodes, Vars
    Nodes = []
    Vars = {}


def Nodes_Add(node: 'Node'):
    global Nodes
    for n in Nodes:
        if n == node:
            return

    Nodes.append(node)
    Nodes.sort(key=lambda n: n.complexity())


# Outline for what a node class should do
class Node:
    TOKEN_MATCHES = []

    def __init__(self):
        Nodes_Add(self)

    def get(self) -> bool:
        pass

    def complexity(self) -> int:
        return 0

    def __str__(self) -> str:
        return ""

    def __repr__(self) -> str:
        name = str(self)
        return name[1:-1] if name[0] == '(' and name[-1] == ')' else name

    def __eq__(self, other: 'Node') -> bool:
        return False


# The end node is always a Variable, which is used to permutate the truth table
class Variable(Node):
    def __init__(self, name: str):
        self.name = name.lower().strip()
        Vars[self.name] = False

        super().__init__()

    def get(self) -> bool:
        return Vars[self.name]

    def complexity(self) -> int:
        return 0

    def __str__(self) -> str:
        return self.name

    def __eq__(self, other: Node) -> bool:
        return isinstance(other, Variable) and self.name == other.name


class Constant(Node):
    TOKEN_MATCHES = ['0', '1', 'f', 't', 'false', 'true']

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

    def get(self) -> bool:
        return self.value

    def complexity(self) -> int:
        return 0

    def __str__(self) -> str:
        return "⊤" if self.value else "⊥"

    def __eq__(self, other: Node) -> bool:
        return isinstance(other, Constant) and self.value == other.value


# Next most basic node type is Not, which just inverts the child node
class Not(Node):
    TOKEN_MATCHES = ['not', '-', '~', '!']

    def __init__(self, child: Node):
        self.child = child

        super().__init__()

    def get(self) -> bool:
        return not self.child.get()

    def complexity(self) -> int:
        return 1 + self.child.complexity()

    def __str__(self) -> str:
        return f"¬{str(self.child)}"

    def __eq__(self, other: Node) -> bool:
        return isinstance(other, Not) and self.child == other.child


# Operator Node that has two child nodes
class Operator(Node):
    def __init__(self, name: str, operation: Callable[[bool, bool], bool], commutative: bool, child_a: Node, child_b: Node):
        self.name = name

        self.operation = operation
        self.commutative = commutative

        self.child_a = child_a
        self.child_b = child_b

        super().__init__()

    def get(self) -> bool:
        return self.operation(self.child_a.get(), self.child_b.get())

    def complexity(self) -> int:
        return 2 + self.child_a.complexity() + self.child_b.complexity()

    def __str__(self) -> str:
        return f"({str(self.child_a)} {self.name} {str(self.child_b)})"

    def __eq__(self, other: Node) -> bool:
        return isinstance(other, Operator) and self.name == other.name and (
            (self.child_a == other.child_a and self.child_b == other.child_b) or
            (self.commutative and
             (self.child_a == other.child_b and self.child_b == other.child_a))
        )


# Various implementations for the Operator Node
class And(Operator):
    TOKEN_MATCHES = ["&", "&&", "and"]

    def __init__(self, child_a: Node, child_b: Node):
        super().__init__(
            name='∧',
            operation=lambda a, b: a and b,
            commutative=True,
            child_a=child_a,
            child_b=child_b
        )


class Or(Operator):
    TOKEN_MATCHES = ["|", "||", "or"]

    def __init__(self, child_a: Node, child_b: Node):
        super().__init__(
            name='∨',
            operation=lambda a, b: a or b,
            commutative=True,
            child_a=child_a,
            child_b=child_b
        )


class Xor(Operator):
    TOKEN_MATCHES = ["^", "xor"]

    def __init__(self, child_a: Node, child_b: Node):
        super().__init__(
            name='⊻',
            operation=lambda a, b: a != b,
            commutative=True,
            child_a=child_a,
            child_b=child_b
        )


class Nand(Operator):
    TOKEN_MATCHES = ["!&", "!&&", "nand"]

    def __init__(self, child_a: Node, child_b: Node):
        super().__init__(
            name='⊼',
            operation=lambda a, b: not (a and b),
            commutative=True,
            child_a=child_a,
            child_b=child_b
        )


class Nor(Operator):
    TOKEN_MATCHES = ["!|", "!||", "nor"]

    def __init__(self, child_a: Node, child_b: Node):
        super().__init__(
            name='⊽',
            operation=lambda a, b: not (a or b),
            commutative=True,
            child_a=child_a,
            child_b=child_b
        )


class Implies(Operator):
    TOKEN_MATCHES = ["->", "=>", "implies"]

    def __init__(self, child_a: Node, child_b: Node):
        super().__init__(
            name='→',
            operation=lambda a, b: not (a) or b,
            commutative=False,
            child_a=child_a,
            child_b=child_b
        )


class IfAndOnlyIf(Operator):
    TOKEN_MATCHES = ["<->", "<=>", "ifandonlyif", "!^", "nxor"]

    def __init__(self, child_a: Node, child_b: Node):
        super().__init__(
            name='↔',
            operation=lambda a, b: a == b,
            commutative=True,
            child_a=child_a,
            child_b=child_b
        )


# Create a list of every type of node
NodeSet = set(Node.__subclasses__())
for _ in range(16):
    for n in set(NodeSet):
        NodeSet.update(c for c in n.__subclasses__())


# Exception class used to raise parsing errors
class ParsingError(Exception):
    pass


# Find node type based on a token
def match_token_to_node(token) -> Node:
    for node in NodeSet:
        if token in node.TOKEN_MATCHES:
            return node

    raise ParsingError(f"Unknown Operator \"{token}\"!")


# Split text into tokens based on:
#   - Parenthesis [everything in matching parenthesis is an entire token]
#   - Spaces [everything not grouped by parenthesis is split by spaces]
def split_into_tokens(text) -> Iterable[str]:
    paren_count = 0
    start = 0

    for n, c in enumerate(text):
        if c in "{([":
            if paren_count == 0:
                token = text[start: n].strip().lower()
                if token:
                    yield token
                start = n + 1
            paren_count += 1

        if c in "})]":
            paren_count -= 1
            if paren_count == 0:
                token = text[start: n].strip().lower()
                if token:
                    yield token
                start = n + 1

        if paren_count == 0 and c == ' ':
            token = text[start: n].strip().lower()
            if token:
                yield token
            start = n + 1

    if paren_count != 0:
        if paren_count > 0:
            raise ParsingError(
                f"Mismatched Parenthesis in \"{text}\" [{+paren_count} too many \"(\"]")
        else:
            raise ParsingError(
                f"Mismatched Parenthesis in \"{text}\" [{-paren_count} too many \")\"]")

    token = text[start:].strip().lower()
    if token:
        yield token


# Build tree of nodes by splitting text into tokens and calling this function recursively
def build_tree(text) -> Node:
    # This handles empty strings / nodes
    if isinstance(text, Node):
        return text
    if not text:
        raise ParsingError("Malformed Equation")

    # Split text into tokens and concatenate not statements
    # The way not is handled is not ideal, but unless I want
    # to implement shunting yard this is what we get
    tokens: List[str] = list(split_into_tokens(text))

    for i in reversed(range(1, len(tokens))):
        if tokens[i - 1] in Not.TOKEN_MATCHES:
            tokens[i - 1] = Not(build_tree(tokens[i]))
            tokens[i] = None

    tokens = list(token for token in tokens if token)

    # If there is a single token,
    # it is either a variable, or a nested parenthesis
    if len(tokens) == 1:
        variable = tokens[0]
        if variable != text:
            return build_tree(variable)
        elif variable in ['1', 't', 'true', 'yes']:
            return Constant(True)
        elif variable in ['0', 'f', 'false', 'no']:
            return Constant(False)
        elif variable[0] in Not.TOKEN_MATCHES:
            return Not(build_tree(variable[1:]))
        else:
            return Variable(variable)

    # Begin working through the tokens left to right
    lhs = build_tree(tokens[0])
    tokens = tokens[1:]

    while 1 < len(tokens):
        op = match_token_to_node(tokens[0].lower())
        lhs = op(lhs, build_tree(tokens[1]))
        tokens = tokens[2:]

    if len(tokens) != 0:
        raise ParsingError("Unbalanced Operators!")

    return lhs


# Create a graphical truth table using the equations given
def create_table(equations: str):

    def get_bits(n: int, b: int):
        for _ in range(b):
            yield (n & 1) == 0
            n >>= 1

    Nodes_Reset()

    for equation in equations.split(';'):
        print(f"Built Table For: {build_tree(equation)}")

    column_labels = list(f" {repr(n)} " for n in Nodes)
    row_data = []

    for i in range(0, 2 ** len(Vars)):
        for bit, name in zip(get_bits(i, len(Vars)), reversed(Vars.keys())):
            Vars[name] = bit

        row_data.append(list(('■' if n.get() else '□') for n in Nodes))

    fig, ax = plt.subplots()
    fig.patch.set_visible(False)
    ax.axis('off')
    ax.axis('tight')
    table = ax.table(cellText=row_data, colLabels=column_labels,
                     loc='center', cellLoc='center')
    table.auto_set_font_size(False)
    table.set_fontsize(12)
    table.auto_set_column_width(col=list(range(len(column_labels))))

    fig.tight_layout()
    plt.show()


# Sample equations that get typed if you dnt type anything
i = 0
samples = [
    "(a ^ b) <-> (c ^ d)",
    "(a ^ b) ^ True; ~(a ^ b)",
    "(p or q) or !q",
    "(p -> q) and (q -> p); p <-> q",
    "p & (!q | (m <-> (p and !q)))",
]


# Print out supported operators
print("Supported Operators:")
for c in sorted(NodeSet, key=lambda a: a.__name__):
    if c.TOKEN_MATCHES:
        print(f"  - {c.__name__} {c.TOKEN_MATCHES}")


# Simple CLI to enter truth tables
while True:
    equation = input("\nEquation> ")

    if not equation:
        equation = samples[i]
        i = (i + 1) % len(samples)
        print(f"\033[AEquation> {equation}")

    try:
        create_table(equation)
    except ParsingError as e:
        print(f"Error: {str(e)}")