Parsing A Boolean Expression in Python

Suppose we have a boolean expression, we have to find the result after evaluating that expression.

An expression can either be −

• "t", evaluating to True;

• "f", evaluating to False;

• "!(expression)", evaluating to the logical NOT of the inner expression;

• "&(expr1,expr2,...)", evaluating to the logical AND of 2 or more inner expressions;

• "|(expr1,expr2,...)", evaluating to the logical OR of 2 or more inner expressions;

So, if the input is like "|(!(t),&(t,f,t))", then the output will be fasle, this is because !(t) is false, then &(t,f,t) is also false, so the OR of all false values will be false.

To solve this, we will follow these steps −

• define solve(), this will take e, i

• if e[i] is same as "f", then −

  • return (False, i + 1)

• Otherwise when e[i] is same as "t" −

• return (True,i + 1)

• op := e[i], i := i + 2

• Define one stack

• while e[i] is not closing parentheses, do −

  • if e[i] is same as ",", then −

    • i := i + 1

    • Ignore following part, skip to the next iteration

  • res,i := solve(e, i)

  • push res into stack

• if op is same as "&", then −

  • return true when all elements are true in stack, otherwise false, i + 1

• otherwise when op is same as " OR " −

  • return true when at least one elements is true in stack, otherwise false, i + 1

• return (inverse of stack[0], i + 1)

• From the main method, do the following −

• s,y := solve(expression, 0)

• return s

Let us see the following implementation to get better understanding −

Example

 Live Demo

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))"))

Input

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

Output

False