如何在 Python 的一阶逻辑公式中尽可能放置括号？这个公式只存在于逻辑非 ¬ 和 ∧ 或 ∨，意味着 → 和 bi 意味着 ↔。例如“¬(A ∧ B) ∨ C”产生 ((¬(A ∧ B)) ∨ C)。你可以在下面看到我的尝试。我想要一个将每个运算符包装在括号中的函数（请参阅测试），因此括号内只有一个运算符。有谁知道为什么我的代码失败或解决这个问题的任何方法？
import re
def add_brackets(formula):
# Define operator priorities
priority = {'¬': 4, '∧': 3, '∨': 2, '→': 1, '↔': 0}
# Convert formula to list of tokens
tokens = re.findall(r'\(|\)|¬|∧|∨|→|↔|[A-Z]', formula)
# Initialize stack to hold operators
stack = []
# Initialize queue to hold output
output = []
# Loop through tokens
for token in tokens:
if token.isalpha():
output.append(token)
elif token == '¬':
stack.append(token)
elif token in '∧∨→↔':
while stack and stack[-1] != '(' and priority[token] <= priority[stack[-1]]:
output.append(stack.pop())
stack.append(token)
elif token == '(':
stack.append(token)
elif token == ')':
while stack and stack[-1] != '(':
output.append(stack.pop())
stack.pop()
# Empty out remaining operators on the stack
while len(stack) != 0:
if stack[-1] == '(':
raise ValueError('Unmatched left parenthesis')
output.append(stack.pop())
# Loop through output
for i, token in enumerate(output):
if token in '∧∨→↔':
if len(output) < i + 3:
raise ValueError('Invalid formula')
result = '({} {} {})'.format(output[i+1], token, output[i+2])
output[i:i+3] = [result]
# Return final result
return output[0]
# Formula 1
formula1 = "A ∧ B ∨ C"
assert add_brackets(formula1) == "(A ∧ (B ∨ C))"
# Formula 2
formula2 = "¬(A ∧ B) ∨ C"
assert add_brackets(formula2) == "((¬(A ∧ B)) ∨ C)"
# Formula 3
formula3 = "A ∧ B ∧ C ∧ D ∧ E"
assert add_brackets(formula3) == "((((A ∧ B) ∧ C) ∧ D) ∧ E))"
# Formula 4
formula4 = "¬A ∧ ¬B ∧ ¬C"
assert add_brackets(formula4) == "(((¬A) ∧ (¬B)) ∧ (¬C))"
# Formula 5
formula5 = "A ∧ ¬(B ∨ C)"
assert add_brackets(formula5) == "(A ∧ (¬(B ∨ C)))"
# Formula 6
formula6 = "A ∨ B → C ∧ D"
assert add_brackets(formula6) == "((A ∨ B) → (C ∧ D))"
# Formula 7
formula7 = "A ∧ B → C ∨ D"
assert add_brackets(formula7) == "(((A ∧ B) → (C ∨ D)))"
# Formula 8
formula8 = "¬(A ∧ B) → C ∨ D"
assert add_brackets(formula8) == "((¬(A ∧ B)) → (C ∨ D))"
# Formula 9
formula9 = "(A → B) → (C → D)"
assert add_brackets(formula9) == "((A → B) → (C → D))"
# Formula 10
formula10 = "(A ∧ B) ∨ (C ∧ D) → E"
assert add_brackets(formula10) == "(((A ∧ B) ∨ (C ∧ D)) → E)"
Pyparsing 是一个 Python 解析器组合器库，用于使用其自己的嵌入式 DSL 语法构建解析器。将其视为一种冗长的正则表达式，但具有更多递归语法、命名结果和解析时回调的功能。
Pyparsing 还包括用于常见构造的帮助程序或宏方法，如分隔列表、带引号的字符串和其他模式，如 IP 地址、日期/时间时间戳等。一种这样的方法是用于定义中缀表示法的方法，你可以在其中提供和表达对于基本操作数（在您的情况下，单个字母）和按优先顺序定义操作的元组列表。每个元组包含符号、操作数的数量以及右或左结合性。
这是解析语法的整个 pyparsing 解析器：
import pyparsing as pp
var = pp.Word(pp.alphas)
expr = pp.infix_notation(
var,
[
# '¬': 4, '∧': 3, '∨': 2, '→': 1, '↔': 0
('¬', 1, pp.opAssoc.RIGHT),
('∧', 2, pp.opAssoc.LEFT),
('∨', 2, pp.opAssoc.LEFT),
('→', 2, pp.opAssoc.LEFT),
('↔', 2, pp.opAssoc.LEFT),
]
)
Pyparsing 表达式有一个
run_testsrun_tests这是您的测试字符串：
test_strings = (
"""
# Formula 1
A ∧ B ∨ C
# Formula 2
¬(A ∧ B) ∨ C
# Formula 3
A ∧ B ∧ C ∧ D ∧ E
# Formula 4
¬A ∧ ¬B ∧ ¬C
# Formula 5
A ∧ ¬(B ∨ C)
# Formula 6
A ∨ B → C ∧ D
# Formula 7
A ∧ B → C ∨ D
# Formula 8
¬(A ∧ B) → C ∨ D
# Formula 9
(A → B) → (C → D)
# Formula 10
(A ∧ B) ∨ (C ∧ D) → E
"""
)
expr.run_tests(test_strings, full_dump=False)
调用
run_tests# Formula 1
A ∧ B ∨ C
[[['A', '∧', 'B'], '∨', 'C']]
# Formula 2
¬(A ∧ B) ∨ C
[[['¬', ['A', '∧', 'B']], '∨', 'C']]
# Formula 3
A ∧ B ∧ C ∧ D ∧ E
[['A', '∧', 'B', '∧', 'C', '∧', 'D', '∧', 'E']]
# Formula 4
¬A ∧ ¬B ∧ ¬C
[[['¬', 'A'], '∧', ['¬', 'B'], '∧', ['¬', 'C']]]
# Formula 5
A ∧ ¬(B ∨ C)
[['A', '∧', ['¬', ['B', '∨', 'C']]]]
# Formula 6
A ∨ B → C ∧ D
[[['A', '∨', 'B'], '→', ['C', '∧', 'D']]]
# Formula 7
A ∧ B → C ∨ D
[[['A', '∧', 'B'], '→', ['C', '∨', 'D']]]
# Formula 8
¬(A ∧ B) → C ∨ D
[[['¬', ['A', '∧', 'B']], '→', ['C', '∨', 'D']]]
# Formula 9
(A → B) → (C → D)
[[['A', '→', 'B'], '→', ['C', '→', 'D']]]
# Formula 10
(A ∧ B) ∨ (C ∧ D) → E
[[[['A', '∧', 'B'], '∨', ['C', '∧', 'D']], '→', 'E']]
这非常接近您想要的输出，尽管这些是经过解析的嵌套列表，我们真的希望您的输出字符串带有括号。您还会注意到 pyparsing 不会发出所有二进制输出，但是对于具有相同运算符的重复操作数，您只会得到一个列表（就像公式 3
A ∧ B ∧ C ∧ D ∧ E[['A', '∧', 'B', '∧', 'C', '∧', 'D', '∧', 'E']]infix_notationdef unary_regroup(tokens):
t = tokens[0]
return [pp.ParseResults([t[0], [t[1:]]])]
def binary_regroup(tokens):
t = t[0]
op = t[1]
opers = t[::2]
ret = pp.ParseResults([opers[0], op, opers[1]])
for operand in opers[2:]:
ret = pp.ParseResults([ret, op, operand])
return [ret]
var = pp.Word(pp.alphas)
expr = pp.infix_notation(
var,
[
# '¬': 4, '∧': 3, '∨': 2, '→': 1, '↔': 0
('¬', 1, pp.opAssoc.RIGHT, unary_regroup),
('∧', 2, pp.opAssoc.LEFT, binary_regroup),
('∨', 2, pp.opAssoc.LEFT, binary_regroup),
('→', 2, pp.opAssoc.LEFT, binary_regroup),
('↔', 2, pp.opAssoc.LEFT, binary_regroup),
]
)
（我为这两个函数的复杂性道歉，当解析操作需要返回不是简单结构的标记列表时，pyparsing 有点挑剔。）
如果我们现在为公式 3 调用
run_tests# Formula 3
A ∧ B ∧ C ∧ D ∧ E
[[[[['A', '∧', 'B'], '∧', 'C'], '∧', 'D'], '∧', 'E']]
现在我们可以编写递归方法将其转换为带有嵌套括号的字符串：
for test in test_strings.splitlines():
test = test.strip()
if not test or test.startswith("#"):
print(test)
continue
parsed = expr.parse_string(test)
def enclose_groups_in_parens(t):
ret = []
for ob in t:
if isinstance(ob, (pp.ParseResults, list)):
ret.append(enclose_groups_in_parens(ob))
else:
ret.append(ob)
return f"({' '.join(ret)})" if len(ret) > 1 else ' '.join(ret)
regrouped_string = enclose_groups_in_parens(parsed)
print(test, '->', regrouped_string)
打印：
# Formula 1
A ∧ B ∨ C -> ((A ∧ B) ∨ C)
# Formula 2
¬(A ∧ B) ∨ C -> ((¬ (A ∧ B)) ∨ C)
# Formula 3
A ∧ B ∧ C ∧ D ∧ E -> ((((A ∧ B) ∧ C) ∧ D) ∧ E)
# Formula 4
¬A ∧ ¬B ∧ ¬C -> (((¬ A) ∧ (¬ B)) ∧ (¬ C))
# Formula 5
A ∧ ¬(B ∨ C) -> (A ∧ (¬ (B ∨ C)))
# Formula 6
A ∨ B → C ∧ D -> ((A ∨ B) → (C ∧ D))
# Formula 7
A ∧ B → C ∨ D -> ((A ∧ B) → (C ∨ D))
# Formula 8
¬(A ∧ B) → C ∨ D -> ((¬ (A ∧ B)) → (C ∨ D))
# Formula 9
(A → B) → (C → D) -> ((A → B) → (C → D))
# Formula 10
(A ∧ B) ∨ (C ∧ D) → E -> (((A ∧ B) ∨ (C ∧ D)) → E)