在Python中解析布尔表达式

假设我们有一个布尔表达式，我们必须在对该表达式求值后找到结果。

表达式可以是-

• “ t”，评估为True；

• “ f”，评估为False；

• “！（表达式）”，计算内部表达式的逻辑非；

• “＆(expr1,expr2,...)”，计算2个或更多内部表达式的逻辑与；

• “ |(expr1,expr2,...)”，求两个或多个内部表达式的逻辑或；

因此，如果输入类似于“ |（！(t)，＆(t,f,t)）”，则输出将变得混乱，这是因为！(t)为假，则＆（t，f， t）也为假，因此所有假值的OR均为假。

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

• 定义solve()，这将需要e，i

• 如果e [i]与“ f”相同，则-

• 返回（False，i + 1）

• 否则，当e [i]与“ t”相同时-

• 返回（True，i + 1）

• op：= e [i]，i：= i + 2

• 定义一个堆栈

• 当e [i]不在右括号中时，执行-

• 我：=我+ 1

• 忽略以下部分，跳至下一个迭代

• 如果e [i]与“，”相同，则-

• res，i：=解决(e,i)

• 将res推入堆栈

• 如果op与“＆”相同，则-

• 当所有元素在堆栈中都为true时，返回true；否则为i + 1

• 否则，当op与“ OR”相同时-

• 当至少一个元素在堆栈中为true时返回true，否则为false，i + 1

• 返回（堆栈[0]的逆，i + 1）

• 从主要方法中，执行以下操作-

• s，y：= solve（表达式，0）

• 返回s

让我们看下面的实现以更好地理解-

示例

class Solution(object):
   def parseBoolExpr(self, expression):
      s,y = self.solve(expression,0)
      return s
   def solve(self,e,i):
      if e[i] =="f":
         return False,i+1
      elif e[i] == "t":
         return True,i+1
      op = e[i]
      i = i+2
      stack = []
      while e[i]!=")":
         if e[i] == ",":
            i+=1
            continue
         res,i = self.solve(e,i)
         stack.append(res)
      if op == "&":
         return all(stack),i+1
      elif op == "|":
         return any(stack),i+1
      return not stack[0],i+1
ob = Solution()print(ob.parseBoolExpr("|(!(t),&(t,f,t))"))

输入项

"|(!(t),&(t,f,t))"

输出结果

False