英文:
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.
<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))
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论