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评论100阅读模式
英文:

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:

  1. 我想创建一个算法，该算法以不带括号的命题逻辑表达式作为输入，并根据逻辑连接词的不同，输出所有可能的方式将表达式括起来。例如，如果我输入 "p and q or r implies not s"，则应该得到 ((p and (q or r)) implies (not s))，以下是我的代码：
  3. def parenthesize(expression):
  4.     # 定义逻辑连接词的列表
  5.     connectives = ["and", "or", "not", "implies", "if and only if"]
  7.     # 基本情况：如果表达式是单个变量，则返回它括在括号中
  8.     if expression not in connectives and len(expression.split()) == 1:
  9.         return "(" + expression + ")"
  11.     # 递归情况：找到最外层的逻辑连接词并对每个子表达式应用算法
  12.     nesting_levels = [0] * len(expression)
  13.     stack = []
  14.     for i, char in enumerate(expression):
  15.         if char == "(":
  16.             stack.append(i)
  17.         elif char == ")":
  18.             j = stack.pop()
  19.             nesting_levels[j:i+1] = [len(stack)] * (i-j+1)
  21.     max_nesting_level = max(nesting_levels)
  22.     outermost_connectives = [connectives[i] for i, level in enumerate(nesting_levels) if level == max_nesting_level]
  24.     if len(outermost_connectives) == 1:
  25.         connective = outermost_connectives[0]
  26.         subexpressions = expression.split(connective)
  27.         parenthesized_subexpressions = [parenthesize(subexpression) for subexpression in subexpressions]
  28.         return "(" + connective.join(parenthesized_subexpressions) + ")"
  29.     else:
  30.         # 如果有多个最外层连接词，选择第一个
  31.         connective = outermost_connectives[0]
  32.         index = expression.index(connective)
  33.         left_expression = expression[:index].strip()
  34.         right_expression = expression[index+len(connective):].strip()
  35.         parenthesized_left_expression = parenthesize(left_expression)
  36.         parenthesized_right_expression = parenthesize(right_expression)
  37.         return "(" + parenthesized_left_expression + " " + connective + " " + parenthesized_right_expression + ")"
  39. # 示例用法
  40. expression = "p and q or r implies not s"
  41. parenthesized_expression = parenthesize(expression)
  42. 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:

  1. def parenthesize(expression):
  2. # Define a list of logical connectives
  3. connectives = ["and", "or", "not", "implies", "if and only if"]
  4. # Base case: if the expression is a single variable, return it enclosed in parentheses
  5. if expression not in connectives and len(expression.split()) == 1:
  6. return "(" + expression + ")"
  7. # Recursive case: find the outermost connective and apply the algorithm to each sub-expression
  8. nesting_levels = [0] * len(expression)
  9. stack = []
  10. for i, char in enumerate(expression):
  11. if char == "(":
  12. stack.append(i)
  13. elif char == ")":
  14. j = stack.pop()
  15. nesting_levels[j:i+1] = [len(stack)] * (i-j+1)
  16. max_nesting_level = max(nesting_levels)
  17. outermost_connectives = [connectives[i] for i, level in enumerate(nesting_levels) if level == max_nesting_level]
  18. if len(outermost_connectives) == 1:
  19. connective = outermost_connectives[0]
  20. subexpressions = expression.split(connective)
  21. parenthesized_subexpressions = [parenthesize(subexpression) for subexpression in subexpressions]
  22. return "(" + connective.join(parenthesized_subexpressions) + ")"
  23. else:
  24. # If there are multiple outermost connectives, choose the first one
  25. connective = outermost_connectives[0]
  26. index = expression.index(connective)
  27. left_expression = expression[:index].strip()
  28. right_expression = expression[index+len(connective):].strip()
  29. parenthesized_left_expression = parenthesize(left_expression)
  30. parenthesized_right_expression = parenthesize(right_expression)
  31. return "(" + parenthesized_left_expression + " " + connective + " " + parenthesized_right_expression + ")"
  32. # Example usage
  33. expression = "p and q or r implies not s"
  34. parenthesized_expression = parenthesize(expression)
  35. 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.

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

  1. <letter> ::= 'a' | 'b' | ... | 'z'
  2. <term> ::= <letter>+
  4. <not_operator> ::= 'not'
  5. <and_operator> ::= 'and'
  6. <or_operator> ::= 'or'
  7. <implies_operator> ::= 'implies'
  8. <iff_operator> ::= 'iff'
  10. <unary_expression> ::= <not_operator> <term> | <term>
  11. <and_expression> ::= <unary_expression> | <and_expression> <and_operator> <unary_expression>
  12. <or_expression> ::= <and_expression> | <or_expression> <or_operator> <and_expression>
  13. <implies_expression> ::= <or_expression> | <implies_expression> <implies_operator> <or_expression>
  14. <expression> ::= <implies_expression> | <expression> <iff_operator> <implies_expression>

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

优先级顺序是：

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

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

  1. class Parser:
  2.     def __init__(self, input):
  3.         self.tokens = input.split()
  4.         self.current_token = None
  5.         self.next()
  7.     def next(self):
  8.         if len(self.tokens) == 0:
  9.             self.current_token = None
  10.         else:
  11.             self.current_token = self.tokens.pop(0)
  13.     def parse_expression(self):
  14.         result = self.parse_implies_expression()
  15.         while self.current_token == 'iff':
  16.             self.next()
  17.             result = f"({result} iff {self.parse_implies_expression()})"
  18.         return result
  20.     def parse_implies_expression(self):
  21.         result = self.parse_or_expression()
  22.         while self.current_token == 'implies':
  23.             self.next()
  24.             result = f"({result} implies {self.parse_or_expression()})"
  25.         return result
  27.     def parse_or_expression(self):
  28.         result = self.parse_and_expression()
  29.         while self.current_token == 'or':
  30.             self.next()
  31.             result = f"({result} or {self.parse_and_expression()})"
  32.         return result
  34.     def parse_and_expression(self):
  35.         result = self.parse_unary_expression()
  36.         while self.current_token == 'and':
  37.             self.next()
  38.             result = f"({result} and {self.parse_unary_expression()})"
  39.         return result
  41.     def parse_unary_expression(self):
  42.         if self.current_token == 'not':
  43.             self.next()
  44.             return f"(not {self.parse_term()})"
  45.         else:
  46.             return self.parse_term()
  48.     def parse_term(self):
  49.         term = self.current_token
  50.         self.next()
  51.         return term
  53. def parse_string(input_str):
  54.     parser = Parser(input_str)
  55.     return parser.parse_expression()
  57. input_str = "a implies b iff a and b"
  58. 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.

  1. &lt;letter&gt; ::= &#39;a&#39; | &#39;b&#39; | ... | &#39;z&#39;
  2. &lt;term&gt; ::= &lt;letter&gt;+
  3. &lt;not_operator&gt; ::= &#39;not&#39;
  4. &lt;and_operator&gt; ::= &#39;and&#39;
  5. &lt;or_operator&gt; ::= &#39;or&#39;
  6. &lt;implies_operator&gt; ::= &#39;implies&#39;
  7. &lt;iff_operator&gt; ::= &#39;iff&#39;
  8. &lt;unary_expression&gt; ::= &lt;not_operator&gt; &lt;term&gt; | &lt;term&gt;
  9. &lt;and_expression&gt; ::= &lt;unary_expression&gt; | &lt;and_expression&gt; &lt;and_operator&gt; &lt;unary_expression&gt;
  10. &lt;or_expression&gt; ::= &lt;and_expression&gt; | &lt;or_expression&gt; &lt;or_operator&gt; &lt;and_expression&gt;
  11. &lt;implies_expression&gt; ::= &lt;or_expression&gt; | &lt;implies_expression&gt; &lt;implies_operator&gt; &lt;or_expression&gt;
  12. &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. 1. Unary not
  2. 2. Binary and
  3. 3. Binary or
  4. 4. Binary implies
  5. 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.

  1. class Parser:
  2.     def __init__(self, input):
  3.         self.tokens = input.split()
  4.         self.current_token = None
  5.         self.next()
  7.     def next(self):
  8.         if len(self.tokens) == 0:
  9.             self.current_token = None
  10.         else:
  11.             self.current_token = self.tokens.pop(0)
  13.     def parse_expression(self):
  14.         result = self.parse_implies_expression()
  15.         while self.current_token == &#39;iff&#39;:
  16.             self.next()
  17.             result = f&quot;({result} iff {self.parse_implies_expression()})&quot;
  18.         return result
  20.     def parse_implies_expression(self):
  21.         result = self.parse_or_expression()
  22.         while self.current_token == &#39;implies&#39;:
  23.             self.next()
  24.             result = f&quot;({result} implies {self.parse_or_expression()})&quot;
  25.         return result
  27.     def parse_or_expression(self):
  28.         result = self.parse_and_expression()
  29.         while self.current_token == &#39;or&#39;:
  30.             self.next()
  31.             result = f&quot;({result} or {self.parse_and_expression()})&quot;
  32.         return result
  34.     def parse_and_expression(self):
  35.         result = self.parse_unary_expression()
  36.         while self.current_token == &#39;and&#39;:
  37.             self.next()
  38.             result = f&quot;({result} and {self.parse_unary_expression()})&quot;
  39.         return result
  41.     def parse_unary_expression(self):
  42.         if self.current_token == &#39;not&#39;:
  43.             self.next()
  44.             return f&quot;(not {self.parse_term()})&quot;
  45.         else:
  46.             return self.parse_term()
  48.     def parse_term(self):
  49.         term = self.current_token
  50.         self.next()
  51.         return term
  53. def parse_string(input_str):
  54.     parser = Parser(input_str)
  55.     return parser.parse_expression()
  57. input_str = &quot;a implies b iff a and b&quot;
  58. print(parse_string(input_str))

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

发表评论

匿名网友

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

确定