How to create an algorithm that takes as input a propositional logic expression without parentheses and encloses the same in parentheses in Python

Question

I'd like to create an algorithm that takes as input a propositional logic expression without parentheses and outputs the same expression enclosed in parentheses in all possible ways depending on the logical connectives present. For example, if I have "p and q or r implies not s" as input I should obtain ((p and (q or r)) implies (not s): here's my code:

def parenthesize(expression):
    # Define a list of logical connectives
    connectives = ["and", "or", "not", "implies", "if and only if"]

    # Base case: if the expression is a single variable, return it enclosed in parentheses
    if expression not in connectives and len(expression.split()) == 1:
        return "(" + expression + ")"

    # Recursive case: find the outermost connective and apply the algorithm to each sub-expression
    nesting_levels = [0] * len(expression)
    stack = []
    for i, char in enumerate(expression):
        if char == "(":
            stack.append(i)
        elif char == ")":
            j = stack.pop()
            nesting_levels[j:i+1] = [len(stack)] * (i-j+1)

    max_nesting_level = max(nesting_levels)
    outermost_connectives = [connectives[i] for i, level in enumerate(nesting_levels) if level == max_nesting_level]

    if len(outermost_connectives) == 1:
        connective = outermost_connectives[0]
        subexpressions = expression.split(connective)
        parenthesized_subexpressions = [parenthesize(subexpression) for subexpression in subexpressions]
        return "(" + connective.join(parenthesized_subexpressions) + ")"
    else:
        # If there are multiple outermost connectives, choose the first one
        connective = outermost_connectives[0]
        index = expression.index(connective)
        left_expression = expression[:index].strip()
        right_expression = expression[index+len(connective):].strip()
        parenthesized_left_expression = parenthesize(left_expression)
        parenthesized_right_expression = parenthesize(right_expression)
        return "(" + parenthesized_left_expression + " " + connective + " " + parenthesized_right_expression + ")"

# Example usage
expression = "p and q or r implies not s"
parenthesized_expression = parenthesize(expression)
print(parenthesized_expression)

Problem is my output is wrong: it's "(p and q or r implies not s)", could someone lead me to a solution? Thanks

Answer 1

I wrote the following EBNF to define a very basic version of your inputs.

All operators are left associative, which is not usually the case, but I think that it serves well as a basic example.

<letter> ::= 'a' | 'b' | ... | 'z'
<term> ::= <letter>+

<not_operator> ::= 'not'
<and_operator> ::= 'and'
<or_operator> ::= 'or'
<implies_operator> ::= 'implies'
<iff_operator> ::= 'iff'

<unary_expression> ::= <not_operator> <term> | <term>
<and_expression> ::= <unary_expression> | <and_expression> <and_operator> <unary_expression>
<or_expression> ::= <and_expression> | <or_expression> <or_operator> <and_expression>
<implies_expression> ::= <or_expression> | <implies_expression> <implies_operator> <or_expression>
<expression> ::= <implies_expression> | <expression> <iff_operator> <implies_expression>  

There might be more compact and concise ways of defining the same thing, but this is what I was able to come up with.

The order of precedence is:

1. Unary not
2. Binary and
3. Binary or
4. Binary implies
5. Binary iff

Here is a very basic implementation of a recursive descent parser for this grammar I generated with ChatGPT. It seems to work fine however you should double check and tweak it to your needs.

class Parser:
    def __init__(self, input):
        self.tokens = input.split()
        self.current_token = None
        self.next()

    def next(self):
        if len(self.tokens) == 0:
            self.current_token = None
        else:
            self.current_token = self.tokens.pop(0)

    def parse_expression(self):
        result = self.parse_implies_expression()
        while self.current_token == 'iff':
            self.next()
            result = f"({result} iff {self.parse_implies_expression()})"
        return result

    def parse_implies_expression(self):
        result = self.parse_or_expression()
        while self.current_token == 'implies':
            self.next()
            result = f"({result} implies {self.parse_or_expression()})"
        return result

    def parse_or_expression(self):
        result = self.parse_and_expression()
        while self.current_token == 'or':
            self.next()
            result = f"({result} or {self.parse_and_expression()})"
        return result

    def parse_and_expression(self):
        result = self.parse_unary_expression()
        while self.current_token == 'and':
            self.next()
            result = f"({result} and {self.parse_unary_expression()})"
        return result

    def parse_unary_expression(self):
        if self.current_token == 'not':
            self.next()
            return f"(not {self.parse_term()})"
        else:
            return self.parse_term()

    def parse_term(self):
        term = self.current_token
        self.next()
        return term

def parse_string(input_str):
    parser = Parser(input_str)
    return parser.parse_expression()

input_str = "a implies b iff a and b"
print(parse_string(input_str))