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

huangapple go评论70阅读模式
英文:

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

问题

Sure, here's the translated code portion:

我想创建一个算法该算法以不带括号的命题逻辑表达式作为输入并根据逻辑连接词的不同输出所有可能的方式将表达式括起来例如如果我输入 "p and q or r implies not s"则应该得到 ((p and (q or r)) implies (not s))以下是我的代码

def parenthesize(expression):
    # 定义逻辑连接词的列表
    connectives = ["and", "or", "not", "implies", "if and only if"]

    # 基本情况:如果表达式是单个变量,则返回它括在括号中
    if expression not in connectives and len(expression.split()) == 1:
        return "(" + 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:
        # 如果有多个最外层连接词,选择第一个
        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 + ")"

# 示例用法
expression = "p and q or r implies not s"
parenthesized_expression = parenthesize(expression)
print(parenthesized_expression)

如果您需要更多帮助或有其他问题,请随时告诉我。

英文:

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

答案1

得分: 0

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

所有操作符都是左结合的,这通常不是这样,但我认为它在基本示例中表现良好。

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

可能有更紧凑和简洁的定义相同内容的方式,但这是我能想出的。

优先级顺序是:

1. 一元 not
2. 二元 and
3. 二元 or
4. 二元 implies
5. 二元 iff

这是一个用于此语法的递归下降解析器的非常基本的实现,我使用 ChatGPT 生成了它。它似乎可以正常工作,但您应该仔细检查并根据需要进行微调。

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))
英文:

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.

&lt;letter&gt; ::= &#39;a&#39; | &#39;b&#39; | ... | &#39;z&#39;
&lt;term&gt; ::= &lt;letter&gt;+
&lt;not_operator&gt; ::= &#39;not&#39;
&lt;and_operator&gt; ::= &#39;and&#39;
&lt;or_operator&gt; ::= &#39;or&#39;
&lt;implies_operator&gt; ::= &#39;implies&#39;
&lt;iff_operator&gt; ::= &#39;iff&#39;
&lt;unary_expression&gt; ::= &lt;not_operator&gt; &lt;term&gt; | &lt;term&gt;
&lt;and_expression&gt; ::= &lt;unary_expression&gt; | &lt;and_expression&gt; &lt;and_operator&gt; &lt;unary_expression&gt;
&lt;or_expression&gt; ::= &lt;and_expression&gt; | &lt;or_expression&gt; &lt;or_operator&gt; &lt;and_expression&gt;
&lt;implies_expression&gt; ::= &lt;or_expression&gt; | &lt;implies_expression&gt; &lt;implies_operator&gt; &lt;or_expression&gt;
&lt;expression&gt; ::= &lt;implies_expression&gt; | &lt;expression&gt; &lt;iff_operator&gt; &lt;implies_expression&gt;  

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 == &#39;iff&#39;:
            self.next()
            result = f&quot;({result} iff {self.parse_implies_expression()})&quot;
        return result

    def parse_implies_expression(self):
        result = self.parse_or_expression()
        while self.current_token == &#39;implies&#39;:
            self.next()
            result = f&quot;({result} implies {self.parse_or_expression()})&quot;
        return result

    def parse_or_expression(self):
        result = self.parse_and_expression()
        while self.current_token == &#39;or&#39;:
            self.next()
            result = f&quot;({result} or {self.parse_and_expression()})&quot;
        return result

    def parse_and_expression(self):
        result = self.parse_unary_expression()
        while self.current_token == &#39;and&#39;:
            self.next()
            result = f&quot;({result} and {self.parse_unary_expression()})&quot;
        return result

    def parse_unary_expression(self):
        if self.current_token == &#39;not&#39;:
            self.next()
            return f&quot;(not {self.parse_term()})&quot;
        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 = &quot;a implies b iff a and b&quot;
print(parse_string(input_str))

huangapple
  • 本文由 发表于 2023年6月12日 20:39:14
  • 转载请务必保留本文链接:https://go.coder-hub.com/76456755.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定