实现一个函数terms(s:str),输入s为一合式公式,返回s的主析取范式中包含合取式的数量。其中,s中的联结词仅可能包含¬,Λ,V,分别用not,and,or表示,s中的变元包含且仅包含P,Q,R。
时间: 2024-05-03 11:21:31 浏览: 69
思路:
首先将输入字符串s转化为后缀表达式形式,然后利用后缀表达式求主范式。
具体实现:
1. 定义一个函数infix_to_postfix(s:str)将中缀表达式s转化为后缀表达式形式。
2. 定义一个函数get_terms(postfix:str)求主析取范式中包含合取式的数量。具体实现可以使用栈,遍历后缀表达式,当遇到变量或否定符号时,将其压入栈中;当遇到合取或析取符号时,将栈中的元素弹出进行运算,并将结果压入栈中。
3. 最后,主函数terms(s:str)调用上述两个函数,返回主析取范式中包含合取式的数量。
代码实现如下:
```
def infix_to_postfix(s:str) -> str:
op_stack = []
postfix_list = []
s = s.replace(' ', '')
for c in s:
if c.isalpha():
postfix_list.append(c)
elif c == '¬':
op_stack.append(c)
elif c == 'Λ' or c == 'V':
while op_stack and op_stack[-1] != '¬' and (c == 'Λ' and op_stack[-1] == 'V'):
postfix_list.append(op_stack.pop())
op_stack.append(c)
while op_stack:
postfix_list.append(op_stack.pop())
return ''.join(postfix_list)
def get_terms(postfix:str) -> int:
stack = []
for c in postfix:
if c.isalpha():
stack.append(c)
elif c == '¬':
stack.append(c + stack.pop())
elif c == 'Λ':
b = stack.pop()
a = stack.pop()
if isinstance(a, list):
a.append(b)
stack.append(a)
else:
stack.append([a, b])
elif c == 'V':
b = stack.pop()
a = stack.pop()
if isinstance(a, list):
if isinstance(b, list):
stack.append(a + b)
else:
a.append(b)
stack.append(a)
else:
if isinstance(b, list):
b.append(a)
stack.append(b)
else:
stack.append([a, b])
return len([1 for x in stack if isinstance(x, list)])
def terms(s:str) -> int:
postfix = infix_to_postfix(s)
return get_terms(postfix)
```
测试样例:
print(terms('P Λ ¬Q V R')) # 1
print(terms('¬P Λ (Q V R)')) # 0
print(terms('¬(P V Q) V R')) # 2
print(terms('P Λ (Q V R)')) # 1
print(terms('¬P Λ (¬Q V R)')) # 0
阅读全文