Python 中如何编写程序来评估字符串中的布尔表达式？

假设我们有一个包含布尔表达式的字符串 s，其中包含运算符“and”和“or”，评估它并返回结果。这里的表达式可能包含括号，应优先评估。

因此，如果输入类似于 s = "T and (F or T)"，则输出将为 True

为了解决这个问题，我们将遵循以下步骤

• stack := 一个新的列表

• t = s 中以空格分隔的元素的列表

• 对于 t 中的每个 v，执行以下操作：

  • 如果 v[0] 与 "(" 相同，则

    • 当 v[从 "(" 的索引到末尾] 与 "T" 相同时，将 true 推入堆栈

  • 否则，当找到 ")" 时，则

    • ct := v 中 ")" 的数量

    • 当 v[从索引 0 到 v 的大小 - ct] 与 "T" 相同时，将 true 推入堆栈

    • 对于 ct-1 范围内的每个值，执行以下操作：

      • right := 从堆栈中弹出

• := 从堆栈中弹出

  • left := 从堆栈中弹出

  • 执行操作 (left o right) 并将其推入堆栈

  • 否则，当 v 为 "T" 或 "F" 时，则

    • 当 v 与 "T" 相同时，将 true 推入堆栈

  • 否则，

    • 将 op[v] 推入堆栈

• 如果堆栈中的元素数量 > 1，则

  • 对于 0 到堆栈大小 - 1 的 i 范围，以 2 为增量，执行以下操作：

    • stack[i + 2] := stack[i + 1](stack[i], stack[i + 2])

  • 返回堆栈的顶部元素

• 返回堆栈的底部元素

让我们查看以下实现以更好地理解

示例

 实时演示

class Solution:
   def solve(self, s):
      stack = []
      op = {
         "or": lambda x, y: x or y,
         "and": lambda x, y: x and y,
      }
      for v in s.split():
         if v[0] == "(":
            stack.append(v[v.count("(") :] == "T")
         elif v.count(")") > 0:
            ct = v.count(")")
            stack.append(v[:-ct] == "T")
            for _ in range(ct):
               right = stack.pop()
               o = stack.pop()
               left = stack.pop()
               stack.append(o(left, right))
         elif v in ["T", "F"]:
            stack.append(v == "T")
         else:
            stack.append(op[v])

      if len(stack) > 1:
         for i in range(0, len(stack) - 1, 2):
            stack[i + 2] = stack[i + 1](stack[i], stack[i + 2])
         return stack[-1]

      return stack[0]

ob = Solution()
s = "T and (F or T)"
print(ob.solve(s))

输入

"T and (F or T)"

输出

True

Arnab Chakraborty

更新于: 2020年11月10日

752 次浏览

开启你的 职业生涯

通过完成课程获得认证

立即开始