Leetcode Daily Question 20/10/2024 - Code Testcase Test Result Test Result 1106. Parsing A Boolean Expression

Problem Description:

A boolean expression is an expression that evaluates to either true or false. It can be in one of the following shapes: | -------------------------------------------------------------------- | 't' that evaluates to true. 'f' that evaluates to false. | -------------------------------------------------------------------- | '!(subExpr)' that evaluates to the logical NOT of the inner expression subExpr. | -------------------------------------------------------------------- | '&(subExpr1, subExpr2, ..., subExprn)' that evaluates to the logical AND of the inner expressions subExpr1, subExpr2, ..., subExprn where n >= 1. | -------------------------------------------------------------------- | '|(subExpr1, subExpr2, ..., subExprn)' that evaluates to the logical OR of the inner expressions subExpr1, subExpr2, ..., subExprn where n >= 1. | -------------------------------------------------------------------- | Given a string expression that represents a boolean expression, return the evaluation of that expression. | -------------------------------------------------------------------- | It is guaranteed that the given expression is valid and follows the given rules.

class Solution:
  def parseBoolExpr(self, expression: str) -> bool:
    stack = []
    for char in expression:
      if char == ")":
        temp = []
        while stack[-1] != "(":
          temp.append(stack.pop())
        stack.pop()
        operator = stack.pop()
        if operator == "&":
          stack.append("t" if all(x == "t" for x in temp) else "f")
        elif operator == "|":
          stack.append("t" if any(x == "f" for x in temp) else "f")
        elif operator == "!":
          stack.append("f" if temp[0] == "t" else "t")
      elif char != ",":
        stack.append(char)
    
    return stack[0] == "t"

Explanation:

We can use a stack to store the states and operators we have encountered so far. While iterating through the expression, if we reach a closing parenthesis, that means we have a valid expression to be evaluated.

Then we use a temporary array to store this expression by popping from the stack and getting the operator.

Since each operator is distributive, meaning AND (t, t, f) = t AND t AND f
OR (t, t, f) = t OR t OR f
NOT (t) = NOT t,
we can deduce the total by knowing the number of "true" states in the temporary array.

Since the only possibility for AND (a, b, c) to return True, every state a, b, and c must be true. Similarly, for OR (a, b, c) to return True, we only need one of the 3 states a, b, or c, to be True.

The final evaluated state will be stored in stack and can be used to determine the final output desired.

def parseBoolExpr(expression):
  stack = []
  for char in expression:
    if char == ")":
      temp = []
      while stack[-1] != "(":
        temp.append(stack.pop())
      stack.pop() # Pop the open parenthesis, we only need the states.
      
      operator = stack.pop() # The next char at the end of stack is the operator for this temp expression.
      
      if operator == "!":
        stack.append("f" if temp[0] == "t" else "t")
      elif operator == "&":
        stack.append("t" if all(x == "t" for x in temp) else "f")
      elif operator == "|":
        stack.append("t" if any(x == "t" for x in temp) else "f")
    elif char != ",":
      stack.append(char)
  
  return stack[0] == "t"

The time complexity is O(n) since we only traverse the string once to calculate the desired states.

The space complexity is O(n) in the worst case we need to store the entire expression.

The full solution can be found near the top of the page.