Learn to Code via Tutorials on Repl.it

← Back to all posts
Python - Discrete Math Logic Parser
FellowHashbrown (38)

(Python) Discrete Math Logic Parser

What is Discrete Math Logic?

Discrete Math Logic is a basic form of logic. In its simplest form, it can be represented by p ^ q
In discrete math, the basic operators are:

  • ^ (which denotes AND)
  • v (which denotes OR)
  • ~ (which denotes NOT)

There are more operators that exist but for this tutorial, we will only cover these simple ones. If you want to include the other operators, I will have them at the end of this post along with the code for each operator.

Requirements

  • Basic Knowledge of Python
    • Classes
    • Functions
  • Knowledge of Recursion

Logic Parser Layout

Now for this tutorial, we are going to have 4 different python files.

  • errors.py which will hold all the Exceptions we will use
  • logic_var.py which will hold the class for a variable such as a or b
  • logic_node.py which will be the basics for a left and right logical expression such as a ^ b
  • logic_tree.py which will be the primary class for a logical expression

Now we can get started with the tutorial.


errors.py

Now this is the simple stuff. All we really have in this file are just four simple classes that extend Python's Exception object.

class UnbalancedParentheses(Exception): pass
class MissingTruthValue(Exception): pass
class OperatorMismatch(Exception): pass
class MissingValue(Exception): pass

And we're done with that part! That was easy.


logic_var.py

In this file, we have a LogicVar class that will hold all information about a single variable in a logical expression.
This class is very simple as we only have 2 attributes that a LogicVar object holds:

  • Whether or not it has a ~ (NOT) operator attached to it
  • The variable itself

I'm going to layout the contents of each set of functions so hopefully you understand it better.

class LogicVar:
    
    def __init__(self, value = None, has_not = False, *, var_dict = None):
        
        # If the value is given, we are loading it in by the value and has_not parameters
        if value != None:
            self._value = value
            self._has_not = has_not
        
        # If the var_dict is given, we are recursively initializing this LogicVar.
        elif var_dict != None:
            
            # Try loading the value key from var_dict
            try:
                self._value = var_dict["value"]
            except:
                raise MissingValue("Required key for LogicVar. Must have \"value\" key in var_dict.")
            
            # Try loading the has_not key from var_dict
            try:
                self._has_not = var_dict["has_not"]
            except:
                self._has_not = has_not
            
        # If both value and var_dict are missing, we raise an Exception
        elif value == None and var_dict == None:
            raise MissingValue("Required variable for LogicVar. Must use either value or var_dict.")
    
    def __str__(self):
        if self.has_not():
            return "~" + self.get_value()
        return self.get_value()
    
    def __eq__(self, value):
        if not isinstance(value, LogicVar):
            return False
        
        return (
            self.get_value() == value.get_value() and
            self.has_not() == value.has_not()
        )
...

All these functions are built-in functions for Python classes.
The __eq__ function is overridden so we can compare a LogicVar object with some other object later on.
The __str__ function is overridden so we can easily print out a LogicVar object when we print the parsed expression.

...
    def get_value(self):
        return self._value
    
    def has_not(self):
        return self._has_not
...

These functions should be pretty straight forward. They are just getter methods for a LogicVar object.

...
    def evaluate(self, truth_value = {}):
        
        if self.get_value() not in truth_value:
            raise MissingTruthValue("Required truth value for the variable \"{}\"".format(self.get_value()))
        
        if self.has_not():
            return not truth_value[self.get_value()]
        
        return truth_value[self.get_value()]
    
    def get_truth_values(self, truth_values = []):
        
        # Keep track of evaluations
        evaluations = []
        
        # Only run this if there is a has_not
        if self.has_not():
        
            # Iterate through truth values
            for truth_value in truth_values:
                
                # Evaluate the value given by this LogicVar
                evaluation = {
                    "expression": str(self),
                    "truth_value": truth_value,
                    "value": self.evaluate(truth_value)
                }
                
                # Only add the evaluation if it doesn't already exist
                if evaluation not in evaluations:
                    evaluations.append(evaluation)
        
        return evaluations

Now the evaluate function will be given a dictionary of truth values to use to evaluate.
For example, let's say that there is a LogicVar object whose variable is a,
when the evaluate function runs, there is a truth_value given to it such as:

{
    "a": True,
    "b": True
}

A truth value dictionary just holds the truth values for all the variables that exist in a logical expression.

The get_truth_values function will run through all the possible truth values that exist for a logical expression.
It depends on the amount of variables where this comes from.
To explain better, let's say we are given an expression such as a ^ b
All the possible truth values include:

| a | b |
|---+---|
| T | T |
| T | F |
| F | T |
| F | F |

So there are 2ⁿ possible combinations of truth values and that is where the list of truth values comes from.


logic_node.py

Now this file holds the information behind a logical expression such as a ^ b.
In that expression, a would be the left side, b would be the right side, and ^ would be the operator.
This is exactly what the LogicNode class holds

class LogicNode:

    def __init__(self, operator = None, left = None, right = None, has_not = False, *, node_dict = None):
    
        # If operator, left, and right are given, we are loading it in by those parameters
        if operator != None and left != None and right != None:
            self._operator = operator
            self._left = left
            self._right = right
            self._has_not = has_not
        
        # If node_dict is given, we are recursively initializing this LogicNode.
        elif node_dict != None:
            
            # Try loading operator
            try:
                self._operator = node_dict["operator"]
            except:
                raise MissingValue("Required key for LogicNode. Must have \"operator\" key in node_dict.")
            
            # Try loading left
            try:
                self._left = node_dict["left"]
            except:
                raise MissingValue("Required key for LogicNode. Must have \"left\" key in node_dict.")
            
            # Try loading right
            try:
                self._right = node_dict["right"]
            except:
                raise MissingValue("Required key for LogicNode. Must have \"right\" key in node_dict.")
            
            # Try loading has_not
            try:
                self._has_not = node_dict["has_not"]
            except:
                self._has_not = has_not
        
        # If operator, left, right, and node_dict are all missing, raise an Exception
        elif (operator == None or left == None or right == None) or node_dict == None:
            raise MissingValue("Required variable(s) for LogicNode. Must use either operator, left, and right or node_dict.")
        
        # Turn the left and right values into either `LogicNode` or `LogicVar` objects
        if isinstance(self._left, dict):
            if "value" in self._left:
                self._left = LogicVar(var_dict = self._left)
            else:
                self._left = LogicNode(node_dict = self._left)
        
        if isinstance(self._right, dict):
            if "value" in self._right:
                self._right = LogicVar(var_dict = self._right)
            else:
                self._right = LogicNode(node_dict = self._right)
    
    def __str__(self):
        left = str(self.get_left())
        right = str(self.get_right())
        
        # Only put parentheses around expressions that don't have a ~ (NOT) operator attached to it
        if isinstance(self.get_left(), LogicNode) and not self.get_left().has_not():
            left = "(" + left + ")"
        if isinstance(self.get_right(), LogicNode)  and not self.get_right().has_not():
            right = "(" + right + ")"
            
        operator = self.get_operator()
        
        if self.has_not():
            return "~({} {} {})".format(
                left, operator, right
            )
        
        return "{} {} {}".format(
            left, operator, right
        )
    
    def __eq__(self, value):
        if not isinstance(value, LogicNode):
            return False
        
        return (
            self.get_left() == compare.get_left() and
            self.get_right() == compare.get_right() and
            self.get_opoerator() == compare.get_operator() and
            self.has_not() == compare.has_not()
        )
...

Again, this just sets up the LogicNode class and any object that is an instance of it.
Notice that in the __init__ method, the left and right parameters would normally take in a LogicNode or LogicVar object as the parameter. The way I will show how to load it in is using the node_dict keyword parameter.That will be shown in the next portion for the LogicTree class.

...
    def get_operator(self):
        return self._operator
    
    def get_left(self):
        return self._left
    
    def get_right(self):
        return self._right
    
    def has_not(self):
        return self._has_not
...

More getter methods! There's really no need to explain this but I added it in just so there's not missing code for this tutorial.

...
    def evaluate(self, truth_value = {}):
        left = self.get_left().evaluate(truth_value)
        right = self.get_right().evaluate(truth_value)
        
        if self._operator == "^":
            if self.has_not():
                return not (left and right)
            return left and right
        
        if self._operator == "v":
            if self.has_not():
                return not (left or right)
            return left or right
    
    def get_truth_values(self, truth_values = []):
        
        # Keep track of evaluations
        evaluations = []
        
        # Get left evaluations
        left_evaluations = self.get_left().get_truth_values(truth_values)
        for left_evaluation in left_evaluations:
            if left_evaluation not in evaluations:
                evaluations.append(left_evaluation)
            
        # Get right evaluations
        right_evaluations = self.get_right().get_truth_values(truth_values)
        for right_evaluation in right_evaluations:
            if right_evaluation not in evaluations:
                evaluations.append(right_evaluation)
        
        # Iterate through truth values
        for truth_value in truth_values:
            
            # Evaluate this LogicNode object
            evaluation = {
                "expression": str(self),
                "truth_value": truth_value,
                "value": self.evaluate(truth_value)
            }
            
            # Only add the evaluation if it doesn't already exist
            if evaluation not in evaluations:
                evaluations.append(evaluation)
        
        return evaluations

Now the evaluate method in the LogicNode class will take into account the operator of the expression.
So if the expression held in the LogicNode is an ^ (AND) operator, then it will evaluate the left recursively until it hits any LogicVar objects, and finally it will evaluate the right recursively.
If there is a ~ (NOT) operator attached to the LogicNode object, it will handle that as well.

The get_truth_values method will recursively evaluate both the left and right sides of the LogicNode object and then it will evaluate itself. Again, it will only add any evaluations that haven't already been made before. This is used when creating a truth table in the LogicTree class. It is helpful for sure when using it to evaluate a logical expression.


logic_tree.py

Now comes the almost-grand finale of this tutorial: The LogicTree class which is the root of the expresssion parsing.

class LogicTree:
    
    def __init__(self, expression):
        self._expression = expression
        self._variables = []
        self._root = None
        self.parse()
    
    def __str__(self):
        return str(self._root)
    
    def __eq__(self, value):
        
        if not isinstance(value, LogicTree):
            return False
        
        return (
            self.get_expression() == value.get_expression() and
            self.get_variables() == value.get_variables() and
            self._root == value._root
        )
    
    
    def get_expression(self):
        return self._expression
    
    def get_variables(self):
        return self._variables
...

This time I merged the getters in with the built-in methods only because the bulk of the code in this class isn't in the basics of the class.

...
    def parse(self):
        
        expression = parse_expression(self.get_expression())
        expression = expression["expression"]
        variables = expression["variables"]
        
        self._root = LogicNode(node_dict = expression)
        self._variables = variables
        self._expression = str(self._root)
    
    def make_table(self):
    
        lines = []
        result = ""
        
        # Evaluate the root LogicNode
        evaluations = self.get_truth_values()
        table_dict = {}
        for evaluation in evaluations:
            if evaluation["expression"] not in table_dict:
                table_dict[evaluation["expression"]] = []
            
            table_dict[evaluation["expression"]].append(evaluation["value"])
        
        # Add column labels
        count = 0
        length = len(table_dict)
        for column in table_dict:
            line = "| " + column.center(len(column))
            if count > 0:
                line = " " + line
            elif count == length - 1:
                line += " |"
            result += line
            count += 1
        lines.append(result)
        result = ""
        
        # Add label split line
        count = 0
        for column in table_dict:
            line = "+" + "-".center(len(column) + 1, "-")
            if count > 0:
                line = "-" + line
            elif count == length - 1:
                line += "-+"
            result += line
            count += 1
        lines.append(result)
        result = ""
    
        # Add truth values
        max_truths = -1
        for column in table_dict:
            if max_truths == -1:
                max_truths = len(table_dict[column])
                break
        
        for index in range(max_truths):
            count = 0
            for column in table_dict:
                value = table_dict[column][index]
                if value:
                    value = "T"
                elif value == False:
                    value = "F"
                else:
                    value = "-"
                line = "| " + value.center(len(column))
                if count > 0:
                    line = " " + line
                elif count == length - 1:
                    line += " |"
                result += line
                count += 1
            lines.append(result)
            result = ""
        
        return lines
...

Now this code may seem confusing at first but I'll break it down into what each section does.

        # Evaluate the root LogicNode
        evaluations = self.get_truth_values()
        table_dict = {}
        for evaluation in evaluations:
            if evaluation["expression"] not in table_dict:
                table_dict[evaluation["expression"]] = []
            
            table_dict[evaluation["expression"]].append(evaluation["value"])

This code segment will just evaluate itself and get a list of truth values from the LogicNode object held in the self._root variable. The get_truth_values method will actually run all the evaluations for said object.

        # Add column labels
        count = 0
        length = len(table_dict)
        for column in table_dict:
            line = "| " + column.center(len(column))
            if count > 0:
                line = " " + line
            elif count == length - 1:
                line += " |"
            result += line
            count += 1
        lines.append(result)
        result = ""

This code segment will create the table labels in a truth table.
For example, say your expression was a ^ b
The resulting label would look like this:

| a | b | a ^ b |

It looks exactly as you would write a regular truth table!

        # Add label split line
        count = 0
        for column in table_dict:
            line = "+" + "-".center(len(column) + 1, "-")
            if count > 0:
                line = "-" + line
            elif count == length - 1:
                line += "-+"
            result += line
            count += 1
        lines.append(result)
        result = ""

This code segment will add a line that separates the variable or expression in the label from the truth values.
For example, we'll add onto the previous truth table:

| a | b | a ^ b |
+---+---+-------+

That just adds that last little line and makes it neat in raw text.

        # Add truth values
        max_truths = -1
        for column in table_dict:
            if max_truths == -1:
                max_truths = len(table_dict[column])
                break
        
        for index in range(max_truths):
            count = 0
            for column in table_dict:
                value = table_dict[column][index]
                if value:
                    value = "T"
                elif value == False:
                    value = "F"
                else:
                    value = "-"
                line = "| " + value.center(len(column))
                if count > 0:
                    line = " " + line
                elif count == length - 1:
                    line += " |"
                result += line
                count += 1
            lines.append(result)
            result = ""

Now this next code segment has 2 parts.
The first part,

        max_truths = -1
        for column in table_dict:
            if max_truths == -1:
                max_truths = len(table_dict[column])
                break

will find the maximum amount of truth values that are given from an expression.
For example,

| a | b |
+---+---+
| T | T |
| T | F |
| F | T |
| F | F |

this truth table would have 4 truth values to go through.

The next part,

        for index in range(max_truths):
            count = 0
            for column in table_dict:
                value = table_dict[column][index]
                if value:
                    value = "T"
                elif value == False:
                    value = "F"
                else:
                    value = "-"
                line = "| " + value.center(len(column))
                if count > 0:
                    line = " " + line
                elif count == length - 1:
                    line += " |"
                result += line
                count += 1
            lines.append(result)
            result = ""

will add all the other truth values to the table itself.
So if you took the expression from above, a ^ b
The final truth table would look like this:

| a | b | a ^ b |
+---+---+-------+
| T | T |   T   |
| T | F |   F   |
| F | T |   F   |
| F | F |   F   |

Now we'll move on to the get_truth_value and get_truth_values methods. This is where the height of the truth table comes from and how we manage to create every combination (not permutation) of truth values.

def get_truth_value(value, power):
    return ((value // 2 ** power) % 2) == 0

This will be used in a for loop that iterates through 2ⁿ combinations for each truth value.
To simplify that, we'll use three different tables to express this.

1 variable has 2 possible truth values

| a |
+---+
| T |
| F |

2 variables have 4 possible truth values

| a | b |
+---+---+
| T | T |
| T | F |
| F | T |
| F | F |

3 variables have 8 possible truth values

| a | b | c |
+---+---+---+
| T | T | T |
| T | T | F |
| T | F | T |
| T | F | F |
| F | T | T |
| F | T | F |
| F | F | T |
| F | F | F |

As you can see, we want to be able to hop back and forth between each True or False value for however many variables are in the expression.

Now let's get to the code for the get_truth_values method.

...
    def get_truth_values(self):
    
        # Create every possible truth combination for all variables
        truth_values = []

        # Iterate through 2 ** variable_amount possible combinations
        for value in range(2 ** len(self.get_variables())):

            # Iterate through all variables
            value_dict = {}
            for index in range(len(self.get_variables())):

                # Get the power based off of the variable's index in the list
                power = len(self.get_variables()) - index - 1
                variable = self.get_variables()[index]

                # Get the truth value using the get_truth_value function
                value_dict[variable] = get_truth_value(value, power)
            
            truth_values.append(value_dict)
        
        # Create truth values for other operations
        # For example, if there is a "~a", then there will be a column designated to that.
        #              if there is a "~(a v b)", then there will be a column designated to that
        #                 as well as the "a v b" part.
        truth_evaluations = []

        root_truth_evaluations = self._root.get_truth_values(truth_values)

        # Add all the truth evaluations from the root
        for truth_evaluation in root_truth_evaluations:
            if truth_evaluation not in truth_evaluations:
                truth_evaluations.append(truth_evaluation)
            
        # Add all the truth values as evaluations
        for truth_value in truth_values:
            for truth_variable in truth_value:
                truth_evaluation = {
                    "expression": truth_variable,
                    "truth_value": {
                        truth_variable: truth_value[truth_variable]
                    },
                    "value": truth_value[truth_variable]
                }
                
                truth_evaluations.append(truth_evaluation)
        
        truth_evaluations = sorted(truth_evaluations, key = lambda i: len(i["expression"])) 
        
        return truth_evaluations

We'll go segment by segment to explain this method.

        # Create every possible truth combination for all variables
        truth_values = []

        # Iterate through 2 ** variable_amount possible combinations
        for value in range(2 ** len(self.get_variables())):

            # Iterate through all variables
            value_dict = {}
            for index in range(len(self.get_variables())):

                # Get the power based off of the variable's index in the list
                power = len(self.get_variables()) - index - 1
                variable = self.get_variables()[index]

                # Get the truth value using the get_truth_value function
                value_dict[variable] = get_truth_value(value, power)
            
            truth_values.append(value_dict)

This code segment will create each dictionary for the combination of truth values given by how many variables there are.
So the elements in the list that is used to evaluate expressions would match the first n columns where n is the number of different variables.
So if the first row of the expression a ^ b would be:

| a | b |
+---+---+
| T | T |

and the matching dictionary would be:

{
    "a": True,
    "b": True
}

This will repeat for all the rows in the truth table.

        # Create truth values for other operations
        # For example, if there is a "~a", then there will be a column designated to that.
        #              if there is a "~(a v b)", then there will be a column designated to that
        #                 as well as the "a v b" part.
        truth_evaluations = []

        root_truth_evaluations = self._root.get_truth_values(truth_values)

        # Add all the truth evaluations from the root
        for truth_evaluation in root_truth_evaluations:
            if truth_evaluation not in truth_evaluations:
                truth_evaluations.append(truth_evaluation)

As the first comment says, any variables with a ~ (NOT) operator attached to it will have their own column designated to it. This is to make it more like a truth table that you would write yourself to simplify the boolean evaluations.
Again, it will only add evaluations that haven't already been evaluated. If we didn't check for that, there would be an endless amount of columns that exist.

        # Add all the truth values as evaluations
        for truth_value in truth_values:
            for truth_variable in truth_value:
                truth_evaluation = {
                    "expression": truth_variable,
                    "truth_value": {
                        truth_variable: truth_value[truth_variable]
                    },
                    "value": truth_value[truth_variable]
                }
                
                truth_evaluations.append(truth_evaluation)
        
        truth_evaluations = sorted(truth_evaluations, key = lambda i: len(i["expression"])) 

Now this last segment will add all the truth values for a single variable into it's own evaluation.
The final line uses Python's built-in sorted method to sort the expressions by their lengths in order to show the build up to the final expression which is the one you want to evaluate.

I know this has already been a long tutorial but just hold off for a few more explanations.
The method that actually does the parsing, parse_expression, isn't too complex but it definitely requires some explanation or else you might be lost.

def parse_expression(expression, has_not = False):

    # Remove all spaces from the expression
    expression = expression.replace(" ", "")
    
    # Loop through and find any ^ (AND) or v (OR) operators as expressions
    has_not = has_not
    left = None
    operator = None
    right = None
    variables =[]

    parent_depth = 0
    last = 0

    char_has_not = False
    temp_has_not = False

    for index in range(len(expression)):
        char = expression[index]

        # Check for open parenthesis
        if char == "(":
            if parent_depth == 0:
                last = index + 1
            parent_depth += 1
        
        # Check for close parenthesis
        elif char == ")":
            parent_depth -= 1

            # Parse expression if parenthesis depth reaches 0
            if parent_depth == 0:

                # Check if there is a ~ (NOT) operator directly in front of the parenthesis
                if last - 1 > 0:
                    if expression[last - 2] == "~":
                        temp_has_not = True
                
                exp = parse_expression(expression[last: index], temp_has_not)
                if index == len(expression) - 1 and last == 0:
                    has_not = temp_has_not
                temp_has_not = False

                # Check if there is no operator; Must be left side
                if operator == None:
                    left = exp["expression"]
                else:
                    right = exp["expression"]
        
        # No parenthesis depth anymore
        if parent_depth == 0:
            
            # Check for operator only if not within a parenthesis
            if char in ["^", "v"]:

                # Check if operator does not exist yet
                if operator == None:
                    if char == "^":
                        operator = "^"
                    elif char == "v":
                        operator = "v"
                
                # Operator exists; String of logical expressions exists
                # Make the left, operator, right into the left expression
                else:
                    left = {
                        "has_not": has_not,
                        "left": left,
                        "operator": operator,
                        "right": right
                    }

                    if char == "^":
                        operator = "^"
                    elif char == "v":
                        operator = "v"

                    right = None
                    has_not = False
        
        # Check for variable only if not within parentheses
        if ord(char) in range(ord('a'), ord('z') + 1) and ord(char) != ord('v'):

            # See if there is a ~ (NOT) operator directly in front of the variable
            if index > 0:
                if expression[index - 1] == "~":
                    char_has_not = True
                else:
                    char_has_not = False
            
            # Check if there is no operator; Must be left side
            if operator == None:
                left = {
                    "has_not": char_has_not,
                    "value": char
                }
            else:
                right = {
                    "has_not": char_has_not,
                    "value": char
                }
            
            char_has_not = False
            
            if char not in variables:
                variables.append(char)
    
    if parent_depth != 0:
        raise UnbalancedParentheses("You have a missing parenthesis somewhere.")
    
    variables.sort()

    # Check if the expression is a single expression wrapped in parentheses
    if operator == right == None:
        has_not = left["has_not"]
        operator = left["operator"]
        right = left["right"]
        left = left["left"]
    
    return {
        "expression": {
            "has_not": has_not,
            "left": left,
            "operator": operator,
            "right": right
        },
        "variables": variables
    }

Now let's go step-by-step to explain what is going on.

    # Remove all spaces from the expression
    expression = expression.replace(" ", "")
    
    # Loop through and find any ^ (AND) or v (OR) operators as expressions
    has_not = has_not
    left = None
    operator = None
    right = None
    variables = []

    parent_depth = 0
    last = 0

    char_has_not = False
    temp_has_not = False

This is just the basic setup. All the variables we need, all the temporary variables we need. The reason for the has_not in the parameter will be explained in a little bit.

    for index in range(len(expression)):
        char = expression[index]

        # Check for open parenthesis
        if char == "(":
            if parent_depth == 0:
                last = index + 1
            parent_depth += 1
        
        # Check for close parenthesis
        elif char == ")":
            parent_depth -= 1

            # Parse expression if parenthesis depth reaches 0
            if parent_depth == 0:

                # Check if there is a ~ (NOT) operator directly in front of the parenthesis
                if last - 1 > 0:
                    if expression[last - 2] == "~":
                        temp_has_not = True
                
                exp = parse_expression(expression[last: index], temp_has_not)
                if index == len(expression) - 1 and last == 0:
                    has_not = temp_has_not
                temp_has_not = False

                # Check if there is no operator; Must be left side
                if operator == None:
                    left = exp["expression"]
                else:
                    right = exp["expression"]

Now the loop obviously goes through the expression as a whole which is stripped of whitespace so any spaces you put in an expression is just immediately removed.

The first if statement, if char == "(", will help to keep track of the expression that is bound in parentheses. It will only match with the one that is at the same depth as it so if you have parentheses within parentheses, they will each get evaluated separately.

The second if statement, if char == ")", will determine if the current parenthesis closes off the parent parenthesis based off the parent_depth. If it does, then it will determine if there is a ~ (NOT) operator directly attached to it and will recursively parse through whatever is within the parenthesis. It will not include the initial set of parentheses or else that would cause infinite recursion and we don't want that.

After the recursive call completes, it will reset the has_not variable. If we don't do that, we get incorrect expressions for specific original expressions.
For example, if the original expression was ~(a ^ b) ^ c, the parser would assume that the entire expression has a ~ (NOT) operator attached to it and when you printed that out, it would be ~(~(a ^ b) ^ c).

Finally, it will determine if the parsed expression belongs to the left side or the right side based off if there is an operator or not.

        # No parenthesis depth anymore
        if parent_depth == 0:
            
            # Check for operator only if not within a parenthesis
            if char in ["^", "v"]:

                # Check if operator does not exist yet
                if operator == None:
                    if char == "^":
                        operator = "^"
                    elif char == "v":
                        operator = "v"
                
                # Operator exists; String of logical expressions exists
                # Make the left, operator, right into the left expression
                else:
                    left = {
                        "has_not": has_not,
                        "left": left,
                        "operator": operator,
                        "right": right
                    }

                    if char == "^":
                        operator = "^"
                    elif char == "v":
                        operator = "v"

                    right = None
                    has_not = False

Once the parenthesis depth reaches 0, it will find if there is an operator yet to get.
The else statement is there in case you have an expression that doesn't include parentheses but has more than two variables to evaluate.
For example, if you give the parser a ^ b ^ c, it will automatically put the a ^ b in the left side and the resulting expression will look like this: (a ^ b) ^ c. An easy way to get around that is by placing your own parentheses.

        # Check for variable only if not within parentheses
        if ord(char) in range(ord('a'), ord('z') + 1) and ord(char) != ord('v'):

            # See if there is a ~ (NOT) operator directly in front of the variable
            if index > 0:
                if expression[index - 1] == "~":
                    char_has_not = True
                else:
                    char_has_not = False
            
            # Check if there is no operator; Must be left side
            if operator == None:
                left = {
                    "has_not": char_has_not,
                    "value": char
                }
            else:
                right = {
                    "has_not": char_has_not,
                    "value": char
                }
            
            char_has_not = False
            
            if char not in variables:
                variables.append(char)

This segment will only run if it is not in parentheses.
What it will do is find any letter that is not the letter v (this is used as the OR operator) and add that to the list of variables which is used in the parse method mentioned earlier.
It will then determine if the variable given will belong to the left or right side of the expression.

Last, but not least, we have the final part of the parse_expression method. (yippee kayak!)

    if parent_depth != 0:
        raise UnbalancedParentheses("You have a missing parenthesis somewhere.")
    
    variables.sort()

    # Check if the expression is a single expression wrapped in parentheses
    if operator == right == None:
        has_not = left["has_not"]
        operator = left["operator"]
        right = left["right"]
        left = left["left"]
    
    return {
        "expression": {
            "has_not": has_not,
            "left": left,
            "operator": operator,
            "right": right
        },
        "variables": variables
    }

If the for loop reaches the end of the expression and the parent_depth is not 0, it will obviously raise an error because you can't have an unclosed parenthesis!
Then it will sort the variables in place so the truth table, when created, will show each variable in ascending order.

The if statement there, if operator == right == None, is for any expression that might be enclosed in parentheses for no apparent reason or if the expression as a whole has a ~ (NOT) operator attached to it.
For example, ~(a ^ b) would be properly processed as the whole expression.

Then obviously the return statement will give you the expression and all its attributes and the variables that are in the expression itself.


Other Discrete Math Operators

  • Implies (->)
    •  if self._operator == "->":
           if self.has_not():
               return not (not left or right)
           return not left or right
  • Biconditional (<->)
    •  if self._operator == "<->":
           if self.has_not():
               return not (left == right)
           return left == right
  • NAND (|)
    •  if self._operator == "|":
           if self.has_not():
               return left and right
           return not (left and right)
  • NOR (⬇)

    •  if self._operator == "⬇":
           if self.has_not():
               return left or right
           return not (left or right)

Final Comments

I know this was a long tutorial. I did not expect it to be this long. However, I hope I helped to provide some inspiration to create a more complex logic parser. My Logic Parser Repl actually has a few more operators that are in discrete math along with more operator flexibility meaning that you could type in a and b and it will be properly processed as a ^ b.


If you have any suggestions or see any issues, please let me know that way I can fix it!
If you find any bugs in my parser, definitely let me know either by leaving a comment, pinging me in Repl.it's Discord Server, or pinging me in my own Discord Server.

Commentshotnewtop
timmy_i_chen (1003)

Nice work on this :) check out your profile, you now have the Content Creator badge!

FellowHashbrown (38)

@timmy_i_chen oh sweet thanks! Thank you for your feedback :)