Pythonでのブール式の解析

ブール式があるとすると、その式を評価した後で結果を見つける必要があります。

式は次のいずれかになります-

• 「t」、Trueと評価;

• 「f」、Falseと評価;

• 「！（式）」、内部式の論理否定に評価します;

• "＆（expr1、expr2、...）"、2つ以上の内部式の論理ANDに評価;

• "|（expr1、expr2、...）"、2つ以上の内部式の論理和に評価;

したがって、入力が「|（！（t）、＆（t、f、t））」のような場合、出力は簡単になります。これは、！（t）がfalseであるため、＆（t、f、 t）もfalseであるため、すべてのfalse値のORはfalseになります。

これを解決するには、次の手順に従います-

• 定義solve（）、これはe、iを取ります

• e[i]が"f"と同じ場合、-

  • return（False、i + 1）

• それ以外の場合、e[i]が"t"-

  と同じ場合

• return（True、i + 1）

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

• 1つのスタックを定義する

• e [i]が括弧を閉じていない間は、-

  を実行します。

  • e [i]が「、」と同じ場合、-

    • i：=i + 1

    • 次の部分を無視し、次の反復にスキップします

  • res、i：=resolve（e、i）

  • 解像度をスタックにプッシュする

• opが「＆」と同じ場合、-

  • スタック内のすべての要素がtrueの場合はtrueを返し、それ以外の場合はfalseを返します。i+ 1

• それ以外の場合、opが「OR」と同じ場合-

  • スタック内の少なくとも1つの要素がtrueの場合はtrueを返し、それ以外の場合はfalseを返します。i+ 1

• return（stack [0]の逆、i + 1）

• メインの方法から、次のようにします-

• s、y：=resolve（expression、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